Lecture 365:- Double Hashing

Double hashing is another collision resolution technique used in hash tables. It is an extension of linear probing and addresses the clustering issues that can occur with linear probing. Double hashing uses two hash functions to calculate the next index when a collision occurs.

Here's how double hashing works:

1. Compute the hash value (hash code) of the key using the first hash function.
2. If the bucket corresponding to the computed hash value is empty, insert the element at that bucket.
3. If the bucket is occupied, use a second hash function to calculate the step size (the amount to skip) for probing.
4. Repeat step 3 until an empty bucket is found or the entire hash table is scanned.

The second hash function should produce non-zero values and should be relatively prime to the hash table's capacity to ensure that all buckets are probed. A common choice for the second hash function is to use a prime number, which is not a factor of the table's capacity.

The formula for calculating the next index using double hashing is:

cssCopy code

nextIndex = (currentIndex + i * stepSize) % capacity

where currentIndex is the index of the bucket with a collision, i is the probe number starting from 0, stepSize is the value calculated by the second hash function, and capacity is the number of buckets in the hash table.

Double hashing can help reduce clustering and improve the performance of the hash table, but it requires careful selection of the two hash functions.

Here's a C++ implementation of a hash table using double hashing for collision resolution:

cppCopy code

#include <iostream> #include <vector> using namespace std; class HashTable { private:    int capacity; // Number of buckets (size of the hash table)    vector<int> keys;    vector<int> values;    // First hash function to compute the hash value of the key    int hashFunction1(int key) {        return key % capacity;    }    // Second hash function to calculate the step size    int hashFunction2(int key) {        return 1 + (key % (capacity - 1)); // Using a prime number as the step size    } public:    // Constructor    HashTable(int size) : capacity(size) {        keys.resize(capacity, -1); // Initialize keys with -1 (indicating an empty bucket)        values.resize(capacity, 0);    }    // Function to insert a key-value pair into the hash table    void insert(int key, int value) {        int index = hashFunction1(key);        int stepSize = hashFunction2(key);        int i = 0;        // Find the next available bucket using double hashing        while (keys[index] != -1) {            index = (index + i * stepSize) % capacity;            i++;        }        // Insert the key-value pair at the found bucket        keys[index] = key;        values[index] = value;    }    // Function to search for a key and return its corresponding value    int search(int key) {        int index = hashFunction1(key);        int stepSize = hashFunction2(key);        int i = 0;        // Find the bucket with the key using double hashing        while (keys[index] != key && keys[index] != -1) {            index = (index + i * stepSize) % capacity;            i++;        }        // Check if the key is found        if (keys[index] == key) {            return values[index];        } else {            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);    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)    return 0; }

In this implementation, we use two hash functions hashFunction1 and hashFunction2 to compute the hash value and the step size, respectively. The insert and search functions use double hashing to resolve collisions and insert or search for key-value pairs in the hash table.