Введение
2-выборное хеширование, также известное как 2-выборное связывание, является вариантом хеш-таблицы, в котором ключи добавляются путем хеширования с использованием двух хеш-функций. Ключ помещается в позицию массива, в которой меньше (столкновений) ключей. Какая-либо схема разрешения коллизий необходима, если ключи не хранятся в корзинах. Средняя стоимость успешного поиска равна , где – количество ключей, а – размер массива. Наибольшее число коллизий составляет с высокой вероятностью.
Как это работает
Двойное хеширование использует две хеш-функции h1(x) и h2(x), которые работают так, как и ожидается от хеш-функций (то есть, отображают целые числа из универсального множества в заданный диапазон). Эти две хеш-функции должны быть независимыми и не коррелировать друг с другом. Наличие двух хеш-функций позволяет любому ключу x иметь до двух возможных позиций для хранения, определяемых значениями соответствующих результатов h1(x) и h2(x). Важно отметить, что, несмотря на наличие двух хеш-функций, используется только одна таблица; обе хеш-функции отображают позиции в этой таблице.
Реализация
Наиболее важными функциями реализации хэширования в данном случае являются вставка и поиск. Вставка: при вставке вычисляются значения обеих хеш-функций для вставляемого объекта. Затем объект помещается в корзину, содержащую меньшее количество объектов. Если корзины одинакового размера, местоположение по умолчанию определяется значением h1(x). Поиск: эффективный поиск осуществляется путем проверки обеих корзин (местоположений корзин, в которые отобразились h1(x) и h2(x)) для поиска нужного значения.
Выступление
Как и в случае со всеми хэш-таблицами, производительность определяется размером наибольшего корзины. Хотя иногда размеры корзин оказываются большими из-за используемых значений и хэш-функций, это случается редко. Наличие двух хэш-функций и, следовательно, двух возможных позиций для каждого значения, делает вероятность появления больших корзин еще меньше. Ожидаемый размер корзины при использовании хеширования с двумя вариантами выбора составляет: θ(log(log(n))). Это улучшение обусловлено рандомизированной концепцией, известной как «Сила двух выборов». Использование двух хэш-функций дает значительные преимущества по сравнению с одной хэш-функцией. Дальнейшее увеличение количества хэш-функций дает незначительное улучшение (и не влияет на ожидаемую статистику порядка): «Дополнительные хэш-функции уменьшают максимум лишь на постоянный множитель». Некоторые специалисты рекомендуют разновидность хеширования с двумя вариантами выбора, называемую двунаправленным скошенным ассоциативным кэшем, в некоторых кэшах процессоров. Хеширование «2 слева» — использование двух хэш-таблиц одинакового размера n/2 с асимметричным разрешением коллизий путем помещения ключа в левую хэш-таблицу — приводит к меньшему количеству коллизий и, следовательно, к более высокой производительности, чем хеширование с двумя вариантами выбора с использованием одной большой хэш-таблицы размером n.