---
title: "Linear, quadratic probing and double hashing"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:probing-double-hashing-resolve"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/probing-double-hashing-resolve
site: BCT Engineering
---

# Linear, quadratic probing and double hashing

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2072 Asoj, 8 marks
- Video: [Ch 8.3 :Hashing | Open addressing | Quadratic probing |Double hashing | Analysis of open-addressing](https://www.youtube.com/watch?v=Q1Vp6Ezhk5k) — Monalisa CS
- 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/probing-double-hashing-resolve
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

How linear probing, quadratic probing and double hashing techniques are used to resolve collision? Explain with suitable example.

## Short answer

Linear probing (h(k)+i mod m) forms clusters; quadratic probing (h(k)+i² mod m) spreads probes; double hashing (h1(k)+i·h2(k) mod m) uses key-dependent step. Example keys 42,52,62,72 (m=10): linear 2,3,4,5; quadratic 2,3,6,1; double hashing with h2=7-(k mod 7) gives 2,6,3,7.

## Answer

When two keys hash to the same slot (a collision), open addressing searches for another free slot in the table using a probe sequence. Take table size m = 10, with keys 42, 52, 62, 72, which all have home slot 2 (h(k) = k mod 10).

#### Linear probing
h(k, i) = (h(k) + i) mod m. Slots tried: 2, 3, 4, 5, ...
- 42 goes to 2, 52 to 3, 62 to 4, 72 to 5.
- Simple, but forms long clusters (primary clustering).

#### Quadratic probing
h(k, i) = (h(k) + i²) mod m. Slots tried: 2, 3, 6, 11 mod 10 = 1, ...
- 42 goes to 2, 52 to 3, 62 to 6, 72 to 1.
- Avoids primary clustering, but keys with the same home slot still share one path (secondary clustering).

#### Double hashing
h(k, i) = (h1(k) + i·h2(k)) mod m, with h1(k) = k mod 10 and h2(k) = 7 − (k mod 7). The step size depends on the key.
- 42: slot 2.
- 52: h2 = 7 − 3 = 4; slot 2 is full, so the next slot is 2 + 4 = 6.
- 62: h2 = 7 − 6 = 1; slot 2 is full, so the next slot is 3.
- 72: h2 = 7 − 2 = 5; slot 2 is full, so the next slot is 7.

| Method | 42 | 52 | 62 | 72 |
|---|---|---|---|---|
| Linear | 2 | 3 | 4 | 5 |
| Quadratic | 2 | 3 | 6 | 1 |
| Double hashing | 2 | 6 | 3 | 7 |

Double hashing gives the best spread because different keys with the same home slot get different steps. h2(k) must never be 0 and should be relatively prime to m (a prime table size guarantees this; m = 10 is used here only to keep the example simple).

## Check yourself

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

1. Which probe sequence does linear probing use?
   A. h(k, i) = (h(k) + i) mod m
   B. h(k, i) = (h(k) + i^2) mod m
   C. h(k, i) = (h1(k) + i*h2(k)) mod m
   D. h(k, i) = (h(k) * i) mod m
   Answer: A. Linear probing steps one slot at a time: h(k), h(k)+1, h(k)+2, ... modulo m. (Key point: Linear probe sequence)

2. With m = 10, keys 42, 52, 62, 72 all hash to slot 2. Where do they land with linear probing?
   A. 2, 3, 6, 1
   B. 2, 3, 4, 5
   C. 2, 6, 3, 7
   D. 2, 4, 6, 8
   Answer: B. Each colliding key takes the next free consecutive slot, forming a primary cluster. (Key point: Primary clustering)

3. Using h(k, i) = (h(k) + i^2) mod 10, where does 72 (4th key with home slot 2) go?
   A. Slot 5
   B. Slot 6
   C. Slot 1
   D. Slot 7
   Answer: C. Offsets 1, 4, 9 give slots 3, 6, 11 mod 10 = 1; 72 is the 4th key so it takes slot 1. (Key point: Quadratic probing result)

4. Why does double hashing spread keys with the same home slot better than the other methods?
   A. It uses a bigger table
   B. It always probes slot h(k)+1
   C. It removes collisions completely
   D. The step h2(k) depends on the key, so each key gets its own probe path
   Answer: D. Different keys with the same home slot get different steps, avoiding both primary and secondary clustering. (Key point: Double hashing step size)

## 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
- [Linear and quadratic probing](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Alinear-quadratic-probing) — Data Structure and Algorithm, chapter 8
- [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×
- [Quadratic probing vs clustering](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aquadratic-probing-clustering) — Data Structure and Algorithm, chapter 8
- [Linear probing insertion into size-10 table](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahash-linear-probing-62-37) — Data Structure and Algorithm, chapter 8
- [Double hashing table with m = 11](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adouble-hashing-table-m11) — Data Structure and Algorithm, chapter 8

## Related in other subjects

- [Matching techniques and double-stub S-matrix](https://www.bctengineer.com/question.md?key=semester_7%2Frf_and_microwave_engineering%3Amatching-techniques-double-stub-smatrix) — RF and Microwave Engineering, chapter 2
- [Linear solution techniques; CG two iterations](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Asolution-techniques-cg-numerical-two-iter) — Computational Techniques in Civil Engineering, chapter 2
- [Linear solution techniques; CG algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Asolution-techniques-cg-algorithm) — Computational Techniques in Civil Engineering, chapter 2
- [Double refraction, linear and circular light](https://www.bctengineer.com/question.md?key=semester_1%2Fengineering_physics%3Adouble-refraction-produce-polarized-light) — Engineering Physics, chapter 4