Consider the hash table of size 11 that uses open addressing with linear…
2022
Consider the hash table of size 11 that uses open addressing with linear probing. Let ℎ(𝑘) = 𝑘 mod 11 be the hash function. A sequence of records with keys 43,36,92,87.11.47.11,13,14 is inserted into an initially empty hash table, the bins of which are indexed from 0 to 10. What is the index of the bin into which the last record is inserted ?
- A.
8
- B.
7
- C.
10
- D.
4
Attempted by 112 students.
Show answer & explanation
Correct answer: B
Key insight: use h(k) = k mod 11 and linear probing (on collision move to the next index, wrap from 10 to 0).
Insert 43: h(43)=10 -> place at index 10.
Insert 36: h(36)=3 -> place at index 3.
Insert 92: h(92)=4 -> place at index 4.
Insert 87: h(87)=10 -> index 10 occupied (43), probe to 0 -> place at index 0.
Insert 11: h(11)=0 -> index 0 occupied (87), probe to 1 -> place at index 1.
Insert 47: h(47)=3 -> index 3 occupied (36), probe to 4 occupied (92), probe to 5 -> place at index 5.
Insert another 11: h(11)=0 -> 0 occupied (87), probe to 1 occupied (11), probe to 2 -> place at index 2.
Insert 13: h(13)=2 -> index 2 occupied (second 11), probe to 3 occupied (36), probe to 4 (92), probe to 5 (47), probe to 6 -> place at index 6.
Insert 14 (last key): h(14)=3 -> index 3 occupied, probe to 4 occupied, probe to 5 occupied, probe to 6 occupied, probe to 7 -> place at index 7.
Conclusion: the last record (key 14) is inserted into bin index 7.
A video solution is available for this question — log in and enroll to watch it.