What is Chaining?

Chaining is a technique used for avoiding collisions in Hash Tables.
In the chaining approach, the hash table is an array of linked lists. All key-value pairs mapping to the same index will be stored in the linked list of that index.

It’s important to note that :

hashIndex = key % noOfBuckets

PSUEDO CODE -

class Hash{
   int BUCKET;
   list < int >*table;
   public:
   Hash (int V);
   void insertItem (int x);
   void deleteItem (int key);
   int hashFunction (int x){
      return (x % BUCKET);
   }
   void displayHash ();
};
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;
   }
}