How To Resolve Collison in Hash Table in C++.

Created On: 01 September 2023

In hash table implementations, collisions occur when two different keys hash to the same index in the array. To handle collisions, various strategies are employed to ensure efficient storage and retrieval of data. In this article, we'll explore some common methods to resolve collisions and provide working examples in C++.


Collision Resolution Methods in Hash Table.

There are multiple ways to resolve collision in Hash Table (Hash Map) but here we are going to learn about three popular collision resolution methods mentioned below:

Now let's discuss each of these methods one by one in detail and use them in Hash Table Implementation.


Method 1: Chaining (Separate Chaining)

Separate Chaining is a popular collision resolution technique used in hash table implementations. It involves maintaining a linked list at each hash table index to handle collisions.


How does Separate Chaining Work?

It involves four important steps to implement the Chaining method to resolve collision:

1. Initialization: Create an array of linked lists, where each list represents a bucket in the hash table.


2. Insertion: When inserting a key-value pair, compute the hash of the key and determine the index in the array. Add the key-value pair to the linked list at that index.


3. Search: To retrieve a value for a given key, calculate the hash to find the index, and then search the linked list at that index for the key.


4. Collision Handling: When multiple keys hash to the same index (collision), they are simply added to the same linked list at that index.


Implementation of Separate Chaining in C++.

// C++ code for the implementation of Chaining in Hash Table
#include <iostream>
#include <list>
#include <utility>

class HashTable {
private:
    static const int tableSize = 10;
    std::list<std::pair<int, int>> table[tableSize];

    int hashFunction(int key) {
        return key % tableSize;
    }

public:
    void insert(int key, int value) {
        int index = hashFunction(key);
        table[index].emplace_back(key, value);
    }

    int get(int key) {
        int index = hashFunction(key);
        for (const auto& pair : table[index]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return -1; // Key not found
    }
};

int main() {
    HashTable hashTable;

    hashTable.insert(5, 50);
    hashTable.insert(15, 150);
    hashTable.insert(25, 250);
 
    std::cout << "Value at key 15: " << hashTable.get(15) << std::endl;

    return 0;
}
Output:
Value at key 15: 150

Method 1: Open Addressing.

Open Addressing is another widely used collision resolution technique in hash table implementations. Unlike Separate Chaining, Open Addressing aims to resolve collisions by placing the collided element directly into the hash table itself.

How Open Addressing Works?

It involves four important steps to implement the Open Address method to resolve collision:

1. Initialization: Create an array (hash table) to hold the key-value pairs. Initially, all slots are empty.

2. Insertion: When inserting a key-value pair, compute the hash of the key and determine the index in the array. If the slot is occupied, use a probing sequence (linear, quadratic, etc.) to find the next available slot.

3. Search: To retrieve a value for a given key, calculate the hash to find the index, and then use the same probing sequence to search for the key.

4. Collision Handling: When a collision occurs, Open Addressing attempts to find the next available slot within the array to place the collided element.

Implementation of Open Addressing in C++.

// C++ code to implement Open Addression in Hash Map
#include <iostream>
#include <vector>
using namespace std;

class HashTable {
private:
    static const int tableSize = 10;
    vector<pair<int, int>> table;

    int hashFunction(int key) {
        return key % tableSize;
    }

    int linearProbing(int index, int attempt) {
        return (index + attempt) % tableSize;
    }

public:
    HashTable() : table(tableSize, std::make_pair(-1, -1)) {}

    void insert(int key, int value) {
        int index = hashFunction(key);
        int attempt = 0;

        while (table[index].first != -1) {
            index = linearProbing(index, ++attempt);
        }

        table[index] = make_pair(key, value);
    }

    int get(int key) {
        int index = hashFunction(key);
        int attempt = 0;

        while (table[index].first != -1) {
            if (table[index].first == key) {
                return table[index].second;
            }
            index = linearProbing(index, ++attempt);
        }

        return -1; // Key not found
    }
};

int main() {
    HashTable hashTable;

    hashTable.insert(5, 50);
    hashTable.insert(15, 150);
    hashTable.insert(25, 250);

    cout << "Value at key 15: " << hashTable.get(15) << endl;

    return 0;
}
Output:
Value at key 15: 150

Method 3: Robin Hood Hashing.

Robin Hood Hashing is a variant of Open Addressing, a collision resolution technique used in hash tables. It focuses on distributing collided elements more evenly within the table to achieve better performance.

How Robin Hood Hashing Works?

It involves four important steps to implement the Robin Hood Hashing method to resolve collision:

1. Initialization: Create an array (hash table) to hold the key-value pairs. Initially, all slots are empty.

2. Insertion: When inserting a key-value pair, calculate the hash of the key and determine the index in the array. If the slot is occupied, compare the distances between the desired index and the current index for both the existing element and the new element. If the new element's distance is smaller, swap the elements and continue probing.

3. Search: To retrieve a value for a given key, calculate the hash to find the index, and then use the same probing sequence to search for the key.

4. Collision Handling: Robin Hood Hashing aims to minimize the difference in the probing distances, ensuring a more balanced distribution of elements.

Implementation of Robin Hood Hashing in C++.

// C++ code to implement Robin Hood Hashing
#include <iostream>
#include <vector>
using namespace std;

class HashTable {
private:
    static const int tableSize = 10;
    vector<pair<int, int>> table;

    int hashFunction(int key) {
        return key % tableSize;
    }

public:
    HashTable() : table(tableSize, make_pair(-1, -1)) {}

    void insert(int key, int value) {
        int index = hashFunction(key);
        int distance = 0;

        while (table[index].first != -1) {
            if (distance > tableSize - 1) {
                break; // Avoid infinite loop
            }

            if (distance > index - hashFunction(table[index].first)) {
                swap(key, table[index].first);
                swap(value, table[index].second);
                distance = index - hashFunction(key);
            }

            index = (index + 1) % tableSize;
            distance++;
        }

        table[index] = make_pair(key, value);
    }

    int get(int key) {
        int index = hashFunction(key);
        int distance = 0;

        while (table[index].first != -1) {
            if (table[index].first == key) {
                return table[index].second;
            }
            index = (index + 1) % tableSize;
            distance++;
        }

        return -1; // Key not found
    }
};

int main() {
    HashTable hashTable;

    hashTable.insert(5, 50);
    hashTable.insert(15, 150);
    hashTable.insert(25, 250);

    cout << "Value at key 15: " << hashTable.get(15) << endl;

    return 0;
}
Output:
Value at key 15: 150

Conclusion:

Collision resolution is a critical aspect of hash table implementations. Chaining is a popular method using linked lists to store colliding elements. This ensures efficient storage and retrieval while keeping collision-related complexities under control. In more advanced implementations, other methods like open addressing and Robin Hood hashing are explored to further optimize hash table performance.

⚡ Please share your valuable feedback and suggestion in the comment section below or you can send us an email on our offical email id ✉ algolesson@gmail.com. You can also support our work by buying a cup of coffee ☕ for us.

Similar Posts

No comments:

Post a Comment


CLOSE ADS
CLOSE ADS