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

# Hashing and collision resolution techniques

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2068 Magh, 5 marks
- Video: [Hashing in Data Structures, Collision Resolution Techniques, Hashing, Data Structures](https://www.youtube.com/watch?v=M4ePx_MLPo4) — CSIT Tutorials by KanyaKumari
- 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/sequential-search-hashing-collision
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

Define hashing and discuss different collision resolution techniques in hashing.

## Short answer

Hashing computes a record’s address directly from its key using a hash function, giving O(1) average access. Collision resolution methods include open addressing (linear probing, quadratic probing, double hashing) where all keys stay in the table, and separate chaining where each slot holds a linked list.

## Answer

**Hashing** is a technique where the address of a record is computed directly from its key using a hash function h(k), for example h(k) = k mod m in a table of size *m*. It gives O(1) average-time insertion and search. A **collision** occurs when two different keys give the same address, and it must be resolved.

#### Collision resolution techniques
**1. Open addressing:** every key stays in the table; if h(k) is full, a probe sequence is followed.
- Linear probing: (h(k) + i) mod m. Simple but causes primary clustering.
- Quadratic probing: (h(k) + i²) mod m. Less primary clustering, some secondary clustering.
- Double hashing: (h1(k) + i·h2(k)) mod m. Best distribution.

**2. Separate chaining:** each table slot points to a linked list of all keys hashing to it.

Example (m = 10, h(k) = k mod 10, keys 31, 41, 51):

| Method | 31 | 41 | 51 |
|---|---|---|---|
| Linear probing | 1 | 2 | 3 |
| Quadratic probing | 1 | 2 | 5 (1+4) |
| Chaining | slot 1 list: 31 → 41 → 51 | | |

Chaining never overflows but needs pointers; open addressing saves memory but needs a table larger than the number of keys.

## Check yourself

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

1. What is a collision in hashing?
   A. A key not found
   B. Two different keys giving the same address
   C. A full table
   D. A key hashing to 0
   Answer: B. Different keys with h(k1) = h(k2) collide and must be resolved. (Key point: Collision definition)

2. What distinguishes open addressing from chaining?
   A. Keys are stored in linked lists
   B. The table grows automatically
   C. All keys stay inside the table and a probe sequence finds a free slot
   D. Collisions are ignored
   Answer: C. Open addressing probes other slots in the table; chaining uses external lists. (Key point: Open addressing)

3. m = 10, keys 31, 41, 51. Where does 51 go with quadratic probing?
   A. Slot 3
   B. Slot 2
   C. Slot 6
   D. Slot 5
   Answer: D. 31 -> 1, 41 -> 2 (1+1), 51: 1 and 2 full, then 1+4 = 5. (Key point: Quadratic example)

4. Which is true of chaining versus open addressing?
   A. Chaining never overflows but needs pointers
   B. Chaining uses less memory
   C. Open addressing can hold more keys than slots
   D. Chaining causes primary clustering
   Answer: A. Lists grow without limit but cost extra pointer memory. (Key point: Tradeoff)

## 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×
- [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
- [Linear, quadratic probing and double hashing](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aprobing-double-hashing-resolve) — Data Structure and Algorithm, chapter 8