Consider a dynamic hashing approach for 4-bit integer keys: There is a main…
2021
Consider a dynamic hashing approach for 4-bit integer keys:
There is a main hash table of size 4.
The 2 least significant bits of a key is used to index into the main hash table.
Initially, the main hash table entries are empty.
Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.
A split is done only if it is needed, i.e., only when there is a collision.
Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
- A.
5,9,4,13,10,7
- B.
9,5,10,6,7,1
- C.
10,9,6,7,5,13
- D.
9,5,13,6,10,14
Attempted by 73 students.
Show answer & explanation
Correct answer: C
Key insight: index by the 2 least significant bits (b1b0). On collision, split that bucket by the 3rd LSB (b2). If two keys still collide in the same node, split that node by the 4th LSB (b3).
Insert 10 (1010): goes to index 10; bucket 10 stores 10.
Insert 9 (1001): goes to index 01; bucket 01 stores 9.
Insert 6 (0110): collides with 10 at index 10. Split by b2: 10 (b2=0) to left, 6 (b2=1) to right.
Insert 7 (0111): goes to index 11; bucket 11 stores 7.
Insert 5 (0101): collides with 9 at index 01. Split by b2: 9 (b2=0) becomes left child, 5 (b2=1) becomes right child.
Insert 13 (1101): goes to index 01 and collides with 5 in the right child (both have b2=1). Split that node by b3: 5 (b3=0) left, 13 (b3=1) right.
Final bucket contents (matching the picture):
00: empty
01: root with left leaf 9; right child split into leaves 5 (left) and 13 (right)
10: root split by b2 into left 10 and right 6 (both leaves)
11: single leaf 7
Therefore the sequence 10,9,6,7,5,13 yields the shown state; the other sequences either place a key in bucket 00 or cause additional splits that do not appear in the picture.
A video solution is available for this question — log in and enroll to watch it.