C++ Program - Hashing Programme with Chaining

Hashing is a technique used for storing and retrieving data based on some key. In this program, we implement Hashing with Chaining which is a way of handling collisions between different keys by using a linked list to store the values corresponding to the same key.

Syntax

// Structure for the nodes of the linked list
struct Node {
    int data;
    Node* next;
};

const int TABLE_SIZE = 128;

class HashTable {
    private:
        // Array of linked lists to store the keys and their values
        Node* table[TABLE_SIZE];
        
        // Hash function to determine the index for a key
        int hash(int key);
        
    public:
        HashTable();
        void insert(int key, int value);
        int search(int key);
        void remove(int key);
        ~HashTable();
};

Example

#include <iostream>
using namespace std;

// Structure for the nodes of the linked list
struct Node {
    int data;
    Node* next;
};

const int TABLE_SIZE = 128;

class HashTable {
    private:
        // Array of linked lists to store the keys and their values
        Node* table[TABLE_SIZE];
        
        // Hash function to determine the index for a key
        int hash(int key) {
            return key % TABLE_SIZE;
        }
        
    public:
        HashTable() {
            for(int i=0;i<TABLE_SIZE;i++) {
                table[i] = NULL;
            }
        }
        
        void insert(int key, int value) {
            int hash_value = hash(key);
            Node* new_node = new Node { value, NULL };
            
            // If the linked list for the key is empty
            if(table[hash_value] == NULL) {
                table[hash_value] = new_node;
            }
            else {
                // Traverse the linked list and append the new node at the end
                Node* temp = table[hash_value];
                while(temp->next != NULL) {
                    temp = temp->next;
                }
                temp->next = new_node;
            }
        }
        
        int search(int key) {
            int hash_value = hash(key);
            
            // Traverse the linked list and search for the key
            Node* temp = table[hash_value];
            while(temp != NULL) {
                if(temp->data == key) {
                    return temp->data;
                }
                temp = temp->next;
            }
            
            // Key not found
            return -1;
        }
        
        void remove(int key) {
            int hash_value = hash(key);
            
            // If the linked list for the key is empty
            if(table[hash_value] == NULL) {
                return;
            }
            else if(table[hash_value]->data == key) {
                // If the first node in the linked list is the key
                Node* temp = table[hash_value];
                table[hash_value] = table[hash_value]->next;
                delete temp;
            }
            else {
                // Traverse the linked list and remove the node with the key
                Node* temp = table[hash_value];
                while(temp->next != NULL && temp->next->data != key) {
                    temp = temp->next;
                }
                if(temp->next == NULL) {
                    return;
                }
                Node* to_delete = temp->next;
                temp->next = temp->next->next;
                delete to_delete;
            }
        }
        
        ~HashTable() {
            for(int i=0;i<TABLE_SIZE;i++) {
                Node* current = table[i];
                while(current != NULL) {
                    Node* to_delete = current;
                    current = current -> next;
                    delete to_delete;
                }
                table[i] = NULL;
            }
        }
};

int main() {
    HashTable ht;
    
    ht.insert(1, 10);
    ht.insert(2, 20);
    ht.insert(3, 30);
    ht.insert(17, 40);
    
    cout << ht.search(1) << endl;
    cout << ht.search(2) << endl;
    cout << ht.search(3) << endl;
    cout << ht.search(17) << endl;
    
    ht.remove(2);
    
    cout << ht.search(2) << endl;
    
    return 0;
}

Output

10
20
30
40
-1

Explanation

In this program, we implement hashing with chaining to store and retrieve data based on a key. We define a hash table which is an array of linked lists. The hash function is used to determine the index in the array for a key. If the linked list for the key is empty, a new node is added with the value. Otherwise, the new node is appended to the end of the linked list. To search for a key, we traverse the linked list and return the corresponding value if found. To remove a key, we traverse the linked list and remove the node with the key.

Use

Hashing with chaining is a commonly used technique for storing and retrieving data based on a key. It is used in many applications such as databases, search engines, and caching systems.

Important Points

• Hashing with chaining is a way of handling collisions between different keys by using a linked list to store the values corresponding to the same key.
• The hash function is used to determine the position in the array of linked lists for a key.
• To insert a new key and value, a new node is added to the linked list for the key if it exists. Otherwise, a new linked list is created for the key.
• To search for a key, we traverse the linked list for the key and return the corresponding value if found.
• To remove a key, we traverse the linked list for the key and remove the node with the key.

Summary

In summary, hashing with chaining is a useful technique for storing and retrieving data based on a key. We use a hash function to determine the position in an array of linked lists for a key. We use a linked list to store the values corresponding to the same key. We can insert, search, and remove keys efficiently using this technique.