- 2073 Bhadra · 5 marks
Linear probing insertion into size-10 table
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.
Consider a hash table of size 10. Using linear probing, insert the keys 62, 37, 36, 44, 67, 91, 82 and 107.
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.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Hash table with chaining, m = 13 · Data Structure and Algorithm, chapter 8
- Linear and quadratic probing · Data Structure and Algorithm, chapter 8
- Linear, quadratic probing and double hashing · Data Structure and Algorithm, chapter 8
- Double hashing table with m = 11 · Data Structure and Algorithm, chapter 8
- B-tree of order 5 for 82, 12, 22, ... · Data Structure and Algorithm, chapter 6 · asked 2×
- Quadratic probing vs clustering · Data Structure and Algorithm, chapter 8
- Aggregate reserve: sandstone N44W/36, 82 m · Engineering Geology II, chapter 7 · asked 2×
- File size: 10 s, 44.1 KHz, 16-bit stereo · Multimedia System, chapter 2 · asked 2×
- Stability and gains for S21 = 10.11∠91° · RF and Microwave Engineering, chapter 6
- File size: 60 s, 44.1 KHz, 8-bit stereo · Multimedia System, chapter 2 · asked 3×