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.
In more detail
Lookup follows the same path and stops when it finds the key or an empty slot. It is simple and cache-friendly, but occupied runs tend to merge into long clusters as the table fills. CPython's dict uses a scrambled probe sequence derived from the hash instead of plain linear steps.
Related terms
- 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.
- clustering — The tendency of occupied slots in a linear-probing table to form long unbroken runs that make new probes longer still.
- tombstone — A marker left in place of deleted data to record that something was deleted, so later lookups, reads or copies treat it correctly.
- empty slot — An open-addressed hash table slot that has never held an entry, which tells a lookup it can stop probing.
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers