Question

Design a hashtable with fundamental operations by using two types of hashing and collision avoidance. (a) Design two types of hashing, the first is a simple hash that can be completed with O(1), but it may cause collisions; the second hash is a double hash can be completed with O(1). Put the details of your hash function and analysis in codes comments. (b) When your first hash function has collisions, using separate chaining to solve the collision.

Answer 1

CODE:-

#include <bits/stdc++.h>
using namespace std;
class singlehash{
//Key is added in the Hash table
//Index to which a key is stored is decide via hash function
//defined in line index = hash(key ) => index = key % Size of table
//if collision is detected Seperate chaining method is used
//In this method a node is appended to the desired index
//Time Complexity is O(1) for adding key to the table
//Space Complexity is O(N) in worst case with all values chained to same index

private:
int N;
vector< vector< int> > h; // This will store hash table entries in form of 2d vector

public:
singlehash(int N){ //hash table constructor with particular size N
h= vector< vector < int > >(N);
this->N=N;
}
int getIndex(int key){ //Hash function
return key % N;
}
void add(int key){
if(h[getIndex(key)].size()){
cout<<"Collision is there for "<< key <<" while adding key using Separate chaining \n";
}
h[getIndex(key)].push_back(key);
}
void displayHashTable(){
for(int i=0;i<h.size();i++){
cout<<i; //Index
for(int j=0;j<h[i].size();j++){
cout<<" => "<<h[i][j]; //value
}
cout<<"\n";
}
}

};
class doublehash{
//Key is added in the Hash table
//Index to which a key is stored is decide via hash function
//defined in line index = hash(key ) => hash1(key) + i*hash2(key) where i is the iteration 0,1,2,.. N
//If Collision is detected index is recalculated for next i value till size of N in worst case
//Time Complexity is O(1) is Average case and O(N) where N is size of table and index is recalculated till it find an empty spot
//Space complexity is O(1) even with worst case.
private:
int N;
vector< int > h; // This will store hash table entries in form of 1d vector

public:
doublehash(int N){ //hash table constructor with particular size N
h= vector< int>(N,-1);
this->N=N;
}
int getIndex(int key){ //First Hash function
return key % N;
}
int getIndex2(int key){ // Second Hash Function
return 3- (key % 3);
}
void add(int key){ //Adding key into Hash table
int target= getIndex(key); //Calculating Hash for target index
if(h[target]!=-1){ //Collision
int i=1;
while(1){
cout<<"Collision is there for "<< key << " while adding going for next iteration in double hashing \n";
int next= (target + i * getIndex2(key)) % N;
if(h[next]==-1){
h[next]=key; //adding entry
break;
}
i++;
}
}
else{
h[target]= key; //adding entry
}
}
void displayHashTable(){
for(int i=0;i<h.size();i++){
cout<<i; //Index
cout<<" => "<<h[i]; //value
cout<<"\n";
}
}

};
int main() {
//Program Starts here
int keys[] = { 2, 7, 16, 9 , 27, 11 }; //keys stored in an array
int n=6; //No of keys
singlehash sh =singlehash(6); //creating a Single Hash table
for(int i=0;i<n;i++){
sh.add(keys[i]);
}
cout<<"Display Single Hash table \n";
sh.displayHashTable(); //display Single Hash

doublehash dh =doublehash(6); //Creating a double hash table
for(int i=0;i<n;i++){
dh.add(keys[i]);
}
cout<<"Display Double Hash table \n";
dh.displayHashTable(); //display Double Hash

}

OUTPUT:-