Hashing Review Exercises

1. Suppose you are hashing keys k to a hash table of n>=2 slots. For each hash function h(k) below, tell if it is i)acceptable (that is, will it work for both insertions and searches), and ii) good (that is, will it distribute keys relative uniformly). Assume that random(n) returns a random integer in the range 0..n-1.
   1. h(k) = k/n (assumes k integer)

      
      

   2. h(k) = 1

      
      

   3. h(k) = (k + random(n))%n

      
      

   4. h(k) = k % n

      
      

2. Using closed hashing and linear probing to resolve collisions with hash function h(k) = k mod 7, and given a table size of 7, show the hash table after inserting the keys 3, 12, 9, 2. Then for each empty slot, give the probability that it will be the next one filled.

   
   
   
   
   
   
   
   
   

3. Using closed hashing and resolving collisions with double hashing using hash functions h1 and h2 below, and given a table size of 13, show the hash table after the eight keys below have been inserted. Function reverse(k) reverses the decimal digits of k, so reverse(73)=37, reverse(7)=7. Show your work.

   h1(k) = k mod 13     h2(k) = reverse(k+1) mod 11
   
   keys: 2, 8, 31, 20, 19, 18, 53, 27.