Lecture 361:- Let's Code Chaining

Let's implement a hash table using chaining for collision resolution in C++:

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    }    // Function to display the elements of the hash table    void display() {        for (int i = 0; i < capacity; i++) {            cout << "Bucket " << i << ": ";            HashNode* curr = table[i];            while (curr != nullptr) {                cout << "(" << curr->key << ", " << curr->value << ") -> ";                curr = curr->next;            }            cout << "nullptr" << endl;        }    } }; int main() {    HashTable ht(10);    ht.insert(1, 10);    ht.insert(2, 20);    ht.insert(3, 30);    ht.insert(4, 40);    ht.insert(11, 110); // Collides with key 1    cout << "Value for key 2: " << ht.search(2) << endl; // Output: 20    cout << "Value for key 5: " << ht.search(5) << endl; // Output: -1 (not found)    cout << "Hash Table Contents:" << endl;    ht.display();    return 0; }