Что такое коллизия в хеш-таблицах и как с ней работать?

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

Методы разрешения коллизий:

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

   c

2. Метод открытой адресации (Open Addressing): При коллизии ищется следующая свободная ячейка в таблице согласно некоторому правилу пробирования. Элементы хранятся непосредственно в ячейках самой таблицы.

   • Линейное пробирование (Linear Probing): Ищется следующая ячейка по формуле (hash(key) + i) % TABLE_SIZE, где i увеличивается на 1 при каждой попытке.
   • Квадратичное пробирование (Quadratic Probing): Ищется следующая ячейка по ф