Separate Chaining Search

Separate chaining handles collisions in a hash table by storing all elements that hash to the same index in a bucket. Each bucket is typically a linked list, though dynamic arrays or trees are also used.

You search by hashing the key and scanning only the corresponding bucket.

Problem

Given a hash table with chaining and a key $k$, find the associated value if it exists.

Model

• Table $T$ has size $m$
• Hash function $h(k)$ maps keys to indices
• Each $T[i]$ stores a list of entries

Compute:

$$ i = h(k) $$

Then search inside bucket $T[i]$.

Algorithm

chaining_search(T, k):
    i = h(k)
    for each (key, value) in T[i]:
        if key == k:
            return value
    return NOT_FOUND

Example

Let $m = 5$ and:

$$ h(k) = k \bmod 5 $$

Insert:

$$ [12, 7, 22] $$

Buckets:

index	bucket
2	(12 → 7 → 22)

Search for $k = 22$:

• compute $h(22) = 2$
• scan bucket: 12, 7, 22
• match found

Correctness

All keys that hash to index $i$ are stored in bucket $T[i]$. The algorithm examines every element in that bucket. If $k$ exists, it must appear there, so it will be found.

Complexity

Let $\alpha = n/m$ be the load factor.

case	time
average	$O(1 + \alpha)$
worst	$O(n)$

When $\alpha$ remains bounded, lookup runs in constant expected time.

Space

$$ O(n + m) $$

Memory includes the table and all stored elements.

When to Use

Separate chaining is appropriate when:

• table resizing is expensive or infrequent
• deletion operations must be simple
• load factor may grow beyond 1
• memory overhead from pointers is acceptable

It handles high load factors better than open addressing.

Implementation

class HashTable:
    def __init__(self, m=8):
        self.m = m
        self.table = [[] for _ in range(m)]

    def _hash(self, key):
        return hash(key) % self.m

    def get(self, key):
        i = self._hash(key)
        for k, v in self.table[i]:
            if k == key:
                return v
        return None

type Entry[K comparable, V any] struct {
	Key   K
	Value V
}

type HashTable[K comparable, V any] struct {
	Table [][]Entry[K, V]
	M     int
}

func (h *HashTable[K, V]) hash(key K) int {
	return int(uintptr(any(key))) % h.M
}

func (h *HashTable[K, V]) Get(key K) (V, bool) {
	i := h.hash(key)

	for _, e := range h.Table[i] {
		if e.Key == key {
			return e.Value, true
		}
	}

	var zero V
	return zero, false
}