Hash Table Collision Resolution with Open Addressing

In any hash table implementation, collisions are fundamentally inevitable. Because a hash function maps an unbounded universe of application keys into a bounded array of size $m$, multiple keys will eventually hash to the exact same slot (by the Pigeonhole Principle).

Two primary paradigms exist for handling these collisions:

1. Separate Chaining: Storing collided elements in an auxiliary external data structure (e.g., a linked list, balanced binary search tree, or dynamic array) attached to each slot.
2. Open Addressing: Storing all elements directly inside the hash table array itself without allocating external auxiliary structures.

Open addressing offers substantial advantages in memory efficiency and cache locality. However, managing collisions within the table requires a deterministic search strategy known as probing, and changes the fundamental implementation mechanics of insertion, lookup, and deletion.

---

The Core Premise of Open Addressing

In separate chaining, every collision incurs memory allocation overhead for pointers and auxiliary nodes. This introduces pointer-chasing and poor CPU cache locality.

Open addressing operates on a straightforward design principle: if the hash table array already has empty slots elsewhere, reuse them rather than allocating external memory.

Open Addressing (All keys stored within array bounds):

Index   Slot State & Value
[0]  -> [ Empty ]
[1]  -> [ Occupied: Key A ]
[2]  -> [ Occupied: Key B ]  <-- Collided with Key A, relocated here
[3]  -> [ Empty ]
[4]  -> [ Occupied: Key C ]

When inserting a key whose primary slot is already occupied, the hash table deterministically searches for the next available slot. Because no keys live outside the array, every key occupies exactly one slot in the table.

---

Probing Functions: The Heart of Open Addressing

To ensure lookups and insertions remain predictable, alternative slot selection cannot be random. It must follow a strict, deterministic sequence. This sequence is governed by a probing function.

A probing function takes the application key $k$ and the attempt number $i$ (where $0 \le i < m$, with $m$ being the table capacity) and outputs an index in the range $[0, m-1]$:

$\text{Index} = P(k, i)$

• Attempt 0 ($i = 0$): The primary slot where the key naturally maps.
• Attempt 1 ($i = 1$): The first fallback slot if the primary slot is occupied.
• Attempt 2 ($i = 2$): The second fallback slot if Attempt 1 is also occupied.
• Attempt $m - 1$: The final attempt covering the last remaining slot in the table.

flowchart LR
    Key[Key k, Attempt i] --> PF[Probing Function: P k, i]
    PF --> Index[Array Index in range 0 to m-1]
    Index --> Check{Slot Occupied?}
    Check -- Yes --> Inc[Increment i = i + 1]
    Inc --> PF
    Check -- No --> Place[Store Key]

Requirements for an Effective Probing Function

A valid probing function must generate a complete permutation of all indices from $0$ to $m - 1$ for any given key as $i$ ranges from $0$ to $m - 1$.

If the sequence does not form a complete permutation, cycles may occur that skip open slots, causing insertions to fail prematurely even when empty slots remain in the table.

While the sequence of evaluated indices must be deterministic for a specific key, different keys should ideally yield distinct probing sequences to minimize clustering.

---

Algorithmic Operations under Open Addressing

1. Insertion (Add)

To insert a new key $k$:

1. Initialize attempt counter $i = 0$.
2. Compute index = $P(k, i)$.
3. Check the slot at index:
   • If the slot is empty (or marked as deleted), write the key to this slot and terminate.
   • If the slot contains the identical key, update the value and terminate.
   • If the slot is occupied by a different key, increment $i \leftarrow i + 1$.
4. Repeat steps 2–3 until an empty slot is found or $i = m$.
5. If $i = m$, the hash table is completely full and requires resizing or eviction.

2. Retrieval (Lookup)

Lookup mirrors the insertion path:

1. Initialize attempt counter $i = 0$.
2. Compute index = $P(k, i)$.
3. Inspect the slot at index:
   • Match: If the slot holds key $k$, return the entry.
   • Empty Slot: If the slot has never been occupied, stop immediately. The key does not exist.
   • Occupied by another key (or marked Deleted): Increment $i \leftarrow i + 1$ and continue probing.
4. Repeat until the key is found, an empty slot is reached, or $i = m$.

Why Lookup Stops at an Empty Slot

Because open addressing places keys deterministically along the probing sequence without leaving unassigned gaps, hitting an empty slot proves that no subsequent insertion for key $k$ could have probed past this position. If the key had been inserted, it would have claimed this exact empty slot.

Lookup Termination States

A lookup operation terminates under one of three conditions:

1. Found: Slot contains key $k$.
2. Definitive Miss: An empty slot is encountered.
3. Table Exhaustion: $i = m$ attempts have been evaluated without finding the key or an empty slot.

---

The Deletion Dilemma: Hard Delete vs. Soft Delete

A naive implementation of delete(k) might clear the slot, setting its state back to EMPTY. Doing so breaks the lookup invariant for other keys that collided on that same sequence.

The Broken Invariant Walkthrough

Consider three keys ($k_1, k_2, k_3$) that all hash to index $5$ via $P(k, 0)$:

1. Insert $k_1$: Placed at index $5$ ($i = 0$).
2. Insert $k_2$: Index $5$ is occupied $\rightarrow$ Probes to index $7$ ($i = 1$). Placed at index $7$.
3. Insert $k_3$: Index $5$ and $7$ are occupied $\rightarrow$ Probes to index $2$ ($i = 2$). Placed at index $2$.

Now, perform a hard delete of $k_2$ by setting index $7$ to EMPTY:

Index:   [ 2 ]         ...      [ 5 ]         ...      [ 7 ]
State:   Occupied              Occupied               EMPTY
Value:   k3                    k1                     (Cleared!)

Next, perform a lookup for $k_3$:

• Probe 0 ($i = 0$): Evaluates index $5$. Holds $k_1$ (collision, continue).
• Probe 1 ($i = 1$): Evaluates index $7$. Finds EMPTY.
• Failure: The lookup logic halts and reports that $k_3$ does not exist, even though $k_3$ is present at index $2$.

sequenceDiagram
    autonumber
    participant Client
    participant Table as Hash Table Slot Array
    Client->>Table: Delete k2 (Hard Delete: Slot 7 -> EMPTY)
    Client->>Table: Lookup k3
    Table->>Table: Probe i=0: Slot 5 contains k1 (Mismatch)
    Table->>Table: Probe i=1: Slot 7 is EMPTY
    Note over Table: Lookup halts immediately at EMPTY slot!
    Table-->>Client: Key k3 Not Found (False Negative!)

The Solution: Soft Deletes with Tombstones

To preserve search chain continuity, open addressing relies on tombstones (soft deletion). A slot must support three distinct states:

1. EMPTY: The slot has never held a key.
2. OCCUPIED: The slot currently holds an active key-value pair.
3. DELETED (Tombstone): The slot previously held a key that has since been removed.

Slot State Machine:

       +-------------- Insert ----------------+
       |                                      |
       v                                      |
  [ EMPTY ] --- Insert ---> [ OCCUPIED ] -----+
                               |              ^
                             Delete         Insert
                               |              |
                               v              |
                          [ DELETED ] --------+

Operational Rules with Tombstones

• Lookup: Continues probing past DELETED slots just as it would past OCCUPIED slots. It only halts when encountering an EMPTY slot or finding the target key.
• Insert: Can safely reuse DELETED slots to place new keys, preventing unnecessary table growth.

---

Architectural Trade-offs and Constraints

Attribute	Separate Chaining	Open Addressing
Auxiliary Storage	Required (pointers, linked list / tree nodes)	None (data stored inline in array)
Cache Locality	Poor (pointer-chasing across heap memory)	High (sequential or localized array accesses)
Max Load Factor ($\alpha = N/M$)	Can exceed $1.0$ (chains grow arbitrarily)	Strictly bounded: $\alpha < 1.0$
Performance Degradation	Degrades gracefully ($O(1 + \alpha)$)	Degrades sharply as $\alpha \to 1.0$
Deletion Complexity	Simple node unlinking	Requires tombstones / soft-delete markers

Load Factor Boundedness

The most critical limitation of open addressing is capacity. In separate chaining, the table can accommodate more elements than its total slot count ($N > M$). In open addressing, the maximum number of elements is strictly upper-bounded by the table capacity ($N \le M$).

As the load factor approaches $1.0$, empty slots become rare. Probe sequences lengthen significantly, causing both insertion and lookup performance to degrade from $O(1)$ toward $O(M)$ linear scans. Consequently, open-addressed hash tables require proactive resizing and rehashing (typically when the load factor crosses $0.6$ to $0.75$) to maintain optimal performance.