17 of 32 · 6 min
Hash tables, and the trick from page one
Page one turned four minutes into an instant with one line. This is what that line did.
A hash table stores key and value pairs and finds a key in O(1) average, whatever the size.
How
A hash function turns a key into a number, and that number is an index:
hash("priya") = 8823714 -> 8823714 % 16 = 2 -> bucket 2No search. Compute where it should be, and look there.
Collisions
Two keys can land in the same bucket. They must, in fact: there are more possible keys than buckets.
Chaining keeps a list in each bucket and walks it. Open addressing puts the item in the next free slot instead.
Either way, the cost depends on how full the table is. The load factor is items divided by buckets, and when it passes about 0.75 the table doubles and rehashes everything. That resize is O(n), and like the array's doubling it averages out to constant.
Why average and not worst
If every key collides, a lookup walks a list of n items: O(n). That is not theoretical. It is a real denial of service against a web server, where an attacker sends keys chosen to collide, and it is why real hash functions are randomly seeded per process.
| Operation | Average | Worst |
|---|---|---|
| Insert | O(1) | O(n) |
| Lookup | O(1) | O(n) |
| Delete | O(1) | O(n) |
What you give up
Order. A hash table has none. Python dictionaries have preserved insertion order since 3.7, which is a property of that implementation and not of hash tables.
Keys must be hashable, meaning immutable. A list cannot be a dictionary key; a tuple can. That is the reason, and it is not arbitrary: a key that changed after insertion would be in the wrong bucket and unfindable.