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

Taught in

References