This C++ Program demonstrates operations on Hash Tables with Quadratic Probing.
Here is source code of the C++ Program to demonstrate Hash Tables with Quadratic Probing. 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 Quadratic Probing*/#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;
};
/** Returns whether n is prime or not*/bool isPrime (int n)
{if (n == 2 || n == 3)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}/** Finding next prime size of the table*/int nextPrime(int n)
{if (n <= 0)
n == 3;
if (n % 2 == 0)
n++;
for (; !isPrime( n ); n += 2);
return n;
}/** Function To Generate Hash*/int HashFunc(int key, int size)
{return key % 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 = nextPrime(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 at a key*/int Find(int key, HashTable *htable)
{int pos = HashFunc(key, htable->size);
int collisions = 0;
while (htable->table[pos].info != Empty &&
htable->table[pos].element != key)
{pos = pos + 2 * ++collisions -1;
if (pos >= htable->size)
pos = pos - htable->size;
}return pos;
}/** Function to Insert Element into a key*/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 Hash 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 Quadratic Probing"<<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);
cout<<"Size of Hash Table: "<<nextPrime(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;
}
advertisement
$ g++ Quadratic_Probing.cpp $ a.out ---------------------- Operations on Quadratic Probing ---------------------- 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 Size of Hash Table: 5 ---------------------- Operations on Quadratic Probing ---------------------- 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 Size of Hash Table: 11 ---------------------- Operations on Quadratic Probing ---------------------- 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 Quadratic Probing ---------------------- 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: 200 ---------------------- Operations on Quadratic Probing ---------------------- 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: 300 ---------------------- Operations on Quadratic Probing ---------------------- 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: 400 ---------------------- Operations on Quadratic Probing ---------------------- 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: 500 ---------------------- Operations on Quadratic Probing ---------------------- 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: 600 ---------------------- Operations on Quadratic Probing ---------------------- 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: 700 ---------------------- Operations on Quadratic Probing ---------------------- 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: 800 ---------------------- Operations on Quadratic Probing ---------------------- 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: 900 ---------------------- Operations on Quadratic Probing ---------------------- 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 Quadratic Probing ---------------------- 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: 1100 ---------------------- Operations on Quadratic Probing ---------------------- 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 Quadratic Probing ---------------------- 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: 1100 Position: 2 Element: 100 Position: 3 Element: 200 Position: 4 Element: 300 Position: 5 Element: 400 Position: 6 Element: 500 Position: 7 Element: 600 Position: 8 Element: 700 Position: 9 Element: 800 Position: 10 Element: 900 Position: 11 Element: 1000 ---------------------- Operations on Quadratic Probing ---------------------- 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 Quadratic Probing ---------------------- 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: 300 Position: 3 Element: 600 Position: 4 Element: 900 Position: 5 Element: Null Position: 6 Element: Null Position: 7 Element: Null Position: 8 Element: Null Position: 9 Element: 100 Position: 10 Element: 400 Position: 11 Element: 700 Position: 12 Element: 1000 Position: 13 Element: Null Position: 14 Element: Null Position: 15 Element: Null Position: 16 Element: Null Position: 17 Element: 200 Position: 18 Element: 500 Position: 19 Element: 800 Position: 20 Element: 1100 Position: 21 Element: Null Position: 22 Element: Null Position: 23 Element: Null ---------------------- Operations on Quadratic Probing ---------------------- 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: 2200 ---------------------- Operations on Quadratic Probing ---------------------- 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: 3300 ---------------------- Operations on Quadratic Probing ---------------------- 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: 4400 ---------------------- Operations on Quadratic Probing ---------------------- 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: 5500 ---------------------- Operations on Quadratic Probing ---------------------- 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: 6600 ---------------------- Operations on Quadratic Probing ---------------------- 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: 300 Position: 3 Element: 600 Position: 4 Element: 900 Position: 5 Element: 5500 Position: 6 Element: Null Position: 7 Element: Null Position: 8 Element: 4400 Position: 9 Element: 100 Position: 10 Element: 400 Position: 11 Element: 700 Position: 12 Element: 1000 Position: 13 Element: 3300 Position: 14 Element: Null Position: 15 Element: Null Position: 16 Element: 2200 Position: 17 Element: 200 Position: 18 Element: 500 Position: 19 Element: 800 Position: 20 Element: 1100 Position: 21 Element: Null Position: 22 Element: Null Position: 23 Element: 6600 ---------------------- Operations on Quadratic Probing ---------------------- 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
If you wish to look at all C++ Programming examples, go to C++ Programs.