Code:
#include iostream
#include cstdlib
#define MIN_TABLE_SIZE 10
using 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"<
return NULL;
}
htable = new HashTable;
if (htable == NULL)
{
cout<<"Out of Space"<
return NULL;
}
htable->size = size;
htable->table = new HashNode [htable->size];
if (htable->table == NULL)
{
cout<<"Table Size Too Small"<
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: "<
else
cout<<"Position: "<
}
}
/*
* Main Contains Menu
*/
int main()
{
int value, size, pos, i = 1;
int choice;
HashTable *htable;
while(1)
{
cout<<"\n----------------------"<
cout<<"Operations on Double Hashing"<
cout<<"\n----------------------"<
cout<<"1.Initialize size of the table"<
cout<<"2.Insert element into the table"<
cout<<"3.Display Hash Table"<
cout<<"4.Rehash The Table"<
cout<<"5.Exit"<
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"<
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;
}
Output:
----------------------
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
More C++ Programs:
