C++ Program to Implement Hash Tables
//Implementable on C++ 11/14/17
using namespace std;
class hashclass
{
int bucket; //no of buckets you want
list<int>*hashtable;//container
public:
hashclass(int a)//constructor
{
bucket=a;
hashtable=new list<int>[bucket];
}
void insert_element(int key)//function used to insert elements to the hashtable
{
//to get the hash index of key
int indexkey=hashFunction(key);
hashtable[indexkey].push_back(key);
}
void delete_element(int key)//function used to delete elements from the hashtable
{
int indexkey=hashFunction(key);
list<int>::iterator i=hashtable[indexkey].begin();
for(;i!=hashtable[indexkey].end();i++)
{
if(*i==key)
break;
}
if(i!=hashtable[indexkey].end())
{
hashtable[indexkey].erase(i);
}
}
int hashFunction(int a)//function used to map values to key
{
return (a%bucket);
}
void display_table()//used to display hashtable values
{
for(int i=0;i<bucket;i++)
{
cout<<i;
list<int>::iterator j=hashtable[i].begin();
for(;j!=hashtable[i].end();j++)
{
cout<<"---->"<<*j;
}
cout<<endl;
}
}
void search_element(int key)//used to search element
{
int a=0;//will be 1 if element exist otherwise 0
int indexkey=hashFunction(key);
list<int>::iterator i=hashtable[indexkey].begin();
for(;i!=hashtable[indexkey].end();i++)
{
if(*i==key)
{
a=1;
break;
}
}
if(a==1)
{
cout<<"The element you wanted to search is present in the hashtable."<<endl;
}
else
{
cout<<"Element not present"<<endl;
}
}
~hashclass()//destructor
{
delete[]hashtable;
}
};
int main()
{
int bucketn,ch,element;
cout<<"enter the no of buckets"<<endl;
cin>>bucketn;
hashclass hashelement(bucketn);
while(1)
{
cout<<"1.insert element to the hashtable"<<endl;
cout<<"2.search element from the hashtable"<<endl;
cout<<"3.delete element from the hashtable"<<endl;
cout<<"4.display elements of the hashtable"<<endl;
cout<<"5.exit"<<endl;
cout<<"enter your choice"<<endl;
cin>>ch;
switch(ch)
{
case 1:cout<<"enter the element"<<endl;
cin>>element;
hashelement.insert_element(element);
break;
case 2:cout<<"enter the element you want to search"<<endl;
cin>>element;
hashelement.search_element(element);
break;
case 3:cout<<"enter the element to be deleted"<<endl;
cin>>element;
hashelement.delete_element(element);
break;
case 4:hashelement.display_table();
break;
case 5:return 0;
default:cout<<"enter a valid value"<<endl;
}
}
return 0;
}
Hash Tables
DEFINITION :
Hash tables is a data structure which is used to store information with the help of key/value pairs and a hash function which maps keys to values.Hash tables have an associative array like structure which is unordered and this array can also be called as a list of buckets.
HASH FUNCTION :
when we want to insert a key/value pair ,we map the key to an index in the array(hash table) using a hash function. The address of each key is calculated using the key itself inside the hash function which returns a value.
SOME PROPERTIES :
> Hash Table works synchronously.
> When there is a large amount of data to be stored we prefer hash tables.
>Insertion ,deletion and retrieval of data occur in constant time.(note ->except in the case of collision).
COLLISION :
It happens when 2 or more keys have the same value.
eg: Hashfunction(key1) = value1
Hashfunction(key2) = value1
This problem can be solved by: -
> chaining or closed-addressing: this technique is generally used when collision occurs.
> open-addressing: this contains linear probing,quadratic probing etc.
TIME COMPLEXITY :
Average case:O(1)---> insertion,deletion,searching(note- this happens only when there is no collision).
Worst case:O(n):--->this happens when there are collisions.
Working(chaining):
User enters the element to insert,search or delete, this element is known as key which the hash function takes as an argument and returns a value which should be mapped to the array , this value is basically the index where the key is stored in the array. During collision, which happens when 2 or more keys have the same value the latest key will link itself to the older key which is already linked to the value(index) of that particular valued bucket.
(note->list of buckets = array.)
CONTAINER USED :
std::list,Lists are sequence containers that allow non-contiguous memory allocation. By default they are doubly-linked list.
IMPLEMENTATION (chaining):
using namespace std;
class hashclass
{
int bucket; //no of buckets you want
list<int>*hashtable;//container
public:
hashclass(int a)//constructor
{
bucket=a;
hashtable=new list<int>[bucket];
}
void insert_element(int key)//function used to insert elements to the hashtable
{
//to get the hash index of key
int indexkey=hashFunction(key);
hashtable[indexkey].push_back(key);
}
void delete_element(int key)//function used to delete elements from the hashtable
{
int indexkey=hashFunction(key);
list<int>::iterator i=hashtable[indexkey].begin();
for(;i!=hashtable[indexkey].end();i++)
{
if(*i==key)
break;
}
if(i!=hashtable[indexkey].end())
{
hashtable[indexkey].erase(i);
}
}
int hashFunction(int a)//function used to map values to key
{
return (a%bucket);
}
void display_table()//used to display hashtable values
{
for(int i=0;i<bucket;i++)
{
cout<<i;
list<int>::iterator j=hashtable[i].begin();
for(;j!=hashtable[i].end();j++)
{
cout<<"---->"<<*j;
}
cout<<endl;
}
}
void search_element(int key)//used to search element
{
int a=0;//will be 1 if element exist otherwise 0
int indexkey=hashFunction(key);
list<int>::iterator i=hashtable[indexkey].begin();
for(;i!=hashtable[indexkey].end();i++)
{
if(*i==key)
{
a=1;
break;
}
}
if(a==1)
{
cout<<"The element you wanted to search is present in the hashtable."<<endl;
}
else
{
cout<<"Element not present"<<endl;
}
}
~hashclass()//destructor
{
delete[]hashtable;
}
};
int main()
{
int bucketn,ch,element;
cout<<"enter the no of buckets"<<endl;
cin>>bucketn;
hashclass hashelement(bucketn);
while(1)
{
cout<<"1.insert element to the hashtable"<<endl;
cout<<"2.search element from the hashtable"<<endl;
cout<<"3.delete element from the hashtable"<<endl;
cout<<"4.display elements of the hashtable"<<endl;
cout<<"5.exit"<<endl;
cout<<"enter your choice"<<endl;
cin>>ch;
switch(ch)
{
case 1:cout<<"enter the element"<<endl;
cin>>element;
hashelement.insert_element(element);
break;
case 2:cout<<"enter the element you want to search"<<endl;
cin>>element;
hashelement.search_element(element);
break;
case 3:cout<<"enter the element to be deleted"<<endl;
cin>>element;
hashelement.delete_element(element);
break;
case 4:hashelement.display_table();
break;
case 5:return 0;
default:cout<<"enter a valid value"<<endl;
}
}
return 0;
}
SAMPLE OUTPUT:
enter the no of buckets
4
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
1
enter the element
13
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
1
enter the element
16
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
1
enter the element
20
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
4
0---->16---->20
1---->13
2
3
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
2
enter the element you want to search
20
The element you wanted to search is present in the hashtable.
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
3
enter the element to be deleted
20
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
4
0---->16
1---->13
2
3
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
1
enter the element
13
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
1
enter the element
16
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
1
enter the element
20
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
4
0---->16---->20
1---->13
2
3
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
2
enter the element you want to search
20
The element you wanted to search is present in the hashtable.
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
3
enter the element to be deleted
20
1.insert element to the hashtable
2.search element from the hashtable
3.delete element from the hashtable
4.display elements of the hashtable
5.exit
enter your choice
4
0---->16
1---->13
2
3
More Articles of Shubham Edappanavar:
| Name | Views | Likes |
|---|---|---|
| C++ Boost Any | 1717 | 10 |
| C++ boost::heap::binomial_heap | 1196 | 10 |
| C++ Boost Scope Exit | 6746 | 8 |
| C++ Boost Bind | 1595 | 6 |
| C++ Boost Compressed Pair | 1370 | 10 |
| C++ Boost Dynamic Bitset | 2958 | 10 |
| C++ boost::heap::priority_queue | 1314 | 10 |
| C++ Program to Implement Hash Tables | 5295 | 9 |
Comments