Past exam question: 2077 Chaitra (Regular), Q7
Open in the Padhaiko appQuestion
Define collision. Insert the keys 30, 15, 69, 28, 49, 58, 79 and 91 using quadratic probing method. The hash function is : h(key) = key%10 where 10 is the table size.
Solution
Definition of Collision: A collision occurs when two or more distinct keys produce the same home slot under the hash function ( for ).
Quadratic Probing Trace (, ):
- 30: (empty) slot 0.
- 15: (empty) slot 5.
- 69: (empty) slot 9.
- 28: (empty) slot 8.
- 49: (collision).
- : (occupied)
- : (empty) slot 3.
- 58: (collision).
- : (occupied)
- : (empty) slot 2.
- 79: (collision).
- : (occ), : (occ), : (occ), : (occ), : (empty) slot 4.
- 91: (empty) slot 1.
Final Hash Table:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | 30 | 91 | 58 | 49 | 79 | 15 | — | — | 28 | 69 |
Answer:
Final hash table (slots 0..9): [30, 91, 58, 49, 79, 15, —, —, 28, 69].