Consider a dynamic hashing approach for 64-bit integer keys:
1. There is a main hash table of size 4.
2. The least signi...

Question

Consider a dynamic hashing approach for 64-bit integer keys:
1. There is a main hash table of size 4.
2. The least significant 2 bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. 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.
5. The 3rd least significant bit is used to divide the keys into left and right subtrees.
6. 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.
7. A split is done only if it is needed, i.e., only when there is a collision.

Consider the following state of the hash table.
[The hash table has: slot 0b00 -> a binary tree with 5,9,13,7 arranged; slot 0b10 -> contains 10; slot 0b01 and 0b11 are empty]

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, 13, 10, 7, 5, 13
C. 10, 9, 7, 5, 13
D. 5, 9, 13, 6, 14, 10, 14

Accepted Answer

C. 10, 9, 7, 5, 13 This question uses a tree-based dynamic hashing. The 2 least significant bits of a key index into a main table of 4 slots. Collisions at any slot are resolved by building a binary tree: the 3rd bit splits left/right at level 1, and the 4th bit splits left/right at level 2. Only split when there is a collision - if a slot is empty just store one key.