Lecture 363:- Let's Code Linear Probing

Here's a 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 code, we define a HashTable class with a constructor that initializes the hash table with a given size. The hash table is implemented using two vectors keys and values, where each element in the keys vector stores the key, and the corresponding element in the values vector stores the value associated with that key. The hashFunction calculates the index of the bucket where the key-value pair should be stored. If there is a collision (i.e., the calculated index is already occupied), linear probing is used to find the next available bucket. The insert function inserts a key-value pair using linear probing, and the search function searches for a key and returns its corresponding value using the same linear probing approach.