Skip to main content

Chaining for collision resolution

Short answer

In separate chaining, each hash table slot points to a linked list of all keys hashing to that index. Insert appends to the list, search scans only that list, and deletion unlinks the node. It avoids full table but requires extra pointer memory.

Explain the chaining strategy for collision resolution.

In chaining (separate chaining or open hashing), each location of the hash table is the head of a linked list. All keys that hash to the same location are stored in that location's list, so collisions never need another table slot.

  • Insert: compute h(k), add the new node at the head (or end) of list h(k).
  • Search: compute h(k) and scan only that list.
  • Delete: find the node in the list and unlink it.

Example, m = 5, h(k) = k mod 5, keys 12, 7, 22, 9, 17:

0 -> NULL
1 -> NULL
2 -> 12 -> 7 -> 22 -> 17 -> NULL
3 -> NULL
4 -> 9 -> NULL

(12, 7, 22, 17 all hash to 2.)

Advantages: table never becomes full, deletion is simple, performance degrades gently as load grows. Disadvantages: extra memory for pointers; long lists make search slow. Average search time is O(1 + α), where α = n/m is the load factor.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 8 questions →