CS 334: Extendable hashing

Suppose that we are using extendable hashing on a file that contains records with the following search-key values, inserted in the following order:

1, 5, 4, 6, 12, 3, 20, 14, 28, 6

Suppose further that the hash function is \(h(x) = x + 1\), that our extendable hash table starts off empty, and that each block in the index can hold 3 search keys. Draw the structure of the final hash table in a similar fashion to how we have done so in class. Don't use an approach based on binary digits based on most significant bits as the textbook does; rather, use a modular arithmetic approach based on least significant bits as we have (eventually) done in class. Submit your work on paper.

Optional work if you're looking for excitement: don't do this by hand. Code up an extendable hash table, and print it out.

Yes, this is a pretty silly hash function. I just wanted to pick something easy that wasn't the identity.