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

Taught in

References