🤔 Какие знаешь алгоритмы реализации коллизии?

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

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

🟠Линейное пробирование (Linear Probing)
Просто идём вперёд (с фиксированным шагом 1), пока не найдём свободное место.
Хешируем key1, попадаем в index = 3 → занято.
Проверяем index = 4 → занято.
Проверяем index = 5 → свободно, вставляем!

int hash(int key, int size) {
    return key % size;
}

int linearProbe(int key, int size, int table[]) {
    int index = hash(key, size);
    while (table[index] != -1) { // -1 означает пустую ячейку
        index = (index + 1) % size; // Двигаемся вперёд
    }
    return index;
}

🟠Квадратичное пробирование (Quadratic Probing)
Идём по квадратичному шагу: +1², +2², +3², …

index = (hash(key) + i²) % size;

🟠Двойное хеширование (Double Hashing)
Если ячейка занята, используем вторую хеш-функцию для поиска нового места.

index = (hash1(key) + i * hash2(key)) % size;

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

🟠Связный список (Separate Chaining)
Каждая ячейка – это список (обычно std::list), в который добавляются элементы с одинаковым хешем.

#include <iostream>
#include <list>
#include <vector>

class HashTable {
    std::vector<std::list<int>> table;
    int size;
public:
    HashTable(int s) : size(s), table(s) {}

    void insert(int key) {
        int index = key % size;
        table[index].push_back(key);
    }

    void display() {
        for (int i = 0; i < size; i++) {
            std::cout << i << ": ";
            for (int num : table[i])
                std::cout << num << " -> ";
            std::cout << "NULL\n";
        }
    }
};

int main() {
    HashTable ht(5);
    ht.insert(10);
    ht.insert(15);
    ht.insert(20);
    ht.insert(25);
    ht.display();
}

🟠Хеширование с ко-хешированием (Coalesced Hashing)
Комбинация цепочек и открытой адресации:
В таблице хранятся указатели на следующий элемент с таким же хешем.
Не требует выделения памяти для списков.

Ставь 👍 и забирай 📚 Базу знаний