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

Taught in

References