Name:________________________________________

1. (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?
   
   
   
   
   
   
   
   
2. (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.
   
   
   
   
   
   
   
   
   
   
3. (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.
   
   
   
   
   
   
   
   
   
4. (1 pt) What is double hashing?