What collision resolution algorithms do you know…

Open addressing and chaining method.

Open addressing:

Linear probing: Searching for a free cell occurs sequentially (H + 1, H + 2, ...).
Quadratic probing: Searching for a free cell occurs based on a quadratic function (H + 1², H + 2², ...).
Double hashing: A second hash function is used to determine the step size during search (H + H2, H + 2*H2, ...).

Example of linear probing:

// Simple hash function  
int hash(int key, int tableSize) {  
    return key % tableSize;  
}  

// Searching for a free cell  
int probe_linear(int key, int tableSize, int attempt) {  
    return (hash(key, tableSize) + attempt) % tableSize;  
}  

// Usage example  
int tableSize = 10;  
int key = 23;  
int attempt = 0;  
int index = probe_linear(key, tableSize, attempt); // First attempt  
// If the cell is occupied, increase attempt and repeat

Chaining method: Each cell of the hash table contains a pointer to a linked list (or another container), where elements that collided at this index are stored.

Example of chaining method using std::list:

#include <list>  
#include <vector>  

// Example of hash table with chaining method  
class HashTableChain {  
private:  
    std::vector<std::list<int>> table;  
    int tableSize;  

public:  
    HashTableChain(int size) : tableSize(size) {  
        table.resize(tableSize);  
    }  

    int hash(int key) const {  
        return key % tableSize;  
    }  

    void insert(int key) {  
        int index = hash(key);  
        // Check for duplicates before insertion if required  
        table[index].push_back(key);  
    }  

    bool search(int key) const {  
        int index = hash(key);  
        for (int val : table[index]) {  
            if (val == key) {  
                return true;  
            }  
        }  
        return false;  
    }  
};  

// Usage example  
// HashTableChain ht(10);  
// ht.insert(23);  
// ht.insert(13); // Both will have the same hash (23%10=3, 13%10=3)

Brief comparison:

Algorithm	Advantages	Disadvantages
Open addressing	More cache-efficient, no pointer overhead.	Sensitive to load factor, clustering issues.
Chaining method	Less sensitive to load factor, simple implementation.	Additional pointer overhead, less cache-efficient.

What collision resolution algorithms do you know?