# Separate Chaining Search

# 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

```text id="0zx7yw"
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

```python id="0e4g9x"
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
```

```go id="b2x9qa"
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
}
```