---
title: "Collision resolution techniques in hashing"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:collision-resolution-methods"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/collision-resolution-methods
site: BCT Engineering
---

# Collision resolution techniques in hashing

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2071 Bhadra, 8 marks; 2070 Magh, 6 marks; 2068 Magh, 5 marks (asked 3 times)
- Video: [Collision Resolution Techniques in Hashing | Linear Probing | Chaining | Data Structures](https://www.youtube.com/watch?v=CtWwO-_gct8) — Dr. Ankit Verma
- 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/collision-resolution-methods
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

What is collision? Explain different methods of collision resolution in hashing with suitable example.

## Short answer

Collision: different keys map to same table index. Resolution: open addressing probes alternative slots (linear, quadratic, double hashing); separate chaining stores colliding keys in a linked list at that index. Example: h(k)=k mod 10, keys 42,52; linear probing places them at 2 and 3; chaining puts both in list at 2.

## Answer

A **collision** occurs when two different keys hash to the same table location, i.e. h(k1) = h(k2) for k1 ≠ k2. For example, with h(k) = k mod 10, keys 42 and 52 both map to location 2. A collision resolution technique decides where the second key is stored.

Methods are in two groups.

#### 1. Open addressing (closed hashing)
All keys stay inside the table. If the home location is full, other locations are probed in a fixed sequence.
- **Linear probing:** h(k, i) = (h(k) + i) mod m. Try the next slot, then the next, and so on. Simple, but causes primary clustering (long runs of filled slots).
- **Quadratic probing:** h(k, i) = (h(k) + c₁i + c₂i²) mod m, e.g. +1, +4, +9. Reduces primary clustering, but keys with the same home slot follow the same path (secondary clustering).
- **Double hashing:** h(k, i) = (h1(k) + i·h2(k)) mod m. The step depends on the key, so clustering is much lower.

Example (m = 10, h(k) = k mod 10, keys 42, 52, 62):

| Method | 42 | 52 | 62 |
|---|---|---|---|
| Linear | 2 | 3 | 4 |
| Quadratic | 2 | 3 | 6 |

#### 2. Separate chaining (open hashing)
Each table location holds a linked list of all keys that hash there. A colliding key is simply added to the list.

```text
0 -> NULL
2 -> 42 -> 52 -> 62 -> NULL
3 -> 13 -> NULL
```
- Table never overflows; deletion is easy.
- Needs extra memory for pointers; search is O(1 + α) where α = n/m is the load factor.

Other schemes are rehashing and coalesced chaining. Open addressing needs a load factor below 1, while chaining works for any load factor.

## Check yourself

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

1. What is a collision?
   A. Two different keys hash to the same location
   B. A key is not found
   C. The table is empty
   D. A key is deleted
   Answer: A. h(k1) = h(k2) with k1 != k2. (Key point: Collision)

2. What drawback does linear probing have?
   A. Primary clustering
   B. Needs pointers
   C. Table can overflow past 100%
   D. Cannot insert
   Answer: A. Filled slots form long runs. (Key point: Linear probing)

3. With m = 10, keys 42, 52, 62 under quadratic probing go to which slots?
   A. 2, 3, 4
   B. 2, 3, 6
   C. 2, 4, 6
   D. 2, 3, 5
   Answer: B. Offsets +1, +4: 2, 3, 6. (Key point: Quadratic)

4. How does separate chaining resolve collisions?
   A. Probes next slot
   B. Each location holds a linked list of keys hashing there
   C. Rehashes with another function
   D. Overwrites the old key
   Answer: B. Colliding keys are added to the list. (Key point: Chaining)

## Related in Data Structure and Algorithm

- [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
- [Chaining for collision resolution](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Achaining-collision-resolution) — Data Structure and Algorithm, chapter 8