Question

Consider a dynamic hashing approach for 4-bit integer keys: 

1. There is a main hash table of size 4.
2. The 2 least significant bits of a key are used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. To resolve collisions, the set of keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
5. First, the 3^rd least significant bit is used to divide the keys into left and right subtrees.
6. Further collisions are resolved by subdividing based on the 4^th least significant bit.
7. A split is done only if needed, i.e., only when there is a collision.

Consider the following state of the hash table. 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

Hint:

In dynamic hashing, carefully track which bits are used at each level and remember that splits occur only when collisions arise.

Answer 1

The Correct Option is C

Step 1: Identify the main hash table index.
The index is determined by the 2 least significant bits (LSBs) of each key. Thus, keys are grouped based on their binary endings:
\[ 00,\; 01,\; 10,\; 11 \]

Step 2: Analyze the given final hash table state.
From the figure: \[\begin{array}{rl} \bullet & \text{Index \texttt{00} is empty.} \\ \bullet & \text{Index \texttt{01} has a binary tree with further splits using the 3rd and 4th LSBs.} \\ \bullet & \text{Index \texttt{10} has a binary tree with splits.} \\ \bullet & \text{Index \texttt{11} has exactly one key.} \\ \end{array}\]
This means that multiple keys mapped to indices \texttt{01} and \texttt{10}, causing hierarchical splits, while only one key mapped to \texttt{11}.

Step 3: Check option (C).
Keys in option (C): \(10, 9, 6, 7, 5, 13\). Their 4-bit binary representations are:
\[ \begin{aligned} 10 &= 1010 \;(\texttt{10})
9 &= 1001 \;(\texttt{01})
6 &= 0110 \;(\texttt{10})
7 &= 0111 \;(\texttt{11})
5 &= 0101 \;(\texttt{01})
13 &= 1101 \;(\texttt{01}) \end{aligned} \]
Thus: \[\begin{array}{rl} \bullet & \text{Index \texttt{01}: 9, 5, 13 \(\Rightarrow\) multiple collisions and deeper splits.} \\ \bullet & \text{Index \texttt{10}: 10, 6 \(\Rightarrow\) collision and split.} \\ \bullet & \text{Index \texttt{11}: 7 \(\Rightarrow\) single key.} \\ \bullet & \text{Index \texttt{00}: none.} \\ \end{array}\] This exactly matches the shown hash table structure.

Step 4: Eliminate other options.
The remaining options either populate index \texttt{00}, or distribute keys in a way inconsistent with the given tree structures.

Step 5: Conclusion.
Only option (C) produces the illustrated dynamic hashing state.

Final Answer: (C)