Question

Consider an extendible hashing structure where: a. Initially each bucket can hold up to 3 records. b. The directory is an array of Size 4. Now, construct the extendible hashing structure by inserting the keys 2, 3, 7, 14, 15, 18, 20, 26, 27 (in this order). Start by using the lowest 2 bits for the hash function. Show each step. (10 pts)

Answer 1

step1:Taking the binary values

2 - 00010

3 - 00011

7 - 00111

14 - 01110

15 - 01111

18 - 10010

20 - 10100

26 - 11000

27 - 11001

Step 2; one by one, add the numbers to each of the bucket based on the last 2 BINARY digits,( 2 LSB).

See attached picture for structure.