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

Taught in

References