Lecture 362:- Linear Probing

Linear probing is a collision resolution technique used in hash tables. When a collision occurs (i.e., the computed hash value already corresponds to an occupied bucket), linear probing searches for the next available bucket in a linear manner until an empty bucket is found.

Here's how linear 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, search for the next available bucket by incrementing the index linearly.
4. Repeat step 3 until an empty bucket is found or the entire hash table is scanned.

To retrieve an element with a specific key, you need to perform the same linear probing process to find the bucket where the element is stored.

Linear probing can lead to clustering, which means consecutive elements with the same hash value will tend to cluster together in the hash table. This clustering can impact the performance of linear probing, as it may increase the average search time.

Here's a simple C++ implementation of a hash table using linear 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);        // Find the next available bucket using linear probing        while (keys[index] != -1) {            index = (index + 1) % capacity;        }        // 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);        // Find the bucket with the key using linear probing        while (keys[index] != key && keys[index] != -1) {            index = (index + 1) % capacity;        }        // 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 linear probing, and the search function looks for a key and returns its corresponding value using the same linear probing approach.