When two keys hash to the same index, we need to store both. Arrays only hold one value per slot.
Each slot in the hash table holds a linked list (chain) of all key-value pairs that hashed to that index.
- Hash function computes index for a key
- Key-value pair is appended to the linked list at that index
- To search: hash to index, then linearly search the chain
- To delete: find in chain and remove node
- Simple to implement
- Handles high load factors better than probing
- Each chain should be short (ideally O(1) length)
- Deletion is straightforward (just remove from linked list)
- Built from: Hashing, Collision Resolution
- Builds into: Load Factor
- Related: Linked List, Hash Function
- Contrasts with: Linear Probing (chains vs probing)
- Long chains → degrades to O(n) search time
- Extra memory for linked list pointers
- Poor hash function → all keys in one chain
- Best when hash function distributes uniformly