### 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 *k*th 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
11*k* mod *M* to transform the *k*th 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
11*k* mod *M* for the inital probe and the second hash function
(*k* mod 3) + 1 for the search increment.