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. Don't use an approach based on binary digits as the textbook does; rather, use a modular arithmetic approach as we have done in class. (Both are the same if you use the least significant digits of a binary representation, but they come out different if you use the most signficant digits. Submit your answer electronically as a PDF. You can generate it with drawing software, or you carefully and neatly write it, and then scan it. (Note: updated on 10/28 to indicate submission methodology.)

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.