Hash Table
In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.
Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions are always accommodated in some way.
In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at (amortized) constant average cost per operation.
In many situations, hash tables turn out to be on average more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, databaseindexing, caches, and sets.
Linear Hashing in C++
It is very easy and simple method to resolve or to handle the collision. In this collision can be solved by placing the second record linearly down, whenever the empty place is found. In this method there is a problem of clustering which means at some place block of a data is formed in a hash table.
#include<iostream>
#include<conio.h>
#include<stdlib.h>
#include<string>
using namespace::std;
class item
{
public:
int data;
item(int k)
{
data=k;
}
int getkey()
{
return data;
}
void display()
{
cout<<" "<<data;
}
};
class hashtable
{
public:
item* hasharray[20];
int arraysize=20;
//item* nonitem;
hashtable()
{
//problem in dynamic through
//arraysize=20;
//hasharray=new item[arraysize];
for(int i=0;i<arraysize; i++)
{
hasharray[i]=NULL;
}
}
void linear_insert(item* i)
{
int key=i->getkey();
int hashval=hashfunc(key);
while(hasharray[hashval]!=NULL && hasharray[hashval]->getkey()!=-1)
{
++hashval;
hashval=hashval%arraysize;
}
cout<<"\nindex for insertion :"<<hashval<<endl;
hasharray[hashval]=i;
cout<<"\nelement inserted"<<endl;
}
int hashfunc(int key)
{
return (key%arraysize);
}
void linear_delete(int key)
{
item* nonitem=new item(-1);
int hashval=hashfunc(key);
while(hasharray[hashval]!=NULL)
{
if(hasharray[hashval]->getkey()==key)
{
//item* temp=hasharray[hashval];
hasharray[hashval]=nonitem;
cout<<"\nitem deleted at key : "<<key<<" index : "<<hashval;
return ;
}
++hashval;
hashval=hashval%arraysize;
}
cout<<"\nno such element is found for deletion:";
}
item* linear_search(int key)
{
int hashval=hashfunc(key);
while(hasharray[hashval]!=NULL)
{
if(hasharray[hashval]->getkey()==key)
return hasharray[hashval];
++hashval;
hashval=hashval%arraysize;
}
return NULL;
}
int displaytable()
{
for(int i=0;i<arraysize;i++)
{
if(hasharray[i]!=NULL)
cout<<hasharray[i]->getkey()<<" ";
else
cout<<" * ";
}
}
};
int main()
{
item* dataitem;
int akey,n;
hashtable* htable=new hashtable();
cout<<"\ndisplaying the whole empty list";
htable->displaytable();
cout<<"\nenter the size value you want to insert:";
cin>>n;
cout<<"\n generation "<<n<<" random detaitem for insertion";
//srand(time(0))
for(int j=0;j<n;j++)
{
akey=(int)(1+rand()%200);
dataitem=new item(akey);
cout<<"\ninserting item with key "<<akey<<endl;
htable->linear_insert(dataitem);
}
cout<<"\ndisplaying the whole list";
htable->displaytable();
int z;
cout<<"\nenter the value you want to search it"<<endl;
cin>>z;
//htable->linear_delete(z);
//htable->displaytable();
item* nn;
nn=htable->linear_search(z);
if(nn!=NULL)
{
cout<<"\nthe value is found"<<nn->getkey();
}else
{
cout<<" value is not found in the list"<<endl;
}
}
Quadratic Hashing in C++
This is a method in which solving of clustering problem is done. In this method the hash function is defined by the H(key)=(H(key)+x*x)%table size.
#include<iostream>
#include<conio.h>
#include<stdlib.h>
#include<string>
using namespace::std;
class item
{
public:
int data;
item(int k)
{
data=k;
}
int getkey()
{
return data;
}
void display()
{
cout<<" "<<data;
}
};
class hashtable
{
public:
item* hasharray[23];
int arraysize=23;
//item* nonitem;
hashtable()
{
//problem in dynamic through
//arraysize=20;
//hasharray=new item[arraysize];
for(int i=0;i<arraysize; i++)
{
hasharray[i]=NULL;
}
}
void linear_insert(item* i)
{
int key=i->getkey();
int hashval=hashfunc(key);
while(hasharray[hashval]!=NULL && hasharray[hashval]->getkey()!=-1)
{
hashval=hashval+(hashval*hashval);
hashval=hashval%arraysize;
}
cout<<"\nindex for insertion :"<<hashval<<endl;
hasharray[hashval]=i;
cout<<"\nelement inserted"<<endl;
}
int hashfunc(int key)
{
return (key%arraysize);
}
void linear_delete(int key)
{
item* nonitem=new item(-1);
int hashval=hashfunc(key);
while(hasharray[hashval]!=NULL)
{
if(hasharray[hashval]->getkey()==key)
{
item* temp=hasharray[hashval];
hasharray[hashval]=nonitem;
cout<<"\nitem deleted at key : "<<key<<" index : "<<hashval;
return ;
}
hashval=hashval+(hashval*hashval);
hashval=hashval%arraysize;
}
cout<<"\nno such element is found for deletion:";
}
item* linear_search(int key)
{
int hashval=hashfunc(key);
while(hasharray[hashval]!=NULL)
{
if(hasharray[hashval]->getkey()==key)
return hasharray[hashval];
hashval=hashval+(hashval*hashval);
hashval=hashval%arraysize;
}
return NULL;
}
int displaytable()
{
for(int i=0;i<arraysize;i++)
{
if(hasharray[i]!=NULL)
cout<<hasharray[i]->getkey()<<" ";
else
cout<<" * ";
}
}
};
int main()
{
item* dataitem;
int akey,n;
hashtable* htable=new hashtable();
cout<<"\ndisplaying the whole empty list";
htable->displaytable();
cout<<"\nenter the size value you want to insert:";
cin>>n;
cout<<"\n generation "<<n<<" random detaitem for insertion";
//srand(time(0))
for(int j=0;j<n;j++)
{
akey=(int)(1+rand()%200);
dataitem=new item(akey);
cout<<"\ninserting item with key "<<akey<<endl;
htable->linear_insert(dataitem);
}
cout<<"\ndisplaying the whole list";
htable->displaytable();
cout<<"\nwelcome"<<endl;
int z;
cout<<"\nenter the value you want to search it"<<endl;
cin>>z;
//htable->linear_delete(z);
//htable->displaytable();
item* nn;
nn=htable->linear_search(z);
if(nn!=NULL)
{
cout<<"\nthe value is found"<<nn->getkey();
}else
{
cout<<" value is not found in the list"<<endl;
}
}
Double Hashing in C++
It is a technique in which two hash function are used when there is an occurrence of collision. In this method 1 hash function is simple as same as division method. But for the second hash function there are two important rules which are
1. It must never evaluate to zero.
2. Must sure about the buckets, that they are probed.
The hash functions for this technique are:
H1(key)=key % table size
H2(key)=P-(key mod P)
Where, p is a prime number which should be taken smaller than the size of a hash table.
#include<iostream>
#include<conio.h>
#include<stdlib.h>
#include<string>
using namespace::std;
class item
{
public:
int data;
item(int k)
{
data=k;
}
int getkey()
{
return data;
}
void display()
{
cout<<" "<<data;
}
};
class hashTable
{
public:
item* hasharray[19];
int arraysize=19;
//item* nonitem;
hashtable()
{
//problem in dynamic through
//arraysize=20;
//hasharray=new item[arraysize];
for(int i=0;i<arraysize; i++)
{
hasharray[i]=NULL;
}
}
void linear_insert(item* i)
{
int key=i->getkey();
int hashval=hashfunc(key);
int stepSize = hashFunc2(key);
while(hasharray[hashval]!=NULL && hasharray[hashval]->getkey()!=-1)
{
hashval=hashval+stepSize;
hashval=hashval%arraysize;
}
cout<<"\nindex for insertion :"<<hashval<<endl;
hasharray[hashval]=i;
cout<<"\nelement inserted"<<endl;
}
int hashFunc2(int key)
{
return(arraysize-key%arraysize);
}
int hashfunc(int key)
{
return (key%arraysize);
}
void linear_delete(int key)
{
item* nonitem=new item(-1);
int hashval=hashfunc(key);
int stepSize = hashFunc2(key);
while(hasharray[hashval]!=NULL)
{
if(hasharray[hashval]->getkey()==key)
{
item* temp=hasharray[hashval];
hasharray[hashval]=nonitem;
cout<<"\nitem at key : "<<key<<" index : "<<hashval;
return ;
}
hashval=hashval+stepSize;
hashval=hashval%arraysize;
}
cout<<"\nno such element is found for deletion:";
}
item* linear_search(int key)
{
int hashval=hashfunc(key);
int stepSize = hashFunc2(key);
while(hasharray[hashval]!=NULL)
{
if(hasharray[hashval]->getkey()==key)
return hasharray[hashval];
hashval=hashval+stepSize;
hashval=hashval%arraysize;
}
return NULL;
}
int displaytable()
{
for(int i=0;i<arraysize;i++)
{
if(hasharray[i]!=NULL)
cout<<hasharray[i]->getkey()<<" ";
else
cout<<" * ";
}
}
};
int main()
{
item* dataitem;
int akey,n;
hashTable* htable=new hashTable();
cout<<"\ndisplaying the whole empty list";
htable->displaytable();
cout<<"\nenter the size value you want to insert:";
cin>>n;
cout<<"\n generation "<<n<<" random detaitem for insertion";
//srand(time(0))
for(int j=0;j<n;j++)
{
akey=(int)(1+rand()%200);
dataitem=new item(akey);
cout<<"\ninserting item with key "<<akey<<endl;
htable->linear_insert(dataitem);
}
cout<<"\ndisplaying the whole list";
htable->displaytable();
cout<<"\nwelcome"<<endl;
int z;
cout<<"\nenter the value you want to search it"<<endl;
cin>>z;
//htable->linear_delete(z);
//htable->displaytable();
item* nn;
nn=htable->linear_search(z);
if(nn!=NULL)
{
cout<<"\nthe value is found"<<nn->getkey();
}else
{
cout<<" value is not found in the list"<<endl;
}
}
No comments:
Post a Comment