You already know that reaching any address in memory costs the same. A hash table is what happens when you use that to look things up by name instead of by position.
The trick#
Finding a name in an unsorted array of a million names means checking up to a million of them.
A hash table asks a different question. Rather than searching for where the value is, it computes where the value should be.
- Run the key through a hash function, which turns anything into a number.
- Squeeze that number into the range of your array with a remainder:
hash % size. - That is the slot. Look there.
"banana" -> hash 8842301 -> 8842301 % 8 = 5 -> slot 5
No search. One computation, one jump. Constant time, whatever the size.
The problem, and it is unavoidable#
Two different keys can produce the same slot. "banana" and "cherry" might both land on 5. This is a collision, and it is not a bug you can design away: with more possible keys than slots, some must share. That is just counting.
So the real design question is not how to avoid collisions, it is what to do about them.
Chaining#
Each slot holds a small list of everything that landed there.
slot 3: -> ("apple", 1)
slot 5: -> ("banana", 2) -> ("cherry", 7)
slot 6: -> ("date", 4)
To look up "cherry": hash to slot 5, then walk the short list comparing keys.
Two keys colliding does not mean they are equal. The hash gets you to the right shelf; the key comparison finds the right book. Skipping that comparison is a real and nasty bug.
That "small list" is usually a linked list, which gets a lesson of its own later. Nothing here depends on how it is built: all a bucket has to do is hold a handful of entries you can walk through.
Open addressing#
The other approach keeps everything in one flat array. If your slot is taken, try the next one, and keep going until you find a space.
Faster in practice, because everything stays next to each other in memory. Fiddlier to delete from: removing a value outright can break the chain of probes that leads to something else, so deleted slots get marked as tombstones rather than emptied.
Why the cost is only "on average"#
Average case O(1). Keys spread evenly, chains stay tiny, one hop.
Worst case O(n). If every key hashes to the same slot, the table is one long list and you have a linear search wearing a hash table costume.
Good hash functions make the worst case unlikely with ordinary data. But "unlikely with ordinary data" is not "impossible", and where the keys come from an attacker who can choose them, it has been used as a denial of service attack. Real libraries defend against it by seeding the hash randomly at startup.
The load factor#
Slots filling up means longer chains and more probing. So tables track the load factor, which is entries divided by slots. Cross a threshold, typically around 0.75, and the table allocates a bigger array and rehashes every existing entry into it, because every slot number depends on the array size.
That resize is O(n), and like a growing array it amortises to nothing across the insertions that caused it.
What it cannot do#
A hash table throws order away. The slot for a key is effectively random, so you cannot ask for the smallest key, or everything between two values, or the entries in sorted order. If you need those, you want a sorted structure or a tree, and you will pay O(log n) for lookups instead.
What makes a key usable#
A key must have two things: a hash that is the same every time for equal keys, and a way of testing equality. Two equal keys must hash the same, or they land in different slots and your table holds the same key twice.
This is why keys are usually immutable. Change a key after inserting it and its hash changes, and the entry is now sitting in the wrong slot, unreachable.
Common mistakes#
- Treating a collision as a match without comparing the keys.
- Using something mutable as a key, then mutating it.
- Expecting any order from iteration.
- Reaching for a hash table when the keys are a small range of integers, where a plain array indexed by the key is simpler and faster.