April 7, 2004

**Name:**________________________________________

- (2 pts)
Consider a hash table where collisions are resolved
with chaining. Under what conditions do the operations
of insert, search and delete take constant expected time?

- (1 pt)
Consider a hash table using chaining where M = 5, h(k) = k mod 5, and
the keys 1, 5, 11, 15 are inserted, in that order, into
an initially empty hash table. Draw the result.

- (1 pt)
Consider a hash table using open addressing with linear probing
where M = 5, h(k) = k mod 5, and
the keys 1, 5, 11, 15 are inserted, in that order, into
an initially empty hash table. Draw the result.

- (1 pt) What is double hashing?