Какие методы существуют для предотвращения или разрешения коллизий при работе с хеш-функциями?

Коллизии в хеш-функциях возникают, когда разные ключи дают одинаковое хеш-значение. Для предотвращения или разрешения коллизий применяются следующие методы:

1. Метод цепочек (chaining) — в каждой ячейке хеш-таблицы хранится связный список элементов с одинаковым хешем. При коллизии новый элемент добавляется в список.

2. Открытая адресация (open addressing) — при коллизии ищется следующая свободная ячейка по определённой последовательности (линейное пробирование, квадратичное пробирование, двойное хеширование).

3. Двойное хеширование — при коллизии вычисляется второе хеш-значение, которое определяет шаг для поиска следующей ячейки.

4. Рехеширование (rehashing) — при достижении определённой загрузки таблицы создаётся новая таблица большего размера, и все элементы перехешируются.

Пример метода цепочек:

struct Node {
    int key;
    Node* next;
};

Node* hashTable[SIZE];

void insert(int key) {
    int hash = key % SIZE;
    Node* newNode = new Node{key, hashTable[hash]};
    hashTable[hash] = newNode;
}