Lecture 364:- Quadratic Probing

Quadratic probing is another collision resolution technique used in hash tables. When a collision occurs (i.e., the computed hash value already corresponds to an occupied bucket), quadratic probing searches for the next available bucket by using a quadratic function to calculate the next index.

Here's how quadratic probing works:

1. Compute the hash value (hash code) of the key using the 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 quadratic function to calculate the next index to probe.
4. Repeat step 3 until an empty bucket is found or the entire hash table is scanned.

The quadratic function used to calculate the next index is often of the form:

cssCopy code

nextIndex = (currentIndex + i^2) % capacity

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

Quadratic probing is called "quadratic" because the probe sequence forms a quadratic pattern. Unlike linear probing, it does not suffer from clustering, as it systematically explores a quadratic pattern around the initial hash index. However, quadratic probing can still lead to secondary clustering, and its performance depends on the load factor of the hash table.

Here's a C++ implementation of a hash table using quadratic probing 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;    // Hash function to compute the hash value of a key    int hashFunction(int key) {        return key % capacity;    } 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 = hashFunction(key);        int i = 0;        // Find the next available bucket using quadratic probing        while (keys[index] != -1) {            index = (index + i * i) % 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 = hashFunction(key);        int i = 0;        // Find the bucket with the key using quadratic probing        while (keys[index] != key && keys[index] != -1) {            index = (index + i * i) % 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 vectors keys and values to store the keys and values in the hash table. The insert function inserts a new key-value pair using quadratic probing, and the search function looks for a key and returns its corresponding value using the same quadratic probing approach.