Data Structures and Algorithms II

Homework 4

1. Assume an integer key k is to be hashed to a table with n slots (numbered 0..n-1). Open hashing is being used to resolve collisions. For each of the following hash functions, answer these questions:

a) Is it usable (i.e. will it work to perform inserts and finds)?
b) Is it a 'good' hash function (explain why or why not)?

h1(k) = k/n;
h2(k) = 0;
h3(k) = (k + rand(n)) % n; //rand(n) returns a random integer in the range 0..n-1
h4(k) = k % n;

2. Assume closed hashing is being used and the table size is 11. Show the contents of the table after inserting the integer keys in the sequence given using the indicated collision resolution technique. Assume the table contains just the key itself and leave the unused table locations blank. The hash function being used is h(k) = (k*2)%11;

Insert 16, 6, 27, 17, 4 using linear resolution: p(k,i) = h(k) + i;

Insert 2, 14, 24, 3 using quadratic resolution: p(k,i) = h(k) + i*i;

Insert 6, 17, 28, 39 using double hashing resolution: p(k,i) = h(k) + i*h2(k); //h2(k)=k%5)

Insert 6, 17, 28, 39 using double hashing resolution: p(k,i) = h(k) + i*h(k*k+1);

3. Complete the public hash function in the Customer class:

class Customer{
private:
  char * custName; //guaranteed to be a pointer to a valid string
  int custNumber;
public:
  int hash(int tablesize){
     //add ascii values of custName, perform exclusive-or with custNumber, mod by tablesize
  }
//other stuff that is not relevant to problem
};