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

Для борьбы с коллизиями применяют несколько основных методов:

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

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

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

class HashTable {
    static const int SIZE = 10;
    std::vector<std::list<int>> table;
public:
    HashTable() : table(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 k : table[index]) {
            if (k == key) return true;
        }
        return false;
    }
};

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

Объясните, что происходит при возникновении коллизий в хэш-таблицах и как с ними бороться.