Контейнер для коллизий в хеш-таблице

#алгоритм #любой_язык

В каноничной хеш-таблице в случае возниконовения коллизий элементы с равным хешем
помещаются в связный список. Это приводит к тому, что поиск по контейнеру стоит O(n).
Почему для контейнера не использовать другую структуру данных? Например, красно-черное
дерево. Или другую хеш-таблицу с другим хешем. Поиск и удаление в таком случае удешевляется.
Правда, вставка становится заметно дороже. Цена вставки новых элементов перевешивает
цену поиска? Есть ли какие-нибудь библиотеки в любом из современных языков, что позволяют
выбирать контейнер для коллизий? Например, можно было бы придумать такой случай: сначала
я заполняю хеш-таблицу, а после точно знаю, что мне очень сильно понадобится быстрый
поиск - так я возьму и преобразую контейнеры в более подходящие. Или я заранее осознаю
стоимость вставки, но поиск все равно гораздо важней.
    

Ответы

Ответ 1

Поиск будет давать O(n) в случае крайне плохого хэша, когда все элементы будут иметь
один и тот же хэш. При нормально подобранной хэш-функции получается O(1).

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

Вопрос в заложенных в O() константах. При небольших размерах цепочек поиск (и особенно
вставка, когда она играет роль) в них может проводиться быстрее за счет малой константы,
чем в более быстрой, но более сложной структуре.

Более того, тут уже начинают играть свою роль и другие факторы, такие как использование
кэша процессора и т.п. не совсем алгоритмические мелочи.

Так что для достижения максимального быстродействия, пожалуй, есть только один путь
- практически-экспериментальный, и давать он может для каждой связки задача+машина
свое решение...


Ответ 2

Все зависит от решаемой задачи и для каждой задачи можно подобрать соответствующую
структуру данных.

Самая быстрая коллекция элементов - это одноранговый массив, скорость доступа к элементу
которой не намного больше прямого доступа, следовательно идеальная хеш коллекция для
int типа - это массив размером int.Max.

По моим собственным исследованиям (а я делал с десяток разных вариантов хеш таблиц)
наиболее универсальным вариантом является как раз таки "канонический", потому в случае
хорошо распределенного хеша предполагает скорость операции ~O(1). Повторюсь, он наиболее
универсальный.

Конечно в чистом виде доступ O(1) хеш таблицы примерно в 3 раза ниже О(1) массива
из-за дополнительных внутренних проверок, но пока системы не имеют бесконечной памяти
с мгновенным ее выделением в любом объеме, чтобы можно было создавать массивы максимальных
размеров.

С другой стороны если вы имеете жестко ограниченный размер таблицы скажем в 64 элемента,
а хеш заполняемых данных в большинстве случаев кратен 64, то обычный вариант даст ~O(n)
для любой операции и вся прелесть использования хеш таблиц теряется. В этом случае
проще использовать бинарное дерево в чистом виде.