← Back to the hash tables page
Open Addressing
No chains — collisions probe for the next free slot in the same array. One allocation, cache-friendly, but deletion needs tombstones.
What to know
- Linear probing scans forward; clustering is the enemy.
- Robin Hood hashing steals slots from "rich" entries to flatten probe lengths.
- Must resize before load factor gets high (~0.7) or probes explode.
In the wild: Python dict, Rust HashMap (SwissTable), Go map internals.
Algorithms to reach for
Linear / quadratic probing
O(1) avgFind next open slot after collision
Robin Hood insertion
O(1) avgMinimize variance of probe distances
Tombstone deletion
O(1) avgDelete without breaking probe chains
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.