Hash Tables and Collisions
A dictionary lookup feels instant, yet two different keys can land in the same bucket. Insert keys, watch the hash pick a slot, and see what the table does when slots collide and when it runs out of room.
Hash Tables and Collisions
Looking a key up in a dictionary feels instant because a hash function turns the key into a number and that number points straight at a bucket, no scanning required. The catch is that many keys map to few buckets, so two different keys can pick the same one. What the table does at that moment, and what it does when the buckets get crowded, is the whole story behind average constant time.
Load factor is 0.00 (n/m). The next insert that pushes it past 0.75 doubles the table and rehashes everything.
Why lookup is usually O(1). The hash turns a key into a bucket index in one step, so the table jumps to a slot instead of scanning. With a good hash and a load factor kept low, each bucket holds only a key or two, so the scan after the jump is tiny and constant on average.
Why collisions are unavoidable. There are far more possible keys than buckets, so by the pigeonhole principle some keys must share a bucket. Even well short of full, the birthday paradox makes the first collision arrive surprisingly early. The question was never whether collisions happen, only how the table absorbs them.
Chaining versus probing. Chaining hangs a list off each bucket, so colliding keys cost a short list walk and the table never runs out of room. Open addressing keeps every key in the array and probes forward to the next opening, which is cache-friendly but forms clusters and cannot exceed m keys, so it leans harder on resizing.
Why resize, and why it is still O(1) amortized. As the load factor climbs, chains lengthen and probe clusters grow, so the table doubles m and rehashes every key to spread them out again. That rehash is O(n), but it happens rarely enough that spread across all the cheap inserts the average stays constant.
How it degrades to O(n). Switch to the weak hash or load the colliders and watch every key crowd into one bucket. Now a lookup walks the entire chain or probes the whole cluster, and the table behaves like an unsorted list. A bad hash or a load factor left too high erases the constant-time guarantee.