Hash Map Open Addressing vs Chaining: Implementation Differences in hello-algo

Open addressing uses linear probing with tombstone markers in a flat pointer array ([]*pair), while separate chaining stores collisions in dynamic bucket slices ([][]pair), resulting in fundamentally different collision resolution, deletion strategies, and memory layouts.

The krahets/hello-algo repository provides educational Go implementations that demonstrate these classic hash collision resolution strategies side-by-side. Both implementations share the same pair struct and modulo-based hash function, but diverge dramatically in how they handle bucket storage, probing, and entry removal. This article examines the concrete source code differences between these two approaches.

Core Data Structures

The structural foundation differs immediately in how buckets are allocated and typed.

Open addressing uses a flat array of pointers where each slot holds either a key-value pair, nil, or a special tombstone marker:

// zh-hant/codes/go/chapter_hashing/hash_map_open_addressing.go (lines 13-19)
type hashMapOpenAddressing struct {
    size        int
    capacity    int
    loadThres   float64
    extendRatio int
    buckets     []*pair  // Array of pointers
    TOMBSTONE   *pair    // Sentinel for deleted entries
}

Separate chaining allocates an array of slices, where each bucket is itself a dynamic list capable of holding multiple pairs:

// zh-hant/codes/go/chapter_hashing/hash_map_chaining.go (lines 13-20)
type hashMapChaining struct {
    size        int
    capacity    int
    loadThres   float64
    extendRatio int
    buckets     [][]pair  // Array of slices (bucket lists)
}

The open addressing implementation initializes a TOMBSTONE sentinel (lines 28-30) to mark deleted slots without breaking probe sequences, while chaining requires no such marker because deletions simply remove elements from slice indices.

Collision Resolution Mechanisms

Linear Probing in Open Addressing

When a collision occurs in the open addressing implementation, the findBucket method (lines 44-66) performs linear probing by walking forward until finding an empty slot, tombstone, or matching key:

1. Compute initial index: index := h.hashFunc(key)
2. While bucket is occupied (h.buckets[index] != nil), check for key match
3. Remember first tombstone encountered for potential reuse
4. Advance via modulo arithmetic: index = (index + 1) % h.capacity (line 60)

This probing sequence ensures clustered storage where colliding elements occupy nearby indices in the same array.

Bucket Lists in Separate Chaining

The chaining implementation (lines 50-56) treats each bucket as an independent list, iterating through the slice to find matches:

// From hash_map_chaining.go lines 50-56
bucket := m.buckets[idx]
for _, p := range bucket {
    if p.key == key {
        return p.val
    }
}

Colliding keys coexist in the same bucket slice without displacing other entries, eliminating the need for probing beyond the initial hash index.

Insertion and Update Operations

Open addressing insertion follows a "find or place" pattern using the probe sequence (lines 80-88):

• Check load factor threshold (> 2/3) and call extend() if needed (line 80)
• Locate target via findBucket(key) which returns either a tombstone location or empty slot
• If slot is nil or TOMBSTONE, allocate new pair and increment size
• Otherwise overwrite existing value

Chaining insertion uses slice operations (lines 64-81):

• Verify load factor and resize if necessary (line 64)
• Compute bucket index: idx := m.hashFunc(key)
• Scan existing bucket slice for matching key (lines 68-74)
• If found, update value; otherwise append new pair to slice and increment size

The chaining approach may trigger multiple small allocations as buckets grow, while open addressing allocates single pairs but risks primary clustering during high load factors.

Deletion Strategies

Deletion highlights the most significant behavioral difference between the two implementations.

Open addressing (lines 94-98) cannot physically remove entries without breaking probe chains for subsequent elements. Instead, it replaces the pointer with the TOMBSTONE sentinel:

// hash_map_open_addressing.go lines 95-98
h.buckets[index] = h.TOMBSTONE
h.size--

This lazy deletion preserves the probing sequence while marking the slot available for future insertions.

Separate chaining (lines 84-95) performs physical deletion by reconstructing the slice without the target element:

// hash_map_chaining.go lines 86-94
for i, p := range m.buckets[idx] {
    if p.key == key {
        // Remove element by slicing
        m.buckets[idx] = append(m.buckets[idx][:i], m.buckets[idx][i+1:]...)
        m.size--
        break
    }
}

Chaining immediately reclaims the memory for the deleted pair, while open addressing defers cleanup until resize operations filter out tombstones.

Resizing and Rehashing

Both implementations trigger resize when the load factor exceeds 2/3, but handle data migration differently.

Open addressing (lines 101-113) creates a new pointer array, resets size to zero, and re-inserts only live pairs (skipping tombstones):

// From hash_map_open_addressing.go extend() method
oldBuckets := h.buckets
h.capacity *= h.extendRatio
h.buckets = make([]*pair, h.capacity)
h.size = 0
for _, pair := range oldBuckets {
    if pair != nil && pair != h.TOMBSTONE {
        h.put(pair.key, pair.val)
    }
}

This process automatically compacts the table by eliminating tombstones during rehashing.

Separate chaining (lines 98-119) preserves the nested slice structure during resize, copying existing buckets to a temporary variable before rehashing all entries into new empty bucket slices:

tmpBuckets := m.buckets
m.capacity *= m.extendRatio
m.buckets = make([][]pair, m.capacity)
m.size = 0
for _, bucket := range tmpBuckets {
    for _, p := range bucket {
        m.put(p.key, p.val)
    }
}

Chaining maintains its bucket boundaries during rehashing, while open addressing redistributes entries across a completely flat new array.

Practical Usage Comparison

Both implementations expose identical public APIs but exhibit different performance characteristics:

// Open addressing - prone to clustering but cache-friendly
oa := newHashMapOpenAddressing()
oa.put(1, "apple")
oa.put(5, "banana")  // May probe multiple slots
oa.remove(1)         // Leaves tombstone marker

// Chaining - predictable bucket sizes, pointer chasing
ch := newHashMapChaining()
ch.put(1, "apple")
ch.put(5, "banana")  // Stored in same bucket slice
ch.remove(1)         // Physically removes from slice

Summary

• Open addressing stores entries in a flat []*pair array using linear probing and tombstone markers for deletion, requiring careful handling of probe sequences in findBucket (lines 44-66).
• Separate chaining uses [][]pair bucket slices where collisions append to lists, enabling simple slice operations for deletion (lines 84-95) without tombstones.
• Both implementations share hash logic (key % capacity) and resize triggers (load factor > 2/3), but differ in memory layout—flat pointers versus nested slices.
• Open addressing compacts automatically during resize by skipping tombstones, while chaining maintains physical deletion semantics throughout the lifecycle.

Frequently Asked Questions

What is the purpose of the TOMBSTONE marker in open addressing?

The TOMBSTONE sentinel preserves the probe sequence for entries that were inserted after the deleted slot. According to the hello-algo source code (lines 28-30), marking a slot as TOMBSTONE rather than nil ensures that findBucket continues searching past deleted entries when looking up keys that were hashed to later indices. Without this marker, the probe chain would break and retrieval would incorrectly fail for existing keys.

Why does separate chaining use [][]pair instead of []*pair?

Separate chaining stores buckets as slices of value types ([]pair) rather than pointers to allow the underlying array to grow dynamically as collisions occur. Each bucket in hashMapChaining (lines 13-20) functions as an independent resizable list, whereas open addressing requires the fixed capacity of the flat []*pair array to manage probe distances deterministically.

How do the resize operations differ between the two implementations?

During resize, open addressing (lines 101-113) filters out tombstones by only re-inserting live pairs, effectively defragmenting the table. Chaining (lines 98-119) iterates through all existing bucket slices and rehashes every pair into the new bucket array, maintaining the list structure but redistributing entries according to the new capacity. Both double the capacity and reset size to zero before re-insertion.

Which implementation handles high load factors better?

Separate chaining typically tolerates higher load factors before degradation because each bucket grows independently as a slice. Open addressing in hello-algo triggers resize at load factor > 2/3 (line 80) to avoid primary clustering and excessive probing distances that would degrade put and get operations to O(n) in the worst case.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}