COS 226 Exercises on Hashing

NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Hashing

References: Section 4.4 in Algorithms, 4th edition

1. Give the contents of the hash table that results when you insert the following keys in that order into an initially empty table of M = 5 lists, using separate chaining with unordered lists. Use the hash function 11k mod M to transform the kth letter of the alphabet into a table index, e.g., hash(I) = hash(9) = 99 % 5 = 4. Use the conventions from Chapter 4.4 (new key-value pairs are inserted at the beginning of the list).

D E M O C R A T S

2. Give the contents of the hash table that results when you insert the following keys 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.

R E P U B L I C A N S