open addressing
A way of resolving hash collisions in which all entries live in one array and a colliding key probes forward to another free slot.
In more detail
Keeping everything in one array is cache-friendly and avoids per-entry pointers. The table must stay well below full, because probe sequences grow long as it fills. Deletion needs tombstones so that later lookups do not stop too early. Python's dict and set use open addressing.
Related terms
- linear probing — An open-addressing rule: if a key's slot is taken, try the next slot, then the next, wrapping around, until a free one is found.
- tombstone — A marker left in place of deleted data to record that something was deleted, so later lookups, reads or copies treat it correctly.
- load factor — The number of items stored in a hash table divided by the number of slots, a measure of how full it is.
- chaining — A way of resolving hash collisions in which each slot holds a small list of all the key-value pairs that hashed there.
- clustering — The tendency of occupied slots in a linear-probing table to form long unbroken runs that make new probes longer still.
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Python Dicts And Sets Under The Hood — Algorithms & Data Structures for Working Engineers