empty slot
An open-addressed hash table slot that has never held an entry, which tells a lookup it can stop probing.
In more detail
Reaching an empty slot proves the key is absent, because an insert would have placed it there or earlier. That is different from a tombstone, which marks a deleted entry and must be probed past. The course marks empty slots with None and tombstones with a unique sentinel object.
Related terms
- tombstone — A marker left in place of deleted data to record that something was deleted, so later lookups, reads or copies treat it correctly.
- 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.
- sentinel value — A special value that can never be real data, used to mark a condition such as "empty", "deleted" or "end".
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers