You need to write two hash functions (both returning integers)

h_1(k) = k mod m

h_2(k) = m * frac(k*A), A = (sqrt(5) 1)/2

frac(k*A) = (k*A int (k*A))

Also define a rehash function as below:

rehash(int h, int k, int j)

return (h + j * g(k, j) ) mod m

The g function is defined as:

g(int k, int j)

if option == 1, return 1

else if option == 2, return c1 + c2* j

else if option == 3, return (p (k mod p) ) , p is an user input

Program should create a hash table as explained in the class.

Declare as global variables:

m (size of Hash Table)

option (will allow you to choose one of the three collision resolving technique),

hash_method (1 for using division method and 2 for multiplication method)

p (int)

c1, c2 (int)

In main, declare n (integer) and alpha (as float), alpha = n/m

Both n and alpha are user inputs

Also, option and hash_method are user inputs.

Get inputs for C1, C2 and p

Compute m = (n/alpha)

Check is m is a prime number, call ISPrime function

If not, If not a prime, call GetPrime to get the value of next higher prime value.

if (IsPrime(m))

display m , m is a prime no.

else

m = GetPrime(m);

display m

Create an array dynamically for hashTable with size m

Initialize all the values of this array to 0 (assuming no key will be 0)

Now using a loop enter n number of keys, and one key (k) at a time, and inside this loop, compute the h value first, by calling either h_1(k) or h_2(k) depending on the value of hash_method

For(count = 1; count <= n; count++)

{ cin >> k;

Set h = h_1(k) or h_2(k), depending on hash_method is 1 or 2

I = h

if hashTable[I] != 0, then

j = 0

do

J++

I = rehash(h, k, j)

while hashTable[I] != 0

end if

hashTable[I] = k

}

Display the HashTable

Cout << setw(10) << left << Index << setw(10) << left << Key << endl;

For(I = 0 ; I <= m-1 ; I++)

cout << setw(10) << left << I << setw(10) << left << hashTable[I] << endl;

bool IsPrime(int x)

{

int k = x/2;

int i;

for(i = 2; i <= k; i++)

{

if (x % i == 0) return false;

}

return true;

}

int GetPrime(int x)

{

int i;

for(i = x+1; i <= INT_MAX; i++) climits as a header file

{

if(IsPrime(i)) return i;

}

return 1;

}