Collision Handling — Open Addressing

Deletion in open-addressed hash tables presents a fundamental problem that doesn't exist with chaining. In chaining, deleting an element simply removes a node from a linked list — the bucket structure remains intact. In open addressing, deleting an element creates a hole in the probe sequence, potentially severing the connection to elements inserted afterward.

This page confronts the deletion problem head-on. We'll understand why naive deletion breaks the data structure, develop the tombstone (or lazy deletion) solution, analyze its tradeoffs, and explore advanced techniques for managing the complexity tombstones introduce.

Let's start with the intuitive approach: to delete a key, simply mark its slot as empty. This seems reasonable — after all, that's how we'd remove an element from an array. But in open addressing, this intuition leads to catastrophic failure.

The Problem: Severed Probe Chains

Recall the search invariant: when we encounter an empty slot during search, we conclude the key isn't in the table. But if we've deleted an element that was between the initial hash position and the target key, we create a false empty slot that prematurely terminates search.

Step-by-Step Demonstration:

Consider a hash table with linear probing (m = 11). We insert three keys that all hash to index 3:

Step 1: Insert A (h(A) = 3)
[ _ | _ | _ | A | _ | _ | _ | _ | _ | _ | _ ]
  0   1   2   3   4   5   6   7   8   9  10

Step 2: Insert B (h(B) = 3) — collides, probes to 4
[ _ | _ | _ | A | B | _ | _ | _ | _ | _ | _ ]

Step 3: Insert C (h(C) = 3) — collides at 3 and 4, probes to 5
[ _ | _ | _ | A | B | C | _ | _ | _ | _ | _ ]

Now let's naively delete B:

Step 4: Delete B — mark slot 4 as empty
[ _ | _ | _ | A | _ | C | _ | _ | _ | _ | _ ]
                  ^
                  Empty slot created

Now search for C:

Search C (h(C) = 3):
  Probe 0: index 3 → A (not C, continue)
  Probe 1: index 4 → EMPTY
  → Search terminates. C not found!

But C is still in the table at index 5!

The Root Cause:

The problem stems from the dual meaning of 'empty' in naive implementations:

1. Empty = never occupied: No key has ever been placed here
2. Empty = deleted: A key was here but was removed

For search, these two meanings require different actions:

• Never occupied → Stop searching, key not in table
• Deleted → Continue searching, key might be further along

Naive deletion conflates these meanings, causing the search algorithm to stop early when it should continue.

The solution is to introduce a third state for slots: instead of just 'empty' and 'occupied', we add 'deleted' — also known as a tombstone.

The Three Slot States:

How Tombstones Preserve Correctness:

Revisiting our example with tombstones:

After inserting A, B, C:
[ _ | _ | _ | A | B | C | _ | _ | _ | _ | _ ]

Delete B with tombstone (⊗):
[ _ | _ | _ | A | ⊗ | C | _ | _ | _ | _ | _ ]

Search for C:
  Probe 0: index 3 → A (not C, continue)
  Probe 1: index 4 → TOMBSTONE (continue probing!)
  Probe 2: index 5 → C (found!)

The tombstone preserves the probe chain. Search knows to continue past deleted slots, eventually finding C.

Tombstones solve the correctness problem but introduce a new issue: tombstones accumulate over time, degrading performance even when the number of active elements is small.

The Problem:

Consider a hash table that undergoes many insert-delete cycles:

Initial: 100 elements, 0 tombstones
After deleting 50: 50 elements, 50 tombstones
After inserting 50 new: 100 elements, ~50 tombstones (some reused)
After deleting 50 different: 50 elements, ~100 tombstones
... repeat ...

Over time, tombstones accumulate. Even if the table contains only a few active elements, it may be littered with tombstones that slow down every operation.

Impact on Performance:

Tombstones affect performance in multiple ways:

1. Search traversal: Search must probe through tombstones, treating them as occupied slots. A table with 50 elements and 200 tombstones performs as if it had 250 elements for unsuccessful search.

2. Load factor calculation: The 'effective load factor' is (elements + tombstones) / capacity, not just elements / capacity. High tombstone counts effectively reduce capacity.

3. Insertion overhead: Insertion must scan past tombstones to verify key uniqueness, then backtrack to use the first tombstone.

4. Memory waste: Tombstones occupy slots but store no useful data.

Worst-Case Scenario:

Imagine an adversarial usage pattern:

1. Fill table to 70% capacity (70 elements in table of 100)
2. Delete all 70 elements (now: 0 elements, 70 tombstones)
3. Insert 70 new elements (partially reuse tombstones, but many remain)
4. Delete all again
5. Repeat

Without cleanup, tombstones accumulate toward 100%, eventually making every operation O(n). The table is effectively full despite being logically empty.

This workload pattern is common in caches with short-lived entries, session stores, and any system with high churn.

To prevent tombstone accumulation from degrading performance, we need cleanup strategies. The primary approaches are rehashing and lazy cleanup.

Strategy 1: Full Rehash

The most thorough cleanup is to create a new table and reinsert all active elements, discarding tombstones:

def _cleanup_rehash(self):
    """
    Create new table with only active elements.
    Tombstones are discarded.
    """
    old_keys = self.keys
    old_values = self.values
    
    # May resize or keep same capacity
    new_capacity = self._calculate_new_capacity()
    self.keys = [None] * new_capacity
    self.values = [None] * new_capacity
    self.capacity = new_capacity
    self.size = 0
    self.tombstone_count = 0  # Reset!
    
    # Reinsert only active elements
    for i in range(len(old_keys)):
        if old_keys[i] is not None and old_keys[i] is not self.TOMBSTONE:
            self.insert(old_keys[i], old_values[i])

Pros: Completely eliminates tombstones, restores optimal performance Cons: O(n) operation, can cause latency spikes

Strategy 2: Resize Triggers Cleanup

Combine resize with cleanup — whenever we resize (up or down), we get a free tombstone purge:

def _check_load_factor(self):
    """
    Check if resize is needed. Consider both elements and tombstones.
    """
    effective_load = (self.size + self.tombstone_count) / self.capacity
    actual_load = self.size / self.capacity
    
    if effective_load > 0.7:
        if actual_load > 0.5:
            # Table genuinely full, grow it
            self._resize(self.capacity * 2)
        else:
            # Many tombstones, just cleanup (rehash at same size)
            self._resize(self.capacity)

This piggybacks cleanup on resize, avoiding additional operations.

Strategy 3: Periodic Cleanup Based on Tombstone Ratio

Trigger cleanup when tombstones exceed a threshold relative to active elements:

def _maybe_cleanup(self):
    """
    Trigger cleanup if tombstones are excessive.
    """
    if self.size == 0:
        if self.tombstone_count > self.capacity // 4:
            self._cleanup_rehash()  # Table is mostly tombstones
    else:
        tombstone_ratio = self.tombstone_count / self.size
        if tombstone_ratio > 2.0:  # More than 2 tombstones per element
            self._cleanup_rehash()

# Call after each delete
def delete(self, key) -> bool:
    result = self._delete_internal(key)
    if result:
        self._maybe_cleanup()
    return result

This bounds the tombstone-to-element ratio, preventing unbounded accumulation.

Strategy 4: Incremental Cleanup

Spread cleanup work across multiple operations to avoid latency spikes:

def _incremental_cleanup(self, probes_per_op: int = 5):
    """
    Clean up a few tombstones each operation.
    Spread O(n) work over many operations.
    """
    if self.tombstone_count == 0:
        return
    
    checked = 0
    index = self._cleanup_cursor
    
    while checked < probes_per_op:
        if self._is_tombstone(index):
            # Try to fill this tombstone from later in its chain
            self._try_fill_tombstone(index)
        index = (index + 1) % self.capacity
        checked += 1
    
    self._cleanup_cursor = index

This 'housekeeping' approach maintains performance without any single expensive operation.

Tombstones aren't the only way to handle deletion. Several alternative approaches avoid tombstones entirely at the cost of more complex delete operations.

Alternative 1: Backward Shift Deletion

After removing an element, shift subsequent elements backward to fill the gap — but only elements that belong in this probe chain:

def delete_backward_shift(self, key) -> bool:
    """
    Delete key by shifting elements backward.
    No tombstones created.
    """
    # Find the key
    delete_index = None
    for index in self._probe_sequence(key):
        if self._is_empty(index):
            return False  # Not found
        if self.keys[index] == key:
            delete_index = index
            break
    
    if delete_index is None:
        return False
    
    # Now shift elements backward
    current = delete_index
    while True:
        next_idx = (current + 1) % self.capacity
        
        if self._is_empty(next_idx):
            break  # End of chain
        
        # Check if element at next_idx can move backward
        element_ideal = self._hash(self.keys[next_idx])
        
        # Can move if current slot is on element's probe path
        if self._is_between(element_ideal, current, next_idx):
            self.keys[current] = self.keys[next_idx]
            self.values[current] = self.values[next_idx]
            current = next_idx
        else:
            break
    
    # Clear the final slot
    self.keys[current] = None
    self.values[current] = None
    self.size -= 1
    return True

Pros: No tombstones, no accumulation problem Cons: Delete is O(cluster size), complex implementation, cache-unfriendly

Alternative 2: Robin Hood Deletion

Robin Hood hashing tracks the 'probe distance' for each element. During deletion, we can shift elements more intelligently:

def delete_robin_hood(self, key) -> bool:
    """
    Robin Hood deletion: shift elements with positive probe distance.
    """
    delete_index = self._find(key)
    if delete_index is None:
        return False
    
    current = delete_index
    
    while True:
        next_idx = (current + 1) % self.capacity
        
        if self._is_empty(next_idx):
            break
        
        # Elements in Robin Hood have stored probe distances
        if self.probe_distances[next_idx] == 0:
            break  # Element is at ideal position, can't shift
        
        # Move element backward and decrease its probe distance
        self.keys[current] = self.keys[next_idx]
        self.values[current] = self.values[next_idx]
        self.probe_distances[current] = self.probe_distances[next_idx] - 1
        
        current = next_idx
    
    # Clear final slot
    self.keys[current] = None
    self.probe_distances[current] = 0
    self.size -= 1
    return True

Robin Hood's probe distance tracking makes the shift logic simpler and more efficient.

Alternative 3: No Deletion Allowed

The simplest approach: don't support deletion at all. This sounds extreme but is valid for:

• Write-once caches: Data is inserted and read, never deleted
• Append-only logs: Events are added but never removed
• Temporary tables: Built for one computation, then discarded

Many high-performance systems use insert-only hash tables when the workload permits.

Let's compare the deletion strategies across key dimensions:

Decision Framework:

We've thoroughly explored the deletion challenge unique to open addressing. Let's consolidate the essential insights:

What's next:

We've now covered the three core operations for open addressing: insertion, search, and deletion. In the final page of this module, we'll compare open addressing with chaining — examining when each collision resolution strategy excels, their performance tradeoffs, and guidance for choosing between them in practice.