1. One-Liner
Separate chaining stores collisions in per-bucket chains (lists) so many keys can share a slot without probing the whole table.
2. The Problem It Solves
Open addressing struggles with clustering and delete semantics; chaining keeps insert/delete local to a short list while the table load factor can exceed 1 if lists grow.
3. The Core Idea
Hash to an index; if busy, append to the bucket’s list. Lookup scans only that list—average O(1) if load is bounded and hash spreads keys.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Hash | i = h(key) % m |
| 2. Insert | Push or update node in bucket i’s list |
| 3. Search | Walk the list at i comparing keys |
| 4. Delete | Unlink node from the list |
5. Dry Run Example
m=4, chain insert 5,9,13 (all mod 4 → 1): bucket 1 becomes list 5→9→13; search 9 scans at most three nodes.
6. Key Properties
| Property | Value |
|---|---|
| Load factor | Can be >1 (lists grow) |
| Clustering | None in the primary table |
| Cache | Lists may hurt locality vs open addressing |
7. Where It Is Used
| Domain | Use |
|---|---|
| Java | HashMap (bins as trees after threshold) |
| Databases | Symbol tables, join hash indexes |
8. Interview Tips
Contrast chaining vs open addressing; mention rehash when average chain length grows; Java 8+ treeify on long buckets.
9. Comparison with Other Algorithms
| Scheme | Collision handling |
|---|---|
| Chaining | Lists at slot |
| Open addressing | Next empty slot |
| Cuckoo | Evict to alternate table |
10. Complexity
| Metric | Value |
|---|---|
| Average search/insert | O(1) with good hash & load |
| Worst | O(n) if all keys collide |
Implementation Example (PYTHON)
class HashChain:
def __init__(self, m=16):
self.m = m
self.b = [[] for _ in range(m)]
def _h(self, k): return hash(k) % self.m
def put(self, k, v):
i = self._h(k)
for j, (kk, _) in enumerate(self.b[i]):
if kk == k: self.b[i][j] = (k, v); return
self.b[i].append((k, v))
def get(self, k):
i = self._h(k)
for kk, v in self.b[i]:
if kk == k: return v
return None