Double Hashing | DSA in C++ - Software Development PDF Download

Introduction:

Hashing is a popular technique used in computer science to efficiently store and retrieve data. However, collisions can occur when two different elements are mapped to the same hash value. To overcome this issue, various collision resolution techniques are used, and one such technique is double hashing. In this article, we will explore double hashing and its implementation in C++. We will cover the basics of double hashing, provide simple code examples with explanations, and conclude with some sample problems and their solutions.

What is Double Hashing?

Double Hashing Implementation in C++

To implement double hashing in C++, we need to create a hash table and define two hash functions. The first hash function calculates the initial index, and the second hash function determines the step size (the amount to be added to the current index if a collision occurs).
Here's a simplified implementation of a hash table using double hashing in C++:

#include <iostream>

#define SIZE 10

class HashTable {

private:

    int table[SIZE];

    bool isOccupied[SIZE];

    int hashFunc1(int key) {

        return key % SIZE;

    }

    int hashFunc2(int key) {

        return 7 - (key % 7);

    }

public:

    HashTable() {

        for (int i = 0; i < SIZE; i++) {

            table[i] = -1;

            isOccupied[i] = false;

        }

    }

    void insert(int key) {

        int index = hashFunc1(key);

        if (isOccupied[index]) {

            int step = hashFunc2(key);

            while (isOccupied[index]) {

                index = (index + step) % SIZE;

            }

        }

        table[index] = key;

        isOccupied[index] = true;

    }

    bool search(int key) {

        int index = hashFunc1(key);

        if (table[index] == key) {

            return true;

        }

        int step = hashFunc2(key);

        while (table[index] != key) {

            index = (index + step) % SIZE;

            if (!isOccupied[index] || index == hashFunc1(key)) {

                return false;

            }

        }

        return true;

    }

};

Code Examples and Explanations

Let's dive into the code examples and understand how double hashing works for inserting and searching elements in a hash table.

Inserting an Element using Double Hashing

To insert an element into the hash table, we first calculate the initial index using the first hash function (hashFunc1). If the index is already occupied, we use the second hash function (hashFunc2) to determine the step size and probe the next available index until an unoccupied position is found.

HashTable ht;

ht.insert(25);

ht.insert(7);

ht.insert(42);

Output:

No output will be displayed. The elements are successfully inserted into the hash table.

Explanation:

In this example, we insert the elements 25, 7, and 42 into the hash table. The initial indices calculated by 'hashFunc1' are 5, 7, and 2, respectively. Since index 5 is unoccupied, the element 25 is inserted at that position. Index 7 is also unoccupied, so 7 is inserted at that position. However, index 2 is already occupied, so we use 'hashFunc2' to determine the step size, which is 2. We then probe the next available index (4) and insert 42 at that position.

Searching for an Element using Double Hashing

To search for an element in the hash table, we calculate the initial index using 'hashFunc1'. If the element is found at that index, the search is successful. Otherwise, we use 'hashFunc2' to determine the step size and probe the next indices until the element is found or an unoccupied position is encountered.

bool found = ht.search(7);

if (found) {

    std::cout << "Element found!" << std::endl;

} else {

    std::cout << "Element not found." << std::endl;

}

Output:

Element found!

Explanation:

In this example, we search for the element 7 in the hash table. The initial index calculated by 'hashFunc1' is 7, and the element at that position matches the search key. Therefore, the search is successful, and the output displays "Element found!".

Sample Problems and Solutions

Here are a few sample problems related to double hashing, along with their solutions:

Problem 1: Create a hash table using double hashing and insert the following elements: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100. Display the final state of the hash table.

HashTable ht;

int elements[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

for (int i = 0; i < 10; i++) {

    ht.insert(elements[i]);

}

Problem 2: Search for the element 60 in the hash table created in Problem 1 and display the result.

bool found = ht.search(60);

if (found) {

    std::cout << "Element found!" << std::endl;

} else {

    std::cout << "Element not found." << std::endl;

}

Conclusion

Double hashing is an effective collision resolution technique in hash tables. It helps distribute elements evenly, reducing collisions and improving performance. In this article, we explored the basics of double hashing, implemented it in C++, and provided examples and solutions for better understanding. By applying double hashing, you can handle collisions more efficiently and build robust hash table implementations in your programs.