COS 226 Exercises on Hashing

NAME:

LOGIN:

PRECEPT:

1. [Exercise 14.17] Give the contents of the hash table that results when you insert items with the keys D E M O C R A T in that order into an initially empty table of M = 5 lists, using separate chaining with unordered lists. Use the hash function 11 k mod M to transform the kth letter of the alphabet into a table index, e.g., hash(I) = hash(9) = 99 % 5 = 4.

2. [Exercise 14.25] Give the contents of the hash table that results when you insert items with the keys R E P U B L I C A N in that order into an initially empty table of size M = 16 using linear probing. Use the hash function 11k mod M to transform the kth letter of the alphabet into a table index.

3. [Exercise 14.32] Give the contents of the hash table that results when you insert items with the keys A N O T H E R X M P L in that order into an initially empty table of size M = 16 using double hashing. Use the hash function 11k mod M for the inital probe and the second hash function (k mod 3) + 1 for the search increment.