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 page 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. Use the least significant bits of the hash value as we have discussed in class, not the most significant bits as shown in the textbook. Submit your answer on paper in class.
Optional work if you're looking for excitement: don't do this by hand. Code up an extendable hash table, and print it out to the screen.
Yes, this is a pretty silly hash function. I just wanted to pick something easy that wasn't the identity to illustrate that hash functions can vary.