Какие знаешь способы разрешения хеш коллизий

1️⃣ Как кратко ответить

Существуют два основных способа разрешения хеш коллизий: метод цепочек (chaining) и метод открытой адресации (open addressing). Метод цепочек использует связные списки для хранения всех элементов, имеющих одинаковый хеш. Метод открытой адресации хранит все элементы в самом массиве, используя различные стратегии для поиска следующей свободной ячейки, такие как линейное пробирование, квадратичное пробирование и двойное хеширование.

2️⃣ Подробное объяснение темы

Хеш коллизия возникает, когда два разных ключа имеют одинаковое хеш-значение. Это неизбежно в хеш-таблицах, так как количество возможных хеш-значений ограничено размером таблицы, а количество возможных ключей может быть значительно больше. Для эффективного использования хеш-таблиц необходимо уметь разрешать такие коллизии.

Метод цепочек (Chaining)

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

#include <iostream>
#include <list>
#include <vector>
​
class HashTable {
    std::vector<std::list<int>> table;
    int size;
​
public:
    HashTable(int size) : size(size) {
        table.resize(size);
    }
​
    int hashFunction(int key) {
        return key % size;
    }
​
    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
    }
​
    bool search(int key) {
        int index = hashFunction(key);
        for (int element : table[index]) {
            if (element == key) {
                return true;
            }
        }
        return false;
    }
};
​
int main() {
    HashTable ht(10);
    ht.insert(15);
    ht.insert(25);
    std::cout << ht.search(15) << std::endl; // Вывод: 1 (true)
    std::cout << ht.search(30) << std::endl; // Вывод: 0 (false)
    return 0;
}

• std::vector<std::list<int>> table; — создается вектор списков, где каждый список хранит элементы с одинаковым хеш-значением.
• hashFunction(int key) — простая хеш-функция, которая возвращает индекс в таблице.
• insert(int key) — добавляет элемент в соответствующий список.
• search(int key) — ищет элемент в соответствующем списке.

Метод открытой адресации (Open Addressing)

Метод открытой адресации хранит все элементы непосредственно в массиве. При коллизии используется стратегия поиска следующей свободной ячейки.

Линейное пробирование (Linear Probing)

При линейном пробировании, если ячейка занята, проверяются последующие ячейки.

#include <iostream>
#include <vector>
​
class HashTable {
    std::vector<int> table;
    int size;
    int empty;
​
public:
    HashTable(int size) : size(size), empty(-1) {
        table.resize(size, empty);
    }
​
    int hashFunction(int key) {
        return key % size;
    }
​
    void insert(int key) {
        int index = hashFunction(key);
        while (table[index] != empty) {
            index = (index + 1) % size;
        }
        table[index] = key;
    }
​
    bool search(int key) {
        int index = hashFunction(key);
        int start = index;
        while (table[index] != empty) {
            if (table[index] == key) {
                return true;
            }
            index = (index + 1) % size;
            if (index == start) {
                break;
            }
        }
        return false;
    }
};
​
int main() {
    HashTable ht(10);
    ht.insert(15);
    ht.insert(25);
    std::cout << ht.search(15) << std::endl; // Вывод: 1 (true)
    std::cout << ht.search(30) << std::endl; // Вывод: 0 (false)
    return 0;
}

• std::vector<int> table; — массив для хранения элементов.
• empty — специальное значение, обозначающее пустую ячейку.
• insert(int key) — вставляет элемент, используя линейное пробирование для поиска свободной ячейки.
• search(int key) — ищет элемент, проверяя последовательно ячейки.

Квадратичное пробирование (Quadratic Probing)

Квадратичное пробирование использует квадратичную функцию для поиска следующей ячейки.

Двойное хеширование (Double Hashing)

Двойное хеширование использует вторую хеш-функцию для определения шага пробирования.

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