HashingData structureaka chained hashing, bucket lists, closed addressing

Separate Chaining

Collision resolution where each bucket holds a linked list (or small array) of all entries that hash to it.

▶ VisualizePattern: HashingPractice (1)
Progress

Definition

In separate chaining the bucket array does not hold entries directly; each slot points to a chain — a Singly Linked List, a small Dynamic Array, or (Java 8+) a Red-Black Tree once the chain grows past 8 — containing every entry whose hash lands there.

Insert appends to (or updates within) the chain, lookup scans the chain comparing keys, delete unlinks a node. The table never "fills up": the load factor can exceed 1, only the chains grow longer.

Chaining is the default in Java HashMap, C++ std::unordered_map, and most textbook implementations because it is simple, tolerant of poor hashing, and makes deletion trivial.

collisionlinked listbucketsload factorJava HashMap

Intuition

A mental model before the formal terms.

A row of mailboxes where each mailbox has a hook and every letter for that box is clipped onto a chain hanging from it. Finding a letter means going to the right mailbox and flipping through its chain — usually one or two letters.

How it works

  1. Allocate m empty chains.
  2. put(k, v): idx = hash(k) mod m; walk chain idx; if a node has key k, overwrite its value; else prepend or append a new node and increment n.
  3. get(k): walk chain idx and return the first node with key k.
  4. remove(k): walk chain idx with a trailing pointer and unlink the matching node.
  5. When n / m > 0.75, allocate 2m chains and move each node into its new chain (the node objects can be reused).

Why it works

Expected chain length is α = n / m under uniform hashing; with α ≤ 0.75 most chains hold 0 or 1 entries, so scans are O(1) expected.

Because entries never occupy each other's slots, there is no clustering effect and no need for tombstones — deletion is a plain unlink.

Treeifying long chains bounds the worst case at O(log n) even under hash flooding.

Operations

OperationDescriptionCost
put(k, v)Append/overwrite in the bucket chain.O(1 + α) expected
get(k)Scan the bucket chain.O(1 + α) expected
remove(k)Unlink from the bucket chain.O(1 + α) expected
rehashRedistribute all nodes into 2m chains.O(n + m)

Recognition

How to tell a problem wants this.

  • You are asked to implement a hash map "with linked lists" or to handle collisions in the simplest robust way.
  • The key/value payload is large or deletion is frequent.
  • You want predictable behaviour when the hash function quality is uncertain.
“have you seen this before” → Hashing“reverse a linked list” → Linked List Manipulation

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Hash Table visualization.

a
∅
0
∅
1
∅
2
∅
3
∅
4
∅
5
∅
6
bucket 0
∅
0
bucket 1
∅
0
bucket 2
∅
0
bucket 3
∅
0
bucket 4
∅
0
bucket 5
∅
0
bucket 6
∅
0
1/41Empty table with m = 7 buckets. Colliding keys share a bucket as a linked chain, so the table never "fills up" — only the chains grow.
Hashed bucketChain node comparedMatchInserted / removed
PseudocodeLearn Hash Table →
1h = key % m
2insert: scan bucket[h]; if key present: done, else append to the chain
3search: scan bucket[h] comparing each key
4delete: scan bucket[h]; unlink the matching node
Variables
m7
size0
load0.00
Complexity
access O(1)
search O(1)
insert O(1)
delete O(1)
Speed

Pseudocode

1class ChainedHashMap:
2  chains = array of m empty lists
3  put(k, v): c = chains[h(k)]; for node in c: if node.key == k: node.val = v; return
4             c.prepend(Node(k, v)); n++; if n > 0.75 * m: rehash()
5  get(k): for node in chains[h(k)]: if node.key == k: return node.val; return null
6  remove(k): unlink first node in chains[h(k)] with key k; n--

Implementation

1from dataclasses import dataclass
2from typing import Generic, Hashable, Optional, TypeVar
3 
4K = TypeVar("K", bound=Hashable)
5V = TypeVar("V")
6 
7 
8@dataclass
9class Node(Generic[K, V]):
10    key: K
11    value: V
12    next: "Optional[Node[K, V]]" = None
13 
14 
15class ChainedMap(Generic[K, V]):
16    """Separate chaining: each bucket is a singly linked list of nodes."""
17 
181 · Buckets of linked nodes
19    def __init__(self, cap: int = 8) -> None:
20        self._buckets: list[Optional[Node[K, V]]] = [None] * cap
21        self._n = 0
22 
23    def _index(self, key: K) -> int:
24        return hash(key) % len(self._buckets)
25 
262 · Insert or update at the head of the chain
27    def put(self, key: K, value: V) -> None:
28        i = self._index(key)
29        node = self._buckets[i]
30        while node is not None:
31            if node.key == key:
32                node.value = value
33                return
34            node = node.next
35        self._buckets[i] = Node(key, value, self._buckets[i])
36        self._n += 1
37        if self._n > len(self._buckets):  # load factor 1.0
38            self._rehash()
39 
403 · Walk the chain to find
41    def get(self, key: K) -> Optional[V]:
42        node = self._buckets[self._index(key)]
43        while node is not None:
44            if node.key == key:
45                return node.value
46            node = node.next
47        return None
48 
494 · Unlink the node
50    def remove(self, key: K) -> bool:
51        i = self._index(key)
52        prev: Optional[Node[K, V]] = None
53        node = self._buckets[i]
54        while node is not None:
55            if node.key == key:
56                if prev is None:
57                    self._buckets[i] = node.next
58                else:
59                    prev.next = node.next
60                self._n -= 1
61                return True
62            prev, node = node, node.next
63        return False
64 
65    def __len__(self) -> int:
66        return self._n
67 
685 · Rehash into twice as many buckets
69    def _rehash(self) -> None:
70        old = self._buckets
71        self._buckets = [None] * (len(old) * 2)
72        for head in old:
73            while head is not None:
74                nxt = head.next
75                i = self._index(head.key)
76                head.next = self._buckets[i]
77                self._buckets[i] = head  # reuse the node, no allocation
78                head = nxt
Walkthrough
  1. Node is a dataclass with a forward reference to its own type for next.
  2. put walks the chain with a while loop; new nodes are prepended so self._buckets[i] becomes the new head.
  3. get returns None when absent (mirroring dict.get).
  4. remove tracks prev and relinks; prev, node = node, node.next advances both in one statement.
  5. _rehash relinks existing nodes into a bigger bucket list.
Complexity (this implementation)
time O(1 + α) average, O(n) worst · space O(n + capacity)

Python objects are heavy (~56 bytes per node); dict's compact open-addressing layout is far smaller.

Language notes
  • CPython dict does not use chaining; this class is for understanding, not production.
  • @dataclass generates __init__ and __repr__; add slots=True (3.10+) to shrink nodes.
  • A list-of-lists bucket is simpler in Python and often faster because list ops are C-implemented.
Common mistakes in this language
  • Comparing node == None instead of node is None.
  • Building buckets with [[]] * cap (aliasing) — here [None] * cap is safe because None is immutable.
  • Forgetting to save head.next before relinking in _rehash.
Language differences that matter here
  • C++ has a real singly linked list (std::forward_list); JS/TS/Python build nodes by hand.
  • Memory: C++ nodes are compact structs; Python and JS nodes are full heap objects with much higher overhead.
  • C++ unordered_map is chained; Python dict and V8 Map are not — chaining is a teaching model in those languages.

Complexity

OperationAverageWorstNote
AccessO(1)O(n)O(log n) worst with treeified chains.
SearchO(1 + α)O(n)
InsertO(1)O(n)Amortized; rehash is O(n).
DeleteO(1 + α)O(n)Plain unlink, no tombstones.
UpdateO(1 + α)O(n)
RehashO(n + m)O(n + m)
SpaceO(n + m)One extra pointer per entry plus the bucket array.

Advantages & disadvantages

Advantages
  • Simple to implement and reason about; deletion is trivial.
  • Degrades gracefully as the load factor rises past 1.
  • Chains can be upgraded to trees to cap the worst case.
Disadvantages
  • Each entry costs an extra pointer (and often a separate heap allocation), hurting memory and cache locality.
  • Pointer chasing through chains is slower than probing contiguous slots for small keys.
  • Bucket array plus node allocations create more garbage-collector pressure.

Use cases

  • Java HashMap/HashSet, C++ unordered_map, Go sync.Map internals.
  • Interview "design a hash map" implementations.
  • Tables with large values or frequent deletes.
Use it when
  • Default choice when implementing a hash map by hand.
  • Frequent deletions, large entries, or unknown hash quality.
  • Load factors near or above 1 are acceptable to save memory.
Avoid it when
  • Entries are tiny (ints, pointers) and cache locality dominates — prefer Open Addressing.
  • Allocation is expensive or forbidden (embedded, real-time) — open addressing needs one contiguous block.

Alternatives

Open AddressingCollision HandlingBinary Search Tree

Common mistakes

  • Forgetting to check for an existing key before appending, creating duplicate entries in a chain.
  • Losing the head pointer on delete when the matching node is the first in the chain.
  • Rehashing by calling put on each old node (allocates new nodes) instead of relinking existing ones.
  • Using hash % m with a negative hash in Java/C++/Go.

Interview patterns

  • Design HashMap (LeetCode 706): array of linked lists with put/get/remove.
  • Explain how Java HashMap treeifies a bin when its chain reaches 8 and the table has ≥ 64 buckets.
  • Compare memory per entry: chaining (key + value + next pointer + node header) vs. open addressing (key + value only).
Interview questions on this
Mock interviews

Interview problems

Design HashMapeasy