Lecture 360:- Chaining

Chaining is one of the common collision resolution techniques used in hash tables. When two different keys produce the same hash value (collision), chaining allows multiple values to be stored at the same index in the hash table by forming a chain of elements.

In the chaining approach, each bucket (slot) in the hash table contains a linked list (chain) of elements that share the same hash value. When a collision occurs, a new element is simply added to the existing linked list at the corresponding bucket.

Here's how the chaining collision resolution works:

1. Initialize an array of linked lists (buckets) to store the elements.
2. When inserting a new element with key K, compute its hash value (hash(K)).
3. Use the hash value as an index to find the appropriate linked list in the array.
4. If the linked list is empty, simply insert the new element as the head of the list.
5. If the linked list is not empty, traverse the list to check if the key K already exists:
   • If it does, update the value associated with K.
   • If it doesn't, append the new element at the end of the list.
6. When searching for an element with key K, compute its hash value and find the linked list at the corresponding bucket. Traverse the list to find the element with the key K.

Here's a basic C++ implementation of a hash table using chaining:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Structure for each element in the hash table struct HashNode {    int key;    int value;    HashNode* next;    HashNode(int k, int v) : key(k), value(v), next(nullptr) {} }; class HashTable { private:    int capacity; // Number of buckets (size of the hash table)    vector<HashNode*> table;    // Hash function to compute the hash value of a key    int hashFunction(int key) {        return key % capacity;    } public:    // Constructor    HashTable(int size) : capacity(size) {        table.resize(capacity, nullptr);    }    // Function to insert a key-value pair into the hash table    void insert(int key, int value) {        int index = hashFunction(key);        HashNode* newNode = new HashNode(key, value);        if (table[index] == nullptr) {            // If the bucket is empty, simply insert the new node            table[index] = newNode;        } else {            // If the bucket is not empty, add the new node to the linked list            HashNode* curr = table[index];            while (curr->next != nullptr)                curr = curr->next;            curr->next = newNode;        }    }    // Function to search for a key and return its corresponding value    int search(int key) {        int index = hashFunction(key);        HashNode* curr = table[index];        while (curr != nullptr) {            if (curr->key == key)                return curr->value;            curr = curr->next;        }        return -1; // Key not found    } }; int main() {    HashTable ht(10);    ht.insert(1, 10);    ht.insert(2, 20);    ht.insert(3, 30);    ht.insert(4, 40);    cout << "Value for key 2: " << ht.search(2) << endl; // Output: 20    cout << "Value for key 5: " << ht.search(5) << endl; // Output: -1 (not found)    return 0; }

In this implementation, the HashTable class uses a vector to represent the hash table, where each element of the vector is a pointer to the head of a linked list. The insert function inserts a new key-value pair, and the search function looks for a key and returns its corresponding value.