Question

Using 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.

Answer 1

linear probing function:

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int TABLE_SIZE = 5;

class hashnodes
{
public:
int key;
int value;
hashnodes(int key, int value)
{
this->key = key;
this->value = value;
}
};

class delnodes:public hashnodes
{
private:
static delnodes *entry;
delnodes():hashnodes(-1, -1)
{}
public:
static delnodes *getNode()
{
if (entry == NULL)
entry = new delnodes();
return entry;
}
};
delnodes *delnodes::entry = NULL;

class HashMap
{
private:
hashnodes **htable;
public:
HashMap()
{
htable = new hashnodes* [TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
{
htable[i] = NULL;
}
}

~HashMap()
{
for (int i = 0; i < TABLE_SIZE; i++)
{
if (htable[i] != NULL && htable[i] != delnodes::getNode())
delete htable[i];
}
delete[] htable;
}

int HashFunc(int key)
{
return key % TABLE_SIZE;
}

void Insert(int key, int value)
{
int hash_val = HashFunc(key);
int init = -1;
int deletedindex = -1;
while (hash_val != init && (htable[hash_val]
== delnodes::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
if (htable[hash_val] == delnodes::getNode())
deletedindex = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
{
if(deletedindex != -1)
htable[deletedindex] = new hashnodes(key, value);
else
htable[hash_val] = new hashnodes(key, value);
}
if(init != hash_val)
{
if (htable[hash_val] != delnodes::getNode())
{
if (htable[hash_val] != NULL)
{
if (htable[hash_val]->key == key)
htable[hash_val]->value = value;
}
}
else
htable[hash_val] = new hashnodes(key, value);
}
}
  
int search(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val]
== delnodes::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
return -1;
else
return htable[hash_val]->value;
}

void remove(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val]
== delnodes::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hash_val != init && htable[hash_val] != NULL)
{
delete htable[hash_val];
htable[hash_val] = delnodes::getNode();
}
}
};

int main()
{
HashMap hash;
int key, value;
int choice;
while(1)
{

cout<<"Operations on Hash Table"<<endl;

cout<<"1.Insert an element into the table"<<endl;
cout<<"2.search an element from the key"<<endl;
cout<<"3.Delete an element at a key"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element to be inserted: ";
cin>>value;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
hash.Insert(key, value);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>key;
if(hash.search(key) == -1)
{
cout<<"No element found at key "<<key<<endl;
continue;
}
else
{
cout<<"Element at key "<<key<<" : ";
cout<<hash.search(key)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>key;
hash.remove(key);
break;
case 4:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}

--------------------------------

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 a size of the table"<<endl;
cout<<"2.Insert an element into the table"<<endl;
cout<<"3.Display the 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 the 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 the correct option\n";
}
}
return 0;
}

--------------------

double hashing

------------

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

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 the size of the table"<<endl;
cout<<"2.Insert an 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;
}