Coarse Open Addressing

Open addressing stores entries directly in the table and searches for alternative slots in case of collisions (linear, quadratic, double hashing). Deleting requires placeholders (tombstones).

Good locality, but sensitive to high load factors.

High-performance maps, some DB hash indices, when pointer chasing from chaining is too expensive. More probing logic, better cache locality with good load.

Depth

In open addressing, all entries are stored directly in the table array. If the starting position is occupied, the search follows a predetermined probing sequence. Insertion and lookup must use exactly the same sequence, otherwise existing keys may be overlooked.

During deletion, a special marker is often set. A truly empty space indicates that a key cannot continue along this search path. However, a deletion marker allows for the continuation of probing and can be reused later during an insertion.

Difficulty levels

1. Simulate linear probing for a short table.
2. Semantically distinguish between empty slots and deletion markers.
3. Explain clustering and its impact on access time.

Pitfalls

A nearly full table can generate very long probing sequences. If the search fails after the first deleted slot, keys placed further back remain invisible.