L9: Make a Hash of It

<aside> #️⃣

L9 — Make a Hash of It covers hash tables: the concept of content-addressable memory, hash functions (design, modulo operation, prime number table sizes), hash collisions and two strategies for handling them — separate chaining (linked lists at each index) and open addressing (linear probing, quadratic probing, double hashing). It also covers the load factor, deletion problems in open addressing, and practical comparisons with other data structures.

</aside>

📋 At a Glance

[ ] Understand the motivation: searching an unsorted list is O(n), BSTs give O(log n), Tries give O(1) but waste memory
[ ] Know that a hash table combines O(1) average lookup with reasonable memory usage
[ ] Explain what a hash function does: maps a key to an integer index in a table
[ ] Know that hash function output must be taken modulo M (table size) to fit within the table
[ ] Explain why prime numbers should be used for the table size M
[ ] Define hash collision: two different keys mapping to the same index
[ ] Understand data bias — real-world data is never uniformly distributed, causing clustering
[ ] Know the properties of a good hash function: fast, uniform distribution, consistent
[ ] Trace a separate chaining example: inserting, searching, and deleting with linked lists
[ ] Know separate chaining complexity: O(1) best case, O(n) worst case (all keys in one list)
[ ] Trace a linear probing example: inserting and searching with open addressing
[ ] Understand primary clustering in linear probing and why it degrades performance
[ ] Explain quadratic probing: step sizes 1², 2², 3², … to escape clusters
[ ] Know the risk of quadratic probing: may cycle through the same slots and miss empty ones
[ ] Explain double hashing: use a second hash function h₂(x) for the step size
[ ] Know that h₂ must not be a divisor of table size (another reason for prime M)
[ ] Understand the deletion problem in open addressing and the dummy/tombstone solution