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

# Linear and quadratic probing

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2075 Baisakh, 5 marks
- Video: [Hashing - Linear, and Quadratic probing](https://www.youtube.com/watch?v=LGCc82dwLPQ) — Squiva
- 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/linear-quadratic-probing
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

Discuss about linear probing and quadratic probing.

## Short answer

Linear probing uses h(k,i)=(h(k)+i) mod m, causing primary clustering. Quadratic probing uses offsets i², e.g., (h(k)+i²) mod m, breaking primary clustering but keys with same home slot follow identical probe sequences. For keys 42,52,62,72 (m=10): linear yields 2,3,4,5; quadratic yields 2,3,6,1.

## Answer

Both are open-addressing methods: when the home slot h(k) = k mod m is occupied, other slots in the table are probed in a fixed order.

#### Linear probing
h(k, i) = (h(k) + i) mod m, for i = 0, 1, 2, ... The next free slot is used.
- Easy to implement and cache friendly.
- Causes **primary clustering**: filled slots join into long runs, so insertion and search get slower.

#### Quadratic probing
h(k, i) = (h(k) + c₁·i + c₂·i²) mod m, usually h(k) + i² (offsets 1, 4, 9, ...).
- Probes jump apart, which breaks up primary clustering.
- Keys with the same home slot follow the same probe path (**secondary clustering**).
- It may not reach every slot, so m and the constants must be chosen carefully. For example, with m prime and offsets i², a free slot is always found if the table is less than half full.

#### Example (m = 10, keys 42, 52, 62, 72)
| Key | Linear slot | Quadratic slot |
|---|---|---|
| 42 | 2 | 2 |
| 52 | 3 | 3 (2+1) |
| 62 | 4 | 6 (2+4) |
| 72 | 5 | 1 (2+9 = 11 mod 10) |

Linear probing keeps the keys adjacent (2, 3, 4, 5), while quadratic probing spreads them out (2, 3, 6, 1).

## Check yourself

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

1. What do both methods have in common?
   A. Use linked lists
   B. Probe other slots in the table when the home slot is full
   C. Use a second table
   D. Rehash all keys
   Answer: B. Both are open addressing. (Key point: Open addressing)

2. Linear probing causes?
   A. Secondary clustering only
   B. Primary clustering
   C. No collisions
   D. Overflow of chains
   Answer: B. Runs of filled slots grow. (Key point: Linear drawback)

3. Quadratic probing's remaining weakness?
   A. Secondary clustering: same home slot gives the same probe path
   B. Primary clustering
   C. Needs pointers
   D. Slow insertion
   Answer: A. Keys with the same home follow the same sequence. (Key point: Quadratic)

4. With m = 10, 62 after 42 and 52 goes to which slot under quadratic?
   A. 4
   B. 6
   C. 3
   D. 2
   Answer: B. 2+4 = 6 (linear gives 4). (Key point: Example)

## Related in Data Structure and Algorithm

- [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
- [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