This C++ Program demonstrates operations on Hash Tables with Double Hashing.
Here is source code of the C++ Program to demonstrate Hash Tables with Double Hashing. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
/** C++ Program to Implement Hash Tables with Double Hashing*/#include <iostream>#include <cstdlib>#define MIN_TABLE_SIZE 10using namespace std;
/** Node Type Declaration*/enum EntryType {Legitimate, Empty, Deleted};
/** Node Declaration*/struct HashNode{int element;
enum EntryType info;
};
/** Table Declaration*/struct HashTable{int size;
HashNode *table;
};
/** Function to Genereate First Hash*/int HashFunc1(int key, int size)
{return key % size;
}/** Function to Genereate Second Hash*/int HashFunc2(int key, int size)
{return (key * size - 1) % size;
}/** Function to Initialize Table*/HashTable *initializeTable(int size)
{HashTable *htable;
if (size < MIN_TABLE_SIZE)
{cout<<"Table Size Too Small"<<endl;
return NULL;
}htable = new HashTable;
if (htable == NULL)
{cout<<"Out of Space"<<endl;
return NULL;
}htable->size = size;
htable->table = new HashNode [htable->size];
if (htable->table == NULL)
{cout<<"Table Size Too Small"<<endl;
return NULL;
}for (int i = 0; i < htable->size; i++)
{htable->table[i].info = Empty;
htable->table[i].element = NULL;
}return htable;
}/** Function to Find Element from the table*/int Find(int key, HashTable *htable)
{int hashVal= HashFunc1(key, htable->size);
int stepSize= HashFunc2(key, htable->size);
while (htable->table[hashVal].info != Empty &&
htable->table[hashVal].element != key)
{hashVal = hashVal + stepSize;
hashVal = hashVal % htable->size;
}return hashVal;
}/** Function to Insert Element into the table*/void Insert(int key, HashTable *htable)
{int pos = Find(key, htable);
if (htable->table[pos].info != Legitimate )
{htable->table[pos].info = Legitimate;
htable->table[pos].element = key;
}}/** Function to Rehash the table*/HashTable *Rehash(HashTable *htable)
{int size = htable->size;
HashNode *table = htable->table;
htable = initializeTable(2 * size);
for (int i = 0; i < size; i++)
{if (table[i].info == Legitimate)
Insert(table[i].element, htable);
}free(table);
return htable;
}/** Function to Retrieve the table*/void Retrieve(HashTable *htable)
{for (int i = 0; i < htable->size; i++)
{int value = htable->table[i].element;
if (!value)
cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
elsecout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
}}/** Main Contains Menu*/int main()
{int value, size, pos, i = 1;
int choice;
HashTable *htable;
while(1)
{cout<<"\n----------------------"<<endl;
cout<<"Operations on Double Hashing"<<endl;
cout<<"\n----------------------"<<endl;
cout<<"1.Initialize size of the table"<<endl;
cout<<"2.Insert element into the table"<<endl;
cout<<"3.Display Hash Table"<<endl;
cout<<"4.Rehash The Table"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{case 1:
cout<<"Enter size of the Hash Table: ";
cin>>size;
htable = initializeTable(size);
break;
case 2:
if (i > htable->size)
{cout<<"Table is Full, Rehash the table"<<endl;
continue;
}cout<<"Enter element to be inserted: ";
cin>>value;
Insert(value, htable);
i++;
break;
case 3:
Retrieve(htable);
break;
case 4:
htable = Rehash(htable);
break;
case 5:
exit(1);
default:
cout<<"\nEnter correct option\n";
}}return 0;
}
$ g++ Double_Hashing.cpp $ a.out ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 1 Enter size of the Hash Table: 5 Table Size Too Small ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 1 Enter size of the Hash Table: 10 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 3 Position: 1 Element: Null Position: 2 Element: Null Position: 3 Element: Null Position: 4 Element: Null Position: 5 Element: Null Position: 6 Element: Null Position: 7 Element: Null Position: 8 Element: Null Position: 9 Element: Null Position: 10 Element: Null ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 10 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 20 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 30 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 40 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 50 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 60 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 70 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 80 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 90 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 100 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Table is Full, Rehash the table ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 3 Position: 1 Element: 10 Position: 2 Element: 100 Position: 3 Element: 90 Position: 4 Element: 80 Position: 5 Element: 70 Position: 6 Element: 60 Position: 7 Element: 50 Position: 8 Element: 40 Position: 9 Element: 30 Position: 10 Element: 20 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 4 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 3 Position: 1 Element: 100 Position: 2 Element: Null Position: 3 Element: Null Position: 4 Element: Null Position: 5 Element: Null Position: 6 Element: Null Position: 7 Element: 30 Position: 8 Element: 50 Position: 9 Element: 70 Position: 10 Element: 90 Position: 11 Element: 10 Position: 12 Element: Null Position: 13 Element: Null Position: 14 Element: Null Position: 15 Element: Null Position: 16 Element: Null Position: 17 Element: 20 Position: 18 Element: 40 Position: 19 Element: 60 Position: 20 Element: 80 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 1000 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 2000 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 3000 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 4000 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 5000 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 3 Position: 1 Element: 100 Position: 2 Element: Null Position: 3 Element: Null Position: 4 Element: Null Position: 5 Element: Null Position: 6 Element: Null Position: 7 Element: 30 Position: 8 Element: 50 Position: 9 Element: 70 Position: 10 Element: 90 Position: 11 Element: 10 Position: 12 Element: 5000 Position: 13 Element: 4000 Position: 14 Element: 3000 Position: 15 Element: 2000 Position: 16 Element: 1000 Position: 17 Element: 20 Position: 18 Element: 40 Position: 19 Element: 60 Position: 20 Element: 80 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 6000 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 3 Position: 1 Element: 100 Position: 2 Element: Null Position: 3 Element: Null Position: 4 Element: Null Position: 5 Element: Null Position: 6 Element: 6000 Position: 7 Element: 30 Position: 8 Element: 50 Position: 9 Element: 70 Position: 10 Element: 90 Position: 11 Element: 10 Position: 12 Element: 5000 Position: 13 Element: 4000 Position: 14 Element: 3000 Position: 15 Element: 2000 Position: 16 Element: 1000 Position: 17 Element: 20 Position: 18 Element: 40 Position: 19 Element: 60 Position: 20 Element: 80 ---------------------- Operations on Double Hashing ---------------------- 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 5 ------------------ (program exited with code: 1) Press return to continue
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
If you find any mistake above, kindly email to [email protected]Related Posts:
- Check Programming Books
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Programming MCQs
- Practice Computer Science MCQs
