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 primary hashing rule.
The hash table uses the two least significant bits (LSBs) of each key to determine the initial directory index. Hence, the four possible indices are: \[ 00,\; 01,\; 10,\; 11 \]

Step 2: Interpret the final hash table structure. 
From the given figure, we observe:

\[ \begin{array}{rl} \bullet & \text{Index \texttt{00} is empty.} \\ \bullet & \text{Index \texttt{01} contains multiple keys and has grown into a binary tree using additional LSBs.} \\ \bullet & \text{Index \texttt{10} also contains multiple keys and shows further splitting.} \\ \bullet & \text{Index \texttt{11} contains exactly one key.} \end{array} \]

This implies that:

• Several keys hash to 01 and 10, causing collisions and deeper splits.
• Exactly one key hashes to 11.
• No key hashes to 00.

 

Step 3: Evaluate Option (C).
Option (C) contains the keys: \[ \{10, 9, 6, 7, 5, 13\} \] Their 4-bit binary forms and 2-LSB indices 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} \]

So the distribution is:

\[ \begin{array}{rl} \bullet & \text{Index \texttt{01}: 9, 5, 13 \;(\text{multiple keys} \Rightarrow \text{tree growth})} \\ \bullet & \text{Index \texttt{10}: 10, 6 \;(\text{collision} \Rightarrow \text{split})} \\ \bullet & \text{Index \texttt{11}: 7 \;(\text{single key})} \\ \bullet & \text{Index \texttt{00}: \text{no keys}} \end{array} \]

This distribution exactly matches the structure shown in the hash table.

Step 4: Reject other options.
All other options either:

• Place at least one key in index 00, or
• Fail to create the required collisions in indices 01 and 10.

Hence, they do not match the given final state.

 

Final Answer:
(C)