- 2071 Magh · 6 marks
Hash table with chaining, m = 13
Short answer
With h(k)=k mod 13 and chaining, the hash table lists are: 1→27, 2→28, 4→43→30, 5→5, 6→19, 7→20, 9→22, 12→25; other slots empty.
Insert the following data elements into hash table using hash function h(k) = k mod m, take m = 13, assume collisions are handled by chaining. Keys for hashing are: 5, 28, 19, 25, 20, 43, 22, 27, and 30.
h(k) = k mod 13, collisions handled by chaining (new key added at the end of the list).
| Key | k mod 13 | Slot |
|---|---|---|
| 5 | 5 | 5 |
| 28 | 28 − 26 = 2 | 2 |
| 19 | 19 − 13 = 6 | 6 |
| 25 | 25 − 13 = 12 | 12 |
| 20 | 20 − 13 = 7 | 7 |
| 43 | 43 − 39 = 4 | 4 |
| 22 | 22 − 13 = 9 | 9 |
| 27 | 27 − 26 = 1 | 1 |
| 30 | 30 − 26 = 4 | 4 (collision with 43) |
Hash table
0 -> NULL
1 -> 27 -> NULL
2 -> 28 -> NULL
3 -> NULL
4 -> 43 -> 30 -> NULL
5 -> 5 -> NULL
6 -> 19 -> NULL
7 -> 20 -> NULL
8 -> NULL
9 -> 22 -> NULL
10 -> NULL
11 -> NULL
12 -> 25 -> NULL
Only one collision occurs (30 with 43 at slot 4).
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Double hashing table with m = 11 · Data Structure and Algorithm, chapter 8
- Hashing and different hash functions · Data Structure and Algorithm, chapter 8
- Linear probing insertion into size-10 table · Data Structure and Algorithm, chapter 8
- AVL tree for 10 20 30 50 45 40 8 5 3 · Data Structure and Algorithm, chapter 6
- AVL tree for 10, 20, 30, 35, 50, ... · Data Structure and Algorithm, chapter 6
- Collision resolution techniques in hashing · Data Structure and Algorithm, chapter 8 · asked 3×
- Subnet 202.77.19.0/24 for 30, 24, 25, 20 · Computer Networks and Security, chapter 4
- Settling tank 30 m x 3 m, 0.03 mm at 25°C; 0.025 mm at 20°C · Water Supply Engineering, chapter 6 · asked 3×
- Irrigation interval: FC 28%, PWP 13% · Irrigation and Drainage Engineering, chapter 2 · asked 2×
- Standard error; population 12,19,13,16 · Probability and Statistics, chapter 4