- 2069 Bhadra · 8 marks
Double hashing table with m = 11
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.
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.
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 |
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Hashing and different hash functions · Data Structure and Algorithm, chapter 8
- Hash table with chaining, m = 13 · Data Structure and Algorithm, chapter 8
- Linear probing insertion into size-10 table · Data Structure and Algorithm, chapter 8
- Heap sort on 37, 33, 26, 92, ... · Data Structure and Algorithm, chapter 7
- Linear, quadratic probing and double hashing · Data Structure and Algorithm, chapter 8
- B-tree from 78, 21, 14, 11, 97, 85, 74, 63 · Data Structure and Algorithm, chapter 6 · asked 2×
- Block diagram reduction: G3 feedforward, H1 and H2 loops · Control Systems, chapter 3 · asked 4×
- Block diagram reduction: G1–G4, H1, H2, unity loop · Control Systems, chapter 3 · asked 4×
- Block diagram reduction: G1–G4, H1, H2, unity feedback · Control Systems, chapter 3 · asked 3×
- Block diagram reduction: G1–G4 with H1, H2, H3 · Control Systems, chapter 3 · asked 3×