Хеширование с двумя вариантами

Эта статья, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его , проверив сделанные утверждения и добавив встроенные цитаты . Заявления, содержащие только оригинальные исследования, следует удалить. ( Май 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

2-выбор хеширования , также известный как 2-выбор логического вывода , является «вариант хэш - таблицы , в которой ключи добавляют хеширования с двумя хеш - функций . Ключ помещается в позицию массива с помощью клавиш меньше (сталкивающихся). Некоторые Схема разрешения коллизий необходима, если ключи не хранятся в корзинах. Средняя стоимость успешного поиска равна , где - количество ключей, а - размер массива. Большинство коллизий с высокой вероятностью ». ^[1]${\ Displaystyle О (2+ (м-1) / п)}$${\ displaystyle m}$${\ displaystyle n}$${\ Displaystyle \ журнал _ {2} \ пер п + \ тета (м / п)}$

Как это работает [ править ]

Хеширование с двумя вариантами использует две хэш-функции h ₁ ( x ) и h ₂ ( x ), которые работают как ожидаемые хэш-функции (т. Е. Отображение целых чисел из вселенной в указанный диапазон). Две хеш-функции должны быть независимыми и не коррелировать друг с другом. Наличие двух хеш-функций позволяет любому ключу x иметь до двух потенциальных местоположений для хранения на основе значений соответствующих выходов, h ₁ ( x ) и h ₂ ( x). Важно отметить, что, хотя есть две хэш-функции, есть только одна таблица; обе хэш-функции сопоставляются с местоположениями в этой таблице.

Реализация [ править ]

Наиболее важными функциями реализации хеширования в этом случае являются вставка и поиск.

• Вставка: при вставке значения обеих хеш-функций вычисляются для вставляемого объекта. Затем объект помещается в ведро, которое содержит меньше объектов. Если сегменты равны по размеру, по умолчанию используется значение h ₁ ( x ).
• Поиск: эффективный поиск выполняется путем поиска нужного значения в обоих сегментах (местоположениях сегментов, которым сопоставлены h ₁ ( x ) и h ₂ ( x )).

Производительность [ править ]

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

Ожидаемый размер сегмента при использовании хеширования с двумя вариантами: θ (log (log ( n ))) . Это улучшение произошло благодаря рандомизированной концепции, известной как « Сила двух вариантов» .

Использование двух хеш-функций дает существенные преимущества по сравнению с одной хеш-функцией. Если используется более двух хэш-функций, улучшение (и никаких изменений в статистике ожидаемого порядка) не будет: «Дополнительные хеш-функции уменьшают максимум только на постоянный коэффициент». ^[2]

Некоторые люди рекомендуют в некоторых кэшах ЦП тип хеширования с двумя вариантами, называемый двусторонним асинхронно-ассоциативным кешем . ^[3]

2-левое хеширование - использование двух хеш-таблиц равного размера n / 2 и асимметричное разрешение связей путем помещения ключа в левую хеш-таблицу - имеет меньше коллизий и, следовательно, более высокую производительность, чем хеширование с двумя вариантами с одной большой хеш-таблицей размера n. . ^{[4] [ требуется полная ссылка ]}

Ссылки [ править ]

 Эта статья включает материалы, являющиеся общественным достоянием  из  документа NIST :  Black, Paul E. «Хеширование с двумя вариантами» . Словарь алгоритмов и структур данных .

Дальнейшее чтение [ править ]

• Азар, Йоси; Бродер, Андрей З .; Карлин, Анна Р .; Упфаль, Эли (23–25 мая 1994 г.), «Сбалансированное распределение (расширенная аннотация)» (PDF) , Материалы двадцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '94 , Монреаль, стр. 593–602, CiteSeerX  10.1.1.38.5375 , DOI : 10,1145 / 195058,195412 , ISBN 0897916638, S2CID  1014349
• Азар, Йоси; Бродер, Андрей З .; Карлин, Анна Р .; Упфаль, Эли (1999), «Сбалансированное распределение» (PDF) , SIAM J. Comput. , 29 (1): 180–200, DOI : 10.1137 / S0097539795288490