Introduction
Hash tables and STL maps (See Maps in C++) are very useful data structures in computer science. Here we will see the comparison between their properties as well as implementation. First, we will discuss their properties one by one, and then we will differentiate them based on their key characteristics.
Hash Table
Hash Table is a special type of data structure that stores data(key-value pair) in an associative manner and uses a hash function that maps a given value with a key to access the elements faster.
Example
In the above diagram, keys are mapped to corresponding indices of the hash table using the hash function.
Advantages
- As the access time in the hash table is O(1) (i.e., constant ), inserting, deleting, and looking up data can be done very fast.
- The hash table also performs well in the case of large datasets.
Implementation
A Hash table is generally implemented by an array of linked lists where each node will store key-value pairs. A good hash function and collision resolution techniques like chaining are required for mapping the keys properly.
#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
node* next;
};
int has(int key)
{
return (key %10);
}
void HashInsert(int val, node *HT[])
{
//create a newnode with val
struct node *newNode = new node;
newNode->next = NULL;
//calculate hash index
int index = has(val);
//check if HT[index] is empty
if(HT[index] == NULL)
HT[index] = newNode;
//collision
else
{
//add the node at the end of HT[index].
struct node *temp = HT[index];
while(temp->next)
{
temp = temp->next;
}
temp->next = newNode;
}
}
int search(int val,node *HT[])
{
int index = has(val);
struct node *temp = HT[index];
while(temp)
{
if(temp->data == val)
return index;
temp = temp->next;
}
return -1;
}
//driver code
int main()
{
int keys[6]={16,12,45,29,6,122};
struct node *HT[10]; // Hash Table will be an array of linked list pointers
for(int i=0;i<10;i++)
HT[i]=NULL;//initialise each slot with NULL pointers
for(int i=0;i<6;i++)
{
HashInsert(keys[i],HT);
}
cout<<"Index of key=122 in the hash table : " <<search(keys[5],HT);
}