Data Structures & Big-O (CS 201) · Module 6 of 9
Hashing in Depth
How hash tables achieve average O(1) lookup, and what happens when two keys land in the same place.
Hash Functions
- A hash function maps a key to an array index — a hash code, then reduced modulo the table size; a good hash function distributes keys uniformly to minimize collisions.
What makes a hash function "good" for use in a hash table?
Solution. It should distribute keys as uniformly as possible across the available array slots, minimizing the chance that different keys map to the same index — a collision.
Collision Resolution: Chaining
- Separate chaining resolves collisions by storing a linked list, or another structure, at each array index, appending colliding elements to that list.
- With chaining, average-case lookup remains close to O(1) as long as the load factor (elements per slot) stays low, but degrades toward O(n) if many keys collide into the same slot.
What happens to a hash table's performance if too many keys collide into the same slot under chaining?
Solution. The chain at that slot grows longer, and looking up a key in that chain approaches O(n) in the worst case, when all keys hash to one slot, rather than the average-case O(1).
Collision Resolution: Open Addressing
- Open addressing resolves collisions by probing for another open slot within the same array — for example, linear probing checks the next slot, and quadratic probing checks slots at increasing quadratic offsets.
- Open addressing requires the table to have empty slots (load factor < 1) and can suffer from "clustering," where consecutive occupied slots make future collisions more likely.
What is a downside of linear probing as a collision resolution strategy?
Solution. It can lead to clustering, where a group of consecutive slots becomes occupied, which increases the likelihood of future collisions landing in and extending that same cluster, degrading performance.
Load Factor & Resizing
- Load factor (α) is the ratio of stored elements to table size; hash tables typically resize, rehashing all elements into a larger table, once the load factor exceeds a threshold (e.g. 0.7) to maintain good average-case performance.
- Like dynamic array resizing, hash table resizing is analyzed with amortized analysis, giving O(1) amortized time per insertion despite occasional expensive rehashing operations.
Why do hash tables resize once their load factor gets too high, and how is the cost of that resize typically analyzed?
Solution. A high load factor means more collisions and slower operations, so resizing (and rehashing all elements into a larger table) keeps operations fast on average; this cost is analyzed with amortized analysis, showing the expensive rehash, spread out over all the insertions since the last resize, still averages to O(1) per insertion.
Check yourself
2 of this module's 5 quiz questions. Pick your answers, then check them in the app, with an explanation for every question.
1. What is the goal of a good hash function?
2. How does separate chaining resolve collisions?