Какие алгоритмы разрешения коллизий вы знаете?

Открытая адресация и метод цепочек.

Открытая адресация:

• Линейное зондирование: Поиск свободной ячейки происходит последовательно (H + 1, H + 2, ...).
• Квадратичное зондирование: Поиск свободной ячейки происходит по квадратичной зависимости (H + 1², H + 2², ...).
• Двойное хеширование: Используется вторая хеш-функция для определения шага при поиске (H + H2, H + 2*H2, ...).

Пример линейного зондирования:

// Простая хеш-функция  
int hash(int key, int tableSize) {  
    return key % tableSize;  
}  

// Поиск свободной ячейки  
int probe_linear(int key, int tableSize, int attempt) {  
    return (hash(key, tableSize) + attempt) % tableSize;  
}  

// Пример использования  
int tableSize = 10;  
int key = 23;  
int attempt = 0;  
int index = probe_linear(key, tableSize, attempt); // Первая попытка  
// Если ячейка занята, увеличиваем attempt и повторяем  

Метод цепочек: Каждая ячейка хеш-таблицы содержит указатель на связный список (или другой контейнер), где хранятся элементы, коллизировавшие по данному индексу.

Пример метода цепочек с использованием std::list:

#include <list>  
#include <vector>  

// Пример хеш-таблицы с методом цепочек  
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);  
        // Проверяем на дубликаты перед вставкой, если требуется  
        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;  
    }  
};  

// Пример использования  
// HashTableChain ht(10);  
// ht.insert(23);  
// ht.insert(13); // Оба будут иметь тот же хеш (23%10=3, 13%10=3)  

Краткое сравнение: