Hash Tables
A hash table stores key-value pairs and lets you look up a value by its key in O(1) average time. It's the backbone of Python's dict, JavaScript's Map, Java's HashMap, and C++'s unordered_map. Once you understand how it works, you'll see why it's the most-used data structure in real-world code.
How It Works
The trick is the hash function. A hash function takes a key (a string, a number, anything) and turns it into an integer. You then take that integer modulo the size of an internal array to get an index:
index = hash(key) % bucket_count
You store the value at that index. To look it up later, you hash again and go straight to that slot. No scanning. No comparing keys one by one.
Collisions
Two different keys can hash to the same index — that's a collision. Hash tables handle this in two main ways:
- Chaining: each slot holds a linked list of all the entries that hashed there. Lookup checks the list. With a good hash function, lists stay short.
- Open addressing: if the slot is taken, probe the next one (linear, quadratic, or double-hashed) until you find an empty slot.
When the table gets too full (load factor too high), it resizes — typically doubles in size and rehashes everything. That single resize is O(n), but spread over many inserts it averages to O(1) per insert.
Why Average, Not Worst Case
In the worst case, every key hashes to the same slot and lookup degrades to O(n). Good hash functions and resizing keep this from happening in practice, but it's why we say O(1) average rather than O(1) guaranteed.
When to Reach for a Hash Table
Reach for one whenever you need to:
- Check membership quickly ("have I seen this before?")
- Count things ("how many times does each word appear?")
- Map keys to values ("user id -> profile")
- Find pairs that satisfy a condition (two-sum)
Try It Yourself
- Build a frequency counter that finds the most common word in a paragraph
- Use a hash set to find duplicates in an array in O(n) time
- Implement a tiny hash table from scratch with chaining