---
title: "Double hashing table with m = 11"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:double-hashing-table-m11"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/double-hashing-table-m11
site: BCT Engineering
---

# Double hashing table with m = 11

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2069 Bhadra, 8 marks
- Video: [L-6.7: Double Hashing | Collision Resolution Technique](https://www.youtube.com/watch?v=1P7ygNSe9lY) — 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/double-hashing-table-m11
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

Draw the hash table obtained from double hashing with hash functions h1(k) = k mod 11 and h2(k) = k mod 9 to the keys given by: 76, 26, 37, 59, 21, 65 with table size m = 11. Use hp(k, i) = (h1(k) + i*h2(k)) mod m.

## Short answer

With h1(k)=k mod 11 and h2(k)=k mod 9, double hashing places: 76→10, 26→4, 37→5 (i=1), 59→9 (i=1), 21→2 (i=1), 65→1 (i=1). Final table: 0:-, 1:65, 2:21, 3:-, 4:26, 5:37, 6:-, 7:-, 8:-, 9:59, 10:76.

## Answer

Probe sequence: hp(k, i) = (h1(k) + i·h2(k)) mod 11, with h1 = k mod 11 and h2 = k mod 9. Try i = 0, 1, 2, ... until a free slot is found.

| Key | h1 | h2 | Probes (i: slot) | Slot used |
|---|---|---|---|---|
| 76 | 10 | 4 | 0: 10 free | 10 |
| 26 | 4 | 8 | 0: 4 free | 4 |
| 37 | 4 | 1 | 0: 4 full; 1: (4+1) = 5 free | 5 |
| 59 | 4 | 5 | 0: 4 full; 1: (4+5) = 9 free | 9 |
| 21 | 10 | 3 | 0: 10 full; 1: (10+3) mod 11 = 2 free | 2 |
| 65 | 10 | 2 | 0: 10 full; 1: (10+2) mod 11 = 1 free | 1 |

**Final hash table (m = 11)**

| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Key | | 65 | 21 | | 26 | 37 | | | | 59 | 76 |

## Check yourself

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

1. Which formula gives the i-th probe here?
   A. (k mod 9 + i*(k mod 11)) mod 9
   B. (k mod 11 + i^2) mod 11
   C. (k mod 11 + i*(k mod 9)) mod 11
   D. (k mod 11 + i) mod 11
   Answer: C. hp(k,i) = (h1(k) + i*h2(k)) mod m with h1 = k mod 11 and h2 = k mod 9. (Key point: Probe formula)

2. 37 has h1 = 4, h2 = 1 and slot 4 is taken by 26. Where does it go?
   A. Slot 9
   B. Slot 3
   C. Slot 1
   D. Slot 5
   Answer: D. The step is h2 = 1, so (4+1) mod 11 = 5, which is free. (Key point: Key 37)

3. 21 has h1 = 10, h2 = 3, and slot 10 is full. Which slot does it use?
   A. Slot 2
   B. Slot 13
   C. Slot 3
   D. Slot 10
   Answer: A. (10+3) mod 11 = 2. (Key point: Key 21 wraparound)

4. 65 has h1 = 10, h2 = 2. Which slot does it finally occupy?
   A. Slot 0
   B. Slot 1
   C. Slot 2
   D. Slot 12
   Answer: B. (10+2) mod 11 = 1, which is free. (Key point: Key 65)

## Related in Data Structure and Algorithm

- [Hashing and different hash functions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahashing-hash-functions) — Data Structure and Algorithm, chapter 8
- [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 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
- [Heap sort on 37, 33, 26, 92, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-construct-12-element) — Data Structure and Algorithm, chapter 7
- [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
- [B-tree from 78, 21, 14, 11, 97, 85, 74, 63](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-build-78-21-14) — Data Structure and Algorithm, chapter 6, asked 2×

## Related in other subjects

- [Block diagram reduction: G3 feedforward, H1 and H2 loops](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Abdr-g1g2g3-h1h2-b) — Control Systems, chapter 3, asked 4×
- [Block diagram reduction: G1–G4, H1, H2, unity loop](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Abdr-g1-g4-h1h2-2075a) — Control Systems, chapter 3, asked 4×
- [Block diagram reduction: G1–G4, H1, H2, unity feedback](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Abdr-g1-g4-h1h2-unity-2076c) — Control Systems, chapter 3, asked 3×
- [Block diagram reduction: G1–G4 with H1, H2, H3](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Abdr-g1-g4-h1h2h3-2073) — Control Systems, chapter 3, asked 3×