clustering
The tendency of occupied slots in a linear-probing table to form long unbroken runs that make new probes longer still.
In more detail
Any key hashing into a cluster must walk to its end, and then extends it by one, so clusters feed themselves. Clustering is why open-addressed tables resize at a moderate load factor. Probe sequences that jump around, as in CPython, reduce it.
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.
- load factor — The number of items stored in a hash table divided by the number of slots, a measure of how full it is.
- 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.
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers