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

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

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

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

   c

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

   • Линейное пробирование (Linear Probing): Ищется следующая ячейка по формуле (hash(key) + i) % TABLE_SIZE, где i увеличивается на 1 при каждой попытке.
   • Квадратичное пробирование (Quadratic Probing): Ищется следующая ячейка по формуле (hash(key) + i^2) % TABLE_SIZE, где i увеличивается при каждой попытке.
   • Двойное хеширование (Double Hashing): Ищется следующая ячейка по формуле (hash1(key) + i * hash2(key)) % TABLE_SIZE, где i увеличивается при каждой попытке, а hash2 - другая хеш-функция.

   c

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