Past exam question: 2078 Baishakh (Back), Q7
Open in the Padhaiko appQuestion
Insert 2, 3, 9, 6, 11, 13, 7, 12 in a hash table using modulo division method with 2*k+3 as hash function. Resolve collision using double hashing. Take second hash function as 3*k+1.
Solution
Choosing Table Size : The problem does not state the table size , so following the exam instruction ("Assume suitable data if necessary"), we choose prime table size (standard for double hashing with 8 keys so that and every probe sequence visits all 11 slots; note that fails on key 7 because enters an odd-index cycle).
Hash functions:
Step-by-Step Insertion Trace:
- 2: (empty) slot 7.
- 3: (empty) slot 9.
- 9: (empty) slot 10.
- 6: (empty) slot 4.
- 11: (empty) slot 3.
- 13: (collision!). :
- : (occupied)
- : (occupied)
- : (empty) slot 6.
- 7: (collision!). (non-zero step, or raw = standard fallback step ):
- : (occupied)
- : (empty) slot 8.
- 12: (empty) slot 5.
Final Hash Table ():
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Key | — | — | — | 11 | 6 | 12 | 13 | 2 | 7 | 3 | 9 |
Answer:
Assuming prime table size with and (fallback if ), the final hash table is: [—, —, —, 11, 6, 12, 13, 2, 7, 3, 9] (indices 0..10).