Обзор методов разрешения коллизий хеширования
Коллизии хеша происходят, когда два разных ключа хешируются в одинаковый индекс в хеш-таблице. Есть две основные категории методов разрешения: раздельное связывание и открытая адресация.
Методы раздельного связывания
Раздельное связывание хранит несколько значений по одному индексу хеша, используя дополнительные структуры данных:
- Раздельное связывание со связным списком — Каждый слот хеш-таблицы содержит связный список всех элементов, вызвавших коллизию. Это просто реализовать и хорошо работает при высокой частоте коллизий.
- Раздельное связывание с головными узлами — Похоже на связные списки, но использует выделенные головные узлы для лучшей организации памяти и более быстрого доступа.
Методы открытой адресации
Открытая адресация ищет альтернативные слоты внутри самой хеш-таблицы, когда происходит коллизия:
- Объединённое хеширование — Комбинирует открытую адресацию со связыванием, используя указатели для обработки коллизий, сохраняя эффективность линейного пробирования.
- Кукушкино хеширование — Использует две хеш-функции и перемещает существующие элементы на их альтернативные позиции, когда нужно вставить новый элемент, гарантируя O(1) время поиска.
- Hopscotch-хеширование — Поддерживает «окрестность», в пределах которой элементы размещаются на ограниченном расстоянии от своей исходной позиции в хеше, балансируя между кэш-эффективностью и скоростью поиска.
- Robin Hood хеширование — Перераспределяет слоты в пользу элементов с более длинными последовательностями пробирования, забирая их у «везунчиков», что снижает разброс времени поиска по всей таблице.
Соображения при выборе
Выбор метода зависит от твоих конкретных требований: раздельное связывание лучше всего подходит при непредсказуемых коэффициентах загрузки, а методы открытой адресации обычно обеспечивают лучшую кэш-локальность и эффективность памяти при умеренной частоте коллизий.