The GATE Grind

GATE 2021 CS – Question 57

Databases · File Organization and Indexing (B and B+ Trees) · 2 marks · Multiple select

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) 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) First, 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. The final hash table state is: entry 00 empty; entry 01: root splits on bit 3 into a leaf (bit 0) and an internal node (bit 1) which splits into two leaves; entry 10: root splits into two leaves; entry 11: a single leaf. Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

  1. 5, 9, 4, 13, 10, 7
  2. 9, 5, 10, 6, 7, 1
  3. 10, 9, 6, 7, 5, 13
  4. 9, 5, 13, 6, 10, 14

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 10, 9, 6, 7, 5, 13

Explanation

Bucket 01 needs keys 9 (bit3=0), and 5 and 13 (bit3=1, split on bit4). Bucket 10 needs 10 and 6 (differing in bit3), and bucket 11 needs one key, 7. Sequence C gives exactly this. Others put keys in bucket 00 or too many keys elsewhere.