---
title: "Linear probing insertion into size-10 table"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:hash-linear-probing-62-37"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/hash-linear-probing-62-37
site: BCT Engineering
---

# Linear probing insertion into size-10 table

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2073 Bhadra, 5 marks
- Video: [L-6.4: Linear Probing in Hashing with example](https://www.youtube.com/watch?v=ZEyPqqRTO00) — Gate Smashers
- 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/hash-linear-probing-62-37
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

Consider a hash table of size 10. Using linear probing, insert the keys 62, 37, 36, 44, 67, 91, 82 and 107.

## Short answer

With h(k)=k mod 10 and linear probing, keys 62,37,36,44,67,91,82,107 are placed at indices 2,7,6,4,8,1,3,9 respectively after resolving collisions. Final table: 0:-, 1:91, 2:62, 3:82, 4:44, 5:-, 6:36, 7:37, 8:67, 9:107.

## Answer

Table size m = 10, h(k) = k mod 10. If slot h(k) is full, try (h(k) + i) mod 10 for i = 1, 2, ...

| Key | h(k) | Probes | Slot used |
|---|---|---|---|
| 62 | 2 | 2 | 2 |
| 37 | 7 | 7 | 7 |
| 36 | 6 | 6 | 6 |
| 44 | 4 | 4 | 4 |
| 67 | 7 (full) | 7, 8 | 8 |
| 91 | 1 | 1 | 1 |
| 82 | 2 (full) | 2, 3 | 3 |
| 107 | 7 (full) | 7, 8 (full), 9 | 9 |

**Final hash table**

| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | | 91 | 62 | 82 | 44 | | 36 | 37 | 67 | 107 |

Slots 0 and 5 remain empty.

## Check yourself

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

1. With m = 10 and linear probing, key 67 (h = 7) finds slot 7 occupied by 37. Where does it go?
   A. Slot 6
   B. Slot 9
   C. Slot 0
   D. Slot 8
   Answer: D. The next slot (7+1) mod 10 = 8 is free. (Key point: Linear probing rule)

2. Key 107 (h = 7) is inserted after 37 and 67. Which slot does it finally use?
   A. Slot 9
   B. Slot 8
   C. Slot 7
   D. Slot 0
   Answer: A. Slots 7 and 8 are full, so it probes slot 9. (Key point: Repeated probing)

3. After inserting all the keys, which slots remain empty?
   A. 1 and 6
   B. 0 and 5
   C. 3 and 9
   D. 0 and 9
   Answer: B. Slots 1,2,3,4,6,7,8,9 are filled; only 0 and 5 are unused. (Key point: Wraparound/empty slots)

4. Why is 82 placed in slot 3?
   A. 82 mod 10 = 3
   B. Slot 2 is empty so it goes in 3 anyway
   C. Home slot 2 holds 62, so the next probe slot 3 is used
   D. It wraps around from slot 9
   Answer: C. 82 mod 10 = 2 is occupied by 62, and linear probing then tries slot 3. (Key point: Key 82)

## Related in Data Structure and Algorithm

- [Hash table with chaining, m = 13](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahash-chaining-m13) — 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
- [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
- [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
- [B-tree of order 5 for 82, 12, 22, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-order5-82-12-22) — Data Structure and Algorithm, chapter 6, asked 2×
- [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

## Related in other subjects

- [Aggregate reserve: sandstone N44W/36, 82 m](https://www.bctengineer.com/question.md?key=semester_4%2Fengineering_geology_ii%3Areserve-sandstone-n44w-36) — Engineering Geology II, chapter 7, asked 2×
- [File size: 10 s, 44.1 KHz, 16-bit stereo](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Aaudio-size-10s-44khz-16bit) — Multimedia System, chapter 2, asked 2×
- [Stability and gains for S21 = 10.11∠91°](https://www.bctengineer.com/question.md?key=semester_7%2Frf_and_microwave_engineering%3Aamplifier-stability-gains-0-64) — RF and Microwave Engineering, chapter 6
- [File size: 60 s, 44.1 KHz, 8-bit stereo](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Aaudio-size-60s-44khz-8bit) — Multimedia System, chapter 2, asked 3×