---
title: "Chaining for collision resolution"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:chaining-collision-resolution"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/chaining-collision-resolution
site: BCT Engineering
---

# Chaining for collision resolution

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2072 Magh, 4 marks
- Video: [Separate chaining in hashing with simple example](https://www.youtube.com/watch?v=H3RGyGOZqko) — Learn Tech
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/chaining-collision-resolution
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

Explain the chaining strategy 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.

## Answer

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:
```text
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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In separate chaining, what does each hash table location hold?
   A. Only one key, with others discarded
   B. A pointer to the next free slot in the table
   C. A sorted array of all keys
   D. The head of a linked list of all keys hashing there
   Answer: D. Colliding keys are stored in the list at that location, so no other table slot is needed. (Key point: Chaining structure)

2. How is a key searched in a chained hash table?
   A. Compute h(k) and scan only the list at that slot
   B. Scan the whole table linearly
   C. Probe h(k)+1, h(k)+2, ... until found
   D. Rehash the table first
   Answer: A. Only the list at h(k) can contain the key. (Key point: Chaining search)

3. m = 5, h(k) = k mod 5, keys 12, 7, 22, 9, 17. Which keys share slot 2?
   A. 12, 22 only
   B. 12, 7, 22, 17
   C. 7, 9, 17
   D. 12, 7, 9
   Answer: B. 12, 7, 22 and 17 all leave remainder 2 mod 5; 9 goes to slot 4. (Key point: Chaining example)

4. What is the average search time in chaining?
   A. O(log n) always
   B. O(n^2)
   C. O(1 + alpha), where alpha = n/m
   D. O(1) regardless of load
   Answer: C. Average list length is the load factor alpha, so search costs O(1 + alpha). (Key point: Load factor)

## Related in Data Structure and Algorithm

- [Collision resolution techniques in hashing](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acollision-resolution-methods) — Data Structure and Algorithm, chapter 8, asked 3×
- [Hashing and collision resolution techniques](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asequential-search-hashing-collision) — Data Structure and Algorithm, chapter 8