Linear probing overview

Linear probing is a collision resolution technique used in hash tables. When a hash function maps two or more keys to the same index in the array, a collision occurs. In linear probing, when a collision occurs, the hash table looks for the next available index in the array and stores the element there, instead of creating a linked list like in chaining. The search for the next available index is done by sequentially scanning the array starting from the collision index and wrapping around to the beginning of the array if necessary.

Here is an example implementation of a hash table using linear probing in C++:

#include <iostream>
#include <vector>

template <typename K, typename V>
class HashTable {
public:
    static const int TABLE_SIZE = 100;
    std::vector<std::pair<K, V>> table;

    HashTable() {
        table = std::vector<std::pair<K, V>>(TABLE_SIZE);
    }

    int hashFunction(K key) {
        std::hash<K> hashFunction;
        int index = hashFunction(key) % TABLE_SIZE;
        return index;
    }

    void put(K key, V value) {
        int index = hashFunction(key);
        while (table[index].first != K() && table[index].first != key) {
            index = (index + 1) % TABLE_SIZE;
        }
        table[index] = std::make_pair(key, value);
    }

    V get(K key) {
        int index = hashFunction(key);
        while (table[index].first != K()) {
            if (table[index].first == key) {
                return table[index].second;
            }
            index = (index + 1) % TABLE_SIZE;
        }
        throw std::out_of_range("Key not found");
    }

    bool containsKey(K key) {
        int index = hashFunction(key);
        while (table[index].first != K()) {
            if (table[index].first == key) {
                return true;
            }
            index = (index + 1) % TABLE_SIZE;
        }
        return false;
    }

    void remove(K key) {
        int index = hashFunction(key);
        while (table[index].first != K()) {
            if (table[index].first == key) {
                table[index].first = K();
                return;
            }
            index = (index + 1) % TABLE_SIZE;
        }
        throw std::out_of_range("Key not found");
    }
};

int main() {
    HashTable<std::string, int> myHashTable;
    myHashTable.put("one", 1);
    myHashTable.put("two", 2);
    myHashTable.put("three", 3);
    std::cout << myHashTable.get("two") << std::endl;
    myHashTable.remove("one");
    std::cout << myHashTable.containsKey("one") << std::endl;
    return 0;
}

Output:

2
0

In this example, we define a HashTable class to represent the hash table, which has a vector of key-value pairs to store its elements. We provide member functions to insert elements into the hash table, to retrieve elements from the hash table, to check if the hash table contains a given key, and to remove elements from the hash table.

In the main function, we create a HashTable object, insert some elements into the hash table, retrieve an element from the hash table, remove an element from the hash table, and check if the hash table contains a key.