Session 1 - Hash Tables

Icebreaker question

If you could magically change one annoying thing about coding forever, what would it be?

Icebreaker results

Learning objectives

In this session of class we will learn about hash tables, an efficient data structure for mapping key/value pairs. By the end of this session you will be more familiar with the following topics:

• Hash tables: A practical & efficient data structure for storing key/value pairs
• Hash functions for mapping keys to integer values
• Useful hash function properties: Determinism, efficiency, & uniformity of hashes
• Collision-handling schemes: Separate chaining & Linear probing
• Load factor & hash table resizing

In class exercises

• Why don't we just ask ChatGPT to explain hash tables to us? It seems easier that way, and maybe then you won't need me anymore.
• Lecture 1: Introduction to hash tables
• Tutorial 1.0: Hash Table Excercises (jupyter notebook)
• Tutorial 1.1: Interactive Hash Table Exploration

Assignments

• Implement hash table classes in python for each of the collision resolution strategies we discussed today: and HashTableChaining for separate chaining; and HashTableProbing for linear probing. Add them to a hash_tables.py file in the data_structures module of your CSCI232 github repo, and commit/push the changes when they are complete.
• Read Chapter 12 "Sorting and Selection" in Data Structures and Algorithms in Python by Goodrich, Tamassia & Goldwasser (pdf)
• Watch the video 15 sorting Algorithms in 6 minutes
  • ^{_{Most visually satisfying: Merge sort}}
  • ^{_{Most intellectually satisfying: Bogosort}}

---