Everything in one array
With open addressing, every entry lives directly in the bucket array; there are no separate lists. When a key hashes to an occupied slot, the table probes a sequence of other slots until it finds a free one.
Probing strategies
The probe sequence decides where to look next:
- Linear probing checks the next slot, then the next, wrapping around.
- Quadratic probing jumps by growing offsets to spread entries out.
- Double hashing uses a second hash function to set the step size.
Lookup follows the same sequence, comparing keys, and stops when it finds the key or hits an empty slot.
The deletion trap
Deletion is subtle. Simply emptying a slot can break probe chains, making a later key unreachable because the search stops at the new gap. The fix is a tombstone, a special marker meaning deleted but keep probing. Probes pass over tombstones, and inserts may reuse them.
Open addressing is cache friendly because everything is contiguous, but it degrades sharply as the load factor approaches one, so it must resize earlier than chaining.
Key idea
Open addressing stores entries in the array itself and probes a slot sequence to resolve collisions, using tombstones on deletion and resizing before the table fills.