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

> Explore hello-algo's source code comparing hash map open addressing with chaining. Understand their distinct collision resolution, deletion, and memory layout differences.

- Repository: [Yudong Jin/hello-algo](https://github.com/krahets/hello-algo)
- Tags: internals
- Published: 2026-02-25

---

**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:

```go
// 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:

```go
// 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:

```go
// 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:

```go
// 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:

```go
// 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):

```go
// 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:

```go
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:

```go
// 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.