Question

Program in C++

**********Write a program to compute the number of collisions required in a long random sequence of insertions using linear probing, quadratic probing and double hashing. For simplicity, only integers will be hashed and the hash function h(x) = x % D where D is the size of the table (fixed size of 1001). The simulation should continue until the quadratic hashing fails.*********

Answer 1

1. Linear Probing

#include<iostream>

using namespace std;

int main()

{
const int MAX_SIZE = 11;
int collisions = 0;
int array[MAX_SIZE];
bool flags[MAX_SIZE];

for (int i = 0; i < MAX_SIZE; i++)
{
array[i] = 0;
flags[i] = false;

}

//<Inserting numbers in hash table using linear probing
Linear_Probing(array, flags, MAX_SIZE, 67, collisions);
Linear_Probing(array, flags, MAX_SIZE, 19, collisions);
Linear_Probing(array, flags, MAX_SIZE, 3, collisions);
Linear_Probing(array, flags, MAX_SIZE, 808, collisions);
Linear_Probing(array, flags, MAX_SIZE, 337, collisions);
Linear_Probing(array, flags, MAX_SIZE, 1, collisions);
Linear_Probing(array, flags, MAX_SIZE, 86, collisions);
Linear_Probing(array, flags, MAX_SIZE, 38, collisions);

return 0;
}

bool Linear_Probing(int array[], bool flags[], int MAX_SIZE, int number, int &collisions)
{
int dummy_collisions = 0;
int index = Index_Finder(number, flags, MAX_SIZE, dummy_collisions);

if (index == -1)
return false;

else
{
collisions += dummy_collisions;

array[index] = number;
flags[index] = true;
return true;
}
}

int Index_Finder(int number, bool flags[], int MAX_SIZE, int &collisions)
{
int index = Hash(number);

if (index < MAX_SIZE && !flags[index])
return index;

if (index >= MAX_SIZE)
{
index = 0;

if (!flags[index])
return index;

else
collisions++;
}

else
{
collisions++;
}

int limit = index;

return Index_Finder(flags, MAX_SIZE, ++index, limit, collisions);

}

int Index_Finder(bool flags[], int MAX_SIZE, int index, int limit, int &collisions)
{
if (limit == index)
return -1;

if (index == MAX_SIZE)
index = 0;

if (!flags[index])
return index;

else
{
collisions++;
return Index_Finder(flags, MAX_SIZE, ++index, limit, collisions);
}
}

int Hash(int number)
{
int first_digit = 0, last_digit = 0;
bool first_time = true;

while (number > 0)
{
if (first_time)
{
first_digit = number % 10;
number -= (number % 10);
number /= 10;
first_time = false;
}

else
{
last_digit = number % 10;
number -= (number % 10);
number /= 10;
}
}

return (first_digit + last_digit);
}

2. Quadratic Probing

#include <iostream>
#include <cstdlib>
#define MIN_TABLE_SIZE 10
using namespace std;

enum EntryType {Legitimate, Empty, Deleted};

struct HashNode
{
int element;
enum EntryType info;
};

struct HashTable
{
int size;
HashNode *table;
};

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;
}

int nextPrime(int n)
{
if (n <= 0)
n == 3;
if (n % 2 == 0)
n++;
for (; !isPrime( n ); n += 2);
return n;
}
int HashFunc(int key, int size)
{
return key % size;
}

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;
}
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;
}
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;
}
}

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;
}
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;
else
cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
}

}

int main()
{
int value, size, pos, i = 1;
int choice;
HashTable *htable;
while(1)
{
cout<<"Operations on Quadratic Probing"<<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;
}

3. Double Hashing

#include <iostream>
#define MIN_TABLE_SIZE 11
using namespace std;

enum EntryType {Legitimate, Empty, Deleted};

struct HashNode
{
int element;
enum EntryType info;
};

struct HashTable
{
int size;
HashNode *table;
};

int HashFunc1(int key, int size)
{
return key % size;
}

int HashFunc2(int key, int size)
{
return (key * size - 1) % size;
}

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;
}

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;
}

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;
}
}

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;
}

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;
else
cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
}

}

int main()
{
int value, size, pos, i = 1;
int choice;
HashTable *htable;
while(1)
{
cout<<"Operations on Double Hashing"<<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;
}