Few basic things that I might forget later.

  • Hash Table is basically an array of linked lists while STL Maps (in C++) is an Implementation of self-balancing red-black tree.

  • Load Factor and Rehashing: Load factor = Size of hashmap (n)/number of buckets (b). Load factor should normally be kept less than 0.75. Rehashing is done when complexity increases (l.f>0.75) so the size of array(buckets) is doubled and all the values are hashed again.

C++ Implementation of Hashing with chaining

#include <bits/stdc++.h>
using namespace std;
class Hash
{
int Bucket; //no of buckets
list<int> *table;
public:
Hash( int V); //this is a constructor
void insertItem(int x);
void deleteItem(int key);
int hashFunction(int x {
return (x % Bucket);
}
void display Hash();
};
Hash::Hash(int b)
{
this->Bucket = b;
table = new list<int>[Bucket];
}
void Hash::insertItem(int key)
{
int index = hashFunction(key);
table[index].push_back(key);
}
void Hash::deleteItem(int key)
{
int index hashFunction(key);
list<int> :: iterator i;
for(i = table[index].begin(); i!=table[index].end(); i++) {
if(*i == key){
break;
}
}
if(i != table[index].end()){
table[index].erase(i);
}
}
void Hash::displayHash() {
for(int i = 0; i<Bucket; i++) {
cout<<i;
for(auto x: table[i])
{
cout<< " -->" << x;
}
cout<<endl;
}
}
int main()
{
int a[] = {15, 11, 27, 8, 12};
int n = sizeof(a)/sizeof(a[0]);
Hash h(7);
for ( int i = 0; i<n; i++) {
h.insertItem(a[i]);
h.deleteItem(12);
h.displayHash();
return 0;
}
}
© 2021 Mritunjay Sharma