Data Structure and Algorithm

/**********************************************
APPLICATION : Collision Resolution Technique : Double Hashing
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE         : 2010 - October - 22
***********************************************/

#include <iostream.h>
#include <conio.h>

int main()
{
int tb_size,size,resize,key,n,address,*arr,temp;
cout << "Collision Resolution Technique : Double Hashing,";
cout << "\nThe Hash Function is Key%H1_Size and Key%H2_Size,";
cout << "\nThe Table Size must be atleast two times H1_Size and H2_size.";
cout << "\n\nEnter Table Size : ";
cin >> tb_size;
arr = new int[tb_size];
for(int i = 0;i < tb_size;i++)
  arr[i] = -1;
cout << "\nEnter Size for First Hash Function (H1_Size) : ";
cin >> size;
cout << "\nEnter Size for Second Hash Function(H2_Size) : ";
cin >> resize;

cout << endl << "How Many Items? ";
cin >> n;
cout << endl << "Enter " << n << " Keys\n";
for(int i = 0;i < n;i++)
  {
   int j = 1;
   cin >> key;
   address = key%size;
   cout << "\nH(" << key << '%' << size << ") = " << address;
   if(arr[address] == -1)
    arr[address] = key;
   else
    {
     int h = key%resize; //Calculate address using second Hash Function
     temp = address;
     while(arr[temp] != -1)
     {
      cout << "\t(Collision occurs, Rehash required)\n";
      temp = address + j*h; //find address
      cout << "  H' = " << address << '+' << (j*h) << " = " << temp;
      if(temp >= size)
       temp = temp - size;
      j++;
     }
     address = temp;
     arr[address] = key; //insert key
    }
  }

cout << "\n\nHash Table\n";
cout << "----------";
cout << endl << endl;
for(int i = 0;i < tb_size;i++)
  {
   if(arr[i] != -1)
    cout << i << '\t' << arr[i] << endl;
   else
    cout << i << '\t' << endl;
  }

getch();
return 0;
}

OUTPUT

Collision Resolution Technique : Double Hashing,
The Hash Function is Key%H1_Size and Key%H2_Size,
The Table Size must be atleast two times H1_Size and H2_Size.

Enter Table Size : 25

Enter Size for First Hash Fucntion (H1_Size) : 13

Enter Size for Second Hash Fucntion (H2_Size) : 11

How Many Items? 11

Enter 11 Keys
25 46 75 29 36 53 68 89 117 120 140

H(25%13) = 12
H(46%13) = 7
H(75%13) = 10
H(29%13) = 3
H(36%13) = 10    (Collision occurs, Rehash required)
  H' = 10+3 = 13
H(53%13) = 1
H(68%13) = 3    (Collision occurs, Rehash required)
  H' = 3+2 = 5
H(89%13) = 11
H(117%13) = 0 
H(120%13) = 3    (Collision occurs, Rehash required)
  H' = 3+10 = 13  (Collision occurs, Rehash required)
  H' = 3+20 = 23 
H(140%13) = 10    (Collision occurs, Rehash required)
  H' = 10+8 = 18   

Hash Table

0    117
1    53
2   
3    29
4   
5    68
6   
7    46
8   
9
10    75
11    89
12    25
13    36
14
15
16
17
18    140
19
20   
21
22
23    120
24

Double Hashing.cpp