Collision Handling — Open Addressing

We've now explored two fundamentally different approaches to handling hash collisions: chaining (separate chaining with linked lists) and open addressing (probing within the table itself). Both achieve the goal of resolving collisions, but they embody different philosophies and excel in different scenarios.

This page provides a comprehensive comparison across every dimension that matters in practice: memory usage, cache performance, deletion complexity, worst-case behavior, and implementation considerations. By the end, you'll understand not just how each approach works, but when to choose each one — and why production systems make the choices they do.

Before diving into metrics, let's understand the core philosophical difference between these approaches:

Chaining says: "When collisions happen, store multiple elements at each bucket using auxiliary data structures. The table is an array of containers."

Open addressing says: "The table is THE data structure. When collisions happen, find another slot within the table itself. No auxiliary structures needed."

These philosophical differences cascade into practical implications for every operation and design decision. Let's examine each dimension systematically.

Memory efficiency depends on load factor, key/value sizes, and platform-specific overheads. Let's break this down precisely.

Chaining Memory Model:

For a table with m buckets and n elements:

Table array:     m × sizeof(pointer) = 8m bytes (64-bit)
Linked list nodes: n × (sizeof(key) + sizeof(value) + sizeof(next_ptr))
                 = n × (K + V + 8) bytes

Total: 8m + n(K + V + 8) bytes

The pointer overhead is significant: each node carries an 8-byte next pointer, and each bucket carries a head pointer.

Open Addressing Memory Model:

For a table with m slots and n elements:

Table array: m × (sizeof(key) + sizeof(value) + sizeof(metadata))
           = m × (K + V + 1) bytes  [1 byte for empty/tombstone state]

Total: m(K + V + 1) bytes

No per-element pointer overhead, but empty slots consume full key+value space.

Comparative Analysis:

Let's compare for realistic scenarios (K=8 bytes, V=8 bytes):

Chaining:

• Per element: 8 + 8 + 8 = 24 bytes
• Per bucket (empty): 8 bytes
• Overhead ratio at α=1: 8/24 = 33% (just pointers)

Open Addressing:

• Per slot: 8 + 8 + 1 = 17 bytes
• At α=0.5: n elements use 2n × 17 = 34 bytes per element
• At α=0.75: n elements use 1.33n × 17 = 22.7 bytes per element

Memory Allocation Considerations:

Beyond raw byte counts, memory allocation patterns differ significantly:

Chaining:

• Requires dynamic allocation for each insert (new list node)
• Allocation overhead (typically 8-24 bytes per allocation for metadata)
• Fragmented memory: nodes scattered throughout heap
• Can trigger garbage collection pressure (in GC languages)

Open Addressing:

• Single contiguous allocation (the table array)
• No per-insert allocation (until resize)
• Predictable memory footprint
• Resize requires one large reallocation

For embedded systems or real-time applications, open addressing's predictable allocation is often decisive.

Modern CPUs are so fast that memory access is often the bottleneck. Cache behavior can outweigh algorithmic complexity for hash tables. This is where open addressing — particularly linear probing — shines.

Understanding Cache Behavior:

CPU caches are organized in cache lines (typically 64 bytes on modern x86/ARM). When you access a memory location, the entire cache line is loaded. Accessing nearby locations within the same cache line is essentially free.

Chaining memory access pattern:

Search for key K:
1. Load table[hash(K)]           → Cache miss (load bucket pointer)
2. Load head→key                  → Cache miss (node elsewhere in heap)
3. Compare key                    → Likely cache miss (key may be pointer)
4. If mismatch, load head→next   → Cache miss (next node)
5. Repeat until found or end

Each pointer chase is likely a cache miss. For a chain of length L, expect ~L cache misses.

Open addressing (linear probing) access pattern:

Search for key K:
1. Load table[hash(K)]           → Cache miss (load first slot)
2. Compare key                   → Cache hit (key in same cache line)
3. If mismatch, check table[hash(K)+1] → Cache hit! (same cache line)
4. Continue until found/empty   → Many consecutive hits

With 64-byte cache lines and 17-byte slots, we get ~3-4 slots per cache line. Linear probing clusters accesses spatially, achieving high cache hit rates.

SIMD and Modern Optimizations:

Modern hash table implementations exploit SIMD instructions to process multiple slots in parallel:

// Swiss Table approach
1. Load 16 metadata bytes (one cache line)
2. Use SIMD to compare all 16 slots' hash fragments simultaneously
3. Check matches with full key comparison

This turns 16 sequential probes into 1-2 cache accesses plus a few CPU cycles. Libraries like Google's Abseil and Facebook's F14 achieve remarkable performance using these techniques — all built on open addressing foundations.

Let's compare the theoretical and practical complexity of core operations:

*Chaining insert is O(1) if we insert at head. O(n) if we check for duplicates or insert at tail.

Key observations:

1. Average case is similar: Both achieve O(1) average for well-distributed keys

2. Load factor sensitivity differs: Open addressing degrades rapidly past α ≈ 0.7; chaining handles α > 1 gracefully

3. Worst case is identical: Both degrade to O(n) under pathological hash collisions

4. Iteration differs: Chaining must visit empty buckets; open addressing visits all slots but often no pointer chasing

Deletion Complexity Deep Dive:

Deletion deserves special attention as it's the operation where strategies differ most:

Chaining deletion:

• Find element: O(chain length)
• Remove from list: O(1) with proper pointers
• No impact on other elements
• No tombstones, no cleanup needed

Open addressing deletion:

• Find element: O(probe length)
• Mark as tombstone: O(1)
• OR shift subsequent elements: O(cluster size)
• May need periodic cleanup/rehash
• Tombstones degrade future operations

For workloads with frequent deletions, chaining's simpler model is often preferable.

Load factor tolerance is perhaps the starkest difference between strategies:

Chaining:

• α can exceed 1 (more elements than buckets)
• Performance degrades gradually: O(1 + α)
• Typical resize threshold: α = 2.0 to 3.0
• Works fine with α = 10+ (just slower)

Open Addressing:

• α cannot exceed 1 (one element per slot maximum)
• Performance degrades rapidly: O(1/(1-α))
• Typical resize threshold: α = 0.5 to 0.75
• Becomes unusable past α ≈ 0.9

Resize Behavior:

Chaining resize:

• Create new table with more buckets
• For each element in old table, rehash and insert into new
• Old list nodes can be reused (pointer surgery) OR reallocated
• Time: O(n + m_old)
• Memory during resize: old table + new table + possible node allocations

Open addressing resize:

• Create new table (typically 2× size)
• For each non-empty, non-tombstone slot, rehash and insert
• Tombstones are discarded (free cleanup!)
• Time: O(m_old) to scan + O(n) to insert
• Memory during resize: old table + new table (no extra allocations)

Memory Overhead During Resize:

Both strategies need memory for old and new tables simultaneously during resize. For applications with tight memory budgets:

Chaining: Old table = m × 8 bytes, New table = 2m × 8 bytes Total: 24m bytes during resize → 16m after (33% temporary overhead)

Open addressing: Old table = m × S bytes, New table = 2m × S bytes Total: 3mS bytes during resize → 2mS after (50% temporary overhead)

Open addressing's temporary memory spike is proportionally larger because its per-slot overhead is higher.

Let's synthesize everything into a practical decision framework:

Choose Chaining When:

1. Deletion-heavy workloads: Chaining deletion is cleaner, no tombstones
2. Unpredictable sizing: Load factor > 1 is acceptable
3. Large values: Pointer overhead is small relative to value size
4. Stable, long-lived entries: Allocation overhead amortizes well
5. Need to iterate in insertion order: Easy with doubly-linked lists
6. Simple baseline implementation: Easier to implement correctly
7. Pointer-friendly environment: GC handles memory, pointers are cheap

Choose Open Addressing When:

1. Read-heavy workloads: Cache-friendly searches dominate
2. Memory-constrained systems: No per-element pointer overhead
3. Embedded/real-time: Predictable memory, no dynamic allocation per insert
4. Small key-value pairs: Slot overhead is acceptable
5. High-performance requirements: SIMD optimization opportunities
6. Infrequent deletions: Tombstone management is minimal
7. Known size bounds: Can size table appropriately upfront

Let's see what major systems and languages have chosen:

Notable Trends:

1. Newer implementations favor open addressing: The shift toward cache-optimized, SIMD-friendly designs has made open addressing dominant in high-performance contexts.

2. Hybrid approaches are emerging: Java's HashMap uses chaining but converts long chains to trees. Go uses small buckets (open addressing within bucket) with chaining between buckets.

3. SwissTable is the new standard: Google's SwissTable design (used in Abseil, Rust, and others) combines open addressing with clever metadata encoding for exceptional performance.

4. Chaining persists where simplicity matters: Database systems, older codebases, and applications prioritizing correctness over raw speed often stick with chaining.

We've completed a comprehensive comparison of chaining and open addressing. Let's consolidate the essential insights:

Module Complete:

You've now mastered collision handling with open addressing. You understand the probing strategies (linear, quadratic, double hashing), how search navigates probe sequences, the challenges of deletion and tombstone management, and when to choose open addressing over chaining.

With this knowledge, you can make informed decisions about hash table implementations, understand the tradeoffs in library choices, and reason about hash table performance in your systems.