All entries live in the array
Open addressing is a second way to build a hash table. Instead of lists hanging off buckets, every entry sits directly in the array, one per slot. When a key hashes to a slot that is already taken, the table probes a sequence of other slots until it finds an empty one. The same probe sequence is replayed during lookup.
Common probing strategies
The rule for choosing the next slot defines the scheme.
- Linear probing checks the next slot, then the next, wrapping around. It is cache friendly but causes long runs called clustering.
- Quadratic probing jumps by growing offsets to spread entries and reduce clustering.
- Double hashing uses a second hash to set the step size, scattering probes well.
The deletion problem
Deletion is tricky. If you simply empty a slot in the middle of a probe sequence, a later search may stop early and miss a key. The fix is a tombstone, a marker meaning the slot was occupied so searches keep probing while insertions may reuse it. Open addressing needs a load factor well below one, so it resizes earlier than chaining does.
Key idea
Open addressing keeps all entries in the array and resolves collisions by probing nearby slots, using linear, quadratic, or double hashing, and it relies on tombstones for deletion and a low load factor for speed.