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

В реализации хеш-таблиц (как в std::unordered_map) используются два основных подхода к разрешению коллизий, когда разным ключам соответствует один и тот же хеш (индекс в массиве бакетов):

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

   • Принцип: При коллизии новый элемент добавляется в список соответствующего бакета.
   • Преимущества: Простота реализации, эффективен при высоком коэффициенте заполнения, не требует перестройки таблицы при коллизиях.
   • Недостатки: Дополнительные накладные расходы на память для хранения указателей в узлах списка. Производительность может деградировать до O(n), если многие ключи попадают в один бакет.
   • Использование в C++: std::unordered_map по умолчанию использует метод цепочек.

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

   • Стратегии пробинга:
     • Линейное пробирование: index = (hash(key) + i) % table_size. Может приводить к кластеризации (образованию длинных последовательностей занятых ячеек).
     • Квадратичное пробирование: index = (hash(key) + i^2) % table_size. Уменьшает кластеризацию.
     • Двойное хеширование: index = (hash1(key) + i * hash2(key)) % table_size. Использует вторую хеш-функцию для вычисления шага, что даёт наиболее равномерное распределение.
   • Преимущества: Лучшая локальность данных (все элементы в массиве), может быть эффективнее по памяти (нет указателей).
   • Недостатки: Более сложная реализация, чувствительность к коэффициенту заполнения — при высоком заполнении резко падает производительность, требуется аккуратная обработка удаления элементов (например, с помощью пометки "удалён").

На практике в стандартной библиотеке C++ выбран метод цепочек из-за его предсказуемости и устойчивости к различным сценариям использования. В специализированных высокопроизводительных хеш-таблицах (например, flat_hash_map от Google) часто используется открытая адресация с robin hood hashing или аналогичными оптимизациями.