The Core Idea
Turning Keys Into Array Indices
A hash table stores key-value pairs by running each key through a hash function — a function that converts the key into a number — and using that number (typically reduced modulo the table's size) as the index into an underlying array where the value gets stored. Looking up a key later means hashing it the same way and jumping directly to that same index — no scanning, no comparing against every stored item.
This is what gives hash tables their famous average O(1) lookup, insertion, and deletion — dramatically faster than a linked list's O(n) search or even a balanced BST's O(log n), for the specific task of 'look up value by exact key.' The trade-off is that hash tables don't preserve any ordering among keys, unlike a BST's naturally sorted structure.
💡 Memory Trick
Think of a hash table as a coat check at a theater: instead of searching every rack for your coat, the attendant runs your ticket number through a simple rule (say, 'shelf = ticket number mod 50') and walks directly to that shelf. Two different ticket numbers might occasionally land on the same shelf — a collision — which is why the shelf might hold a small rack of a few coats rather than exactly one, but you almost never need to search through more than a couple of coats to find yours.
The Key Challenge
Collisions and How to Handle Them
1
What a Collision Is
Two different keys can hash to the exact same index — this is unavoidable in general, since there are usually far more possible keys than array slots. A good hash function spreads keys evenly across indices, but it can never fully eliminate the possibility of collisions.
2
Chaining
Each array index holds a small secondary structure (commonly a linked list) of all key-value pairs that hashed to that index. On lookup, you hash to the right index, then scan that short chain (usually just one or two items) for the matching key.
Example: if 'apple' and 'grape' both hash to index 7, index 7 holds a tiny linked list containing both entries.
3
Open Addressing
Instead of a secondary structure, if the computed index is already occupied by a different key, the table probes forward (using some defined rule) to find the next open slot, and stores the entry there instead. Lookup follows the same probing sequence to relocate the entry.
4
Load Factor and Resizing
Load factor is the ratio of stored entries to total array slots. As it climbs too high, collisions become more frequent and performance degrades toward O(n). Hash tables resize (typically doubling capacity, then rehashing every existing entry into the new larger array) once the load factor crosses a threshold, to keep collisions rare and performance close to O(1).
Why 'Average' O(1), Not Guaranteed
The Worst Case Still Exists
Hash table operations are described as average-case O(1) rather than worst-case O(1) because a poorly designed hash function (or deliberately crafted malicious input) could send many keys to the same index, forcing long chains or long probe sequences — degrading toward O(n) in the worst case. This is why cryptographically strong or well-distributed hash functions matter for security-sensitive applications, where an attacker who can predict collisions could deliberately degrade performance.
In practice, with a reasonably good hash function and a load factor kept below a sensible threshold (often around 0.7), collisions stay rare enough that real-world performance is consistently close to O(1), which is why hash tables back most language's built-in dictionary/map/object types.
🖥️ Applied Scenario
You're building a system to look up a user's account details instantly by their username, across a database of 10 million users.
1
You consider a sorted array with binary search — O(log n), meaning roughly 24 comparisons per lookup — functional, but not as fast as it could be.
2
You choose a hash table instead, hashing each username to an index, achieving average O(1) lookup — a single hash computation and array access, regardless of how many millions of users exist.
3
You monitor the load factor as the user base grows, triggering a resize (doubling the table and rehashing every entry) once it crosses your chosen threshold, to keep collision chains short.
4
Conclusion: for pure 'look up by exact key' access, the hash table's average O(1) beats even the BST's and sorted array's O(log n), at the cost of losing any sorted ordering among usernames.
📌 Exam Application
Exam questions often ask you to trace through inserting several keys into a small hash table using a specified hash function, showing where collisions occur and how they're resolved (via chaining or open addressing). You may also be asked to explain why hash table operations are 'average' O(1) rather than guaranteed O(1), and to describe what triggers a resize and why doubling the table size (rather than a fixed increment) keeps the amortized cost of resizing low.
⚠️ Most Common Hash Tables Mistakes
The most common mistake is assuming hash table lookup is always O(1) without qualification — a poor hash function or adversarial input can force many keys into the same bucket, degrading to O(n) in the worst case, an important nuance exam questions frequently probe. Another frequent error is confusing a hash table with a BST in terms of ordering — hash tables provide no ordering guarantee among keys at all, so if you need sorted iteration or range queries, a BST (or a sorted structure) is the correct choice, not a hash table.
✓ Quick Self-Test
Can you explain, using the coat-check analogy, what a hash collision is and how chaining resolves it? Can you explain why a hash table's load factor matters, and what happens internally when a resize is triggered?
Next Lesson
Graphs and Graph Traversal
→
← All Data Structures Lessons