Хеширование табуляции - Tabulation hashing

В Информатика, хеширование таблиц это метод построения универсальные семейства хэш-функций путем объединения поиск в таблице с Эксклюзивный или операции. Впервые он был изучен в виде Зобристское хеширование для компьютерных игр; более поздняя работа Картера и Wegman расширил этот метод на произвольные ключи фиксированной длины. Также были разработаны обобщения хеширования табуляции, которые могут обрабатывать ключи переменной длины, такие как текстовые строки.

Несмотря на свою простоту, хеширование таблиц имеет сильные теоретические свойства, которые отличают его от некоторых других хеш-функций. В частности, он 3-независимый: каждый 3-кортеж ключей с равной вероятностью будет сопоставлен с любым 3-мя кортежем хеш-значений. Однако он не является 4-независимым. Более сложные, но более медленные варианты хеширования таблиц расширяют этот метод до более высоких степеней независимости.

Из-за своей высокой степени независимости хеширование табуляции можно использовать с методами хеширования, которые требуют высококачественной хеш-функции, включая классическое хеширование, кукушка, а MinHash методика оценки размеров множества пересечений.

Метод

Позволять п обозначить количество биты в ключе для хеширования, и q обозначают количество бит, желаемое в выходной хэш-функции. Выберите другой номер р, меньше или равно п; этот выбор является произвольным и контролирует компромисс между временем и использованием памяти методом хеширования: меньшие значения р использовать меньше памяти, но работать медленнее хэш-функции. Вычислить т округляя п/р до следующего большего целого числа; это дает количество р-битовые блоки, необходимые для представления ключа. Например, если р = 8, то an р-битовое число - это байт, и т - количество байтов на ключ. Ключевая идея хеширования табуляции - рассматривать ключ как вектор из т р-битовые числа, используйте Справочная таблица заполнены случайными значениями, чтобы вычислить хеш-значение для каждого из р-битовые числа, представляющие данный ключ, и объединить эти значения с побитовой двоичной Эксклюзивный или операция.^[1] Выбор р следует сделать таким образом, чтобы этот стол не был слишком большим; например, чтобы он поместился в компьютер кэш-память.^[2]

На этапе инициализации алгоритма создается двумерный массив Т размеров 2^р к т, и заполняет массив случайными q-битовые числа. Как только массив Т инициализируется, его можно использовать для вычисления хеш-значения час(Икс) любого заданного ключаИкс. Для этого разделите Икс в р-битовые значения, где Икс₀ состоит из низшего порядка р кусочки Икс, Икс₁ состоит из следующих р биты и др. Например, с выбором р = 8, Икс_я это просто я-й байт Икс. Затем используйте эти значения как индексы в Т и объедините их с эксклюзивной операцией or:^[1]

час(Икс) = Т[0][Икс₀] ⊕ Т[1][Икс₁] ⊕ Т[2][Икс₂] ⊕ ...

История

Первый экземпляр хеширования табуляции Зобристское хеширование, метод хеширования позиций в абстрактных настольных играх, таких как шахматы названный в честь Альберт Линдси Зобрист, опубликовавший его в 1970 году.^[3] В этом методе случайная цепочка битов генерируется для каждой особенности игры, такой как комбинация шахматной фигуры и квадрата на шахматной доске. Затем для хеширования любой игровой позиции битовые строки для характеристик этой позиции объединяются поразрядным исключающим или. Полученное хеш-значение затем можно использовать в качестве индекса в таблица транспонирования. Поскольку каждый ход обычно изменяет только небольшое количество игровых функций, значение Zobrist позиции после хода может быть быстро обновлено на основе значения позиции перед ходом, без необходимости перебирать все особенности позиции.^[4]

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

Универсальность

Картер и Вегман (1979) определить рандомизированную схему для генерации хэш-функций, которые будут универсальный если для любых двух ключей вероятность того, что они столкнуться (то есть они отображаются на то же значение, что и друг друга) 1 /м, куда м - количество значений, которые могут принимать ключи. В следующей статье они определили более сильное свойство. Вегман и Картер (1981): рандомизированная схема генерации хэш-функций k-независимый если для каждого k-комплект ключей, и каждый возможный k-набор значений, вероятность того, что эти ключи сопоставлены с этими значениями, равна 1 /м^k. 2-независимые схемы хеширования автоматически становятся универсальными, и любую универсальную схему хеширования можно преобразовать в 2-независимую схему, сохранив случайное число. Икс как часть фазы инициализации алгоритма и добавления Икс к каждому значению хеш-функции. Таким образом, универсальность по сути совпадает с независимостью от 2. Тем не мение, k-независимость при больших значениях k - это более сильное свойство, которое обеспечивается меньшим количеством алгоритмов хеширования.

В качестве Патрашку и Торуп (2012) Обратите внимание, хеширование таблиц является 3-независимым, но не 4-независимым. Для любого ключа Икс, Т[Икс₀, 0] с одинаковой вероятностью примет любое хеш-значение, а исключение или из Т[Икс₀, 0] с остальными значениями таблицы не изменяет это свойство. Для любых двух ключей Икс и у, Икс с одинаковой вероятностью будет отображаться на любое значение хеш-функции, как и раньше, и есть по крайней мере одна позиция я куда Икс_я ≠ у_я; табличное значение Т[у_я,я] используется при расчете час(у) но не при расчете час(Икс), поэтому даже после значения час(Икс) было определено, час(у) с одинаковой вероятностью будет любым допустимым хеш-значением. Аналогично для любых трех ключей Икс, у, и z, по крайней мере, один из трех ключей имеет положение я где его значение z_я отличается от двух других, так что даже после значений час(Икс) и час(у) определены, час(z) с одинаковой вероятностью будет любым допустимым хеш-значением.^[5]

Однако для четырех ключей это рассуждение не работает, потому что есть наборы ключей ш, Икс, у, и z где ни один из четырех ключей не имеет байтового значения, которое он не разделяет хотя бы с одним из других ключей. Например, если ключи имеют два байта каждый, и ш, Икс, у, и z являются четырьмя ключами, которые имеют либо ноль, либо единицу в качестве байтовых значений, тогда каждое байтовое значение в каждой позиции совместно используется ровно двумя из четырех ключей. Для этих четырех ключей хеш-значения, вычисленные с помощью хеширования табуляции, всегда будут удовлетворять уравнению час(ш) ⊕ час(Икс) ⊕ час(у) ⊕ час(z) = 0, тогда как для 4-независимой схемы хеширования то же уравнение будет удовлетворяться только с вероятностью 1 /м. Следовательно, хеширование табуляции не является 4-независимым.^[5]

Заявление

Поскольку хеширование табуляции является универсальной схемой хеширования, его можно использовать в любом алгоритме, основанном на хешировании, для которого достаточно универсальности. Например, в хеш-цепочка, ожидаемое время на операцию пропорционально сумме вероятностей коллизий, которая одинакова для любой универсальной схемы, как и для действительно случайных хэш-функций, и является постоянной, когда коэффициент загрузки хеш-таблицы постоянен. Следовательно, хеширование табуляции может использоваться для вычисления хэш-функций для хеш-цепочки с теоретической гарантией постоянного ожидаемого времени на операцию.^[6]

Однако универсального хеширования недостаточно, чтобы гарантировать производительность некоторых других алгоритмов хеширования. Например, для линейное зондирование, 5-независимых хэш-функций достаточно сильны, чтобы гарантировать постоянное время работы, но есть 4-независимые хеш-функции, которые не работают.^[7] Тем не менее, несмотря на то, что хеширование таблицы является независимым только от трех, обеспечивает такую ​​же гарантию постоянного времени для линейного зондирования.^[8]

Кукушка хеширования, еще один метод реализации хеш-таблицы, гарантирует постоянное время на поиск (независимо от хеш-функции). Вставки в хеш-таблицу с кукушкой могут завершиться неудачно, что приведет к перестройке всей таблицы, но такие сбои настолько маловероятны, что ожидаемое время на вставку (с использованием либо действительно случайной хеш-функции, либо хеш-функции с логарифмической независимостью) будет постоянным. С другой стороны, при хешировании табуляции наилучшая известная граница вероятности отказа выше, достаточно высока, чтобы нельзя было гарантировать, что вставки займут постоянное ожидаемое время. Тем не менее, хеширование табуляции является адекватным для обеспечения построения хеш-таблицы с кукушкой с линейным ожидаемым временем для статического набора ключей, который не изменяется при использовании таблицы.^[8]

Расширения

Хотя хеширование табуляции, как описано выше («простое хеширование табуляции»), является независимым только от трех, варианты этого метода могут использоваться для получения хэш-функций с гораздо более высокой степенью независимости. Сигел (2004) использует ту же идею использования исключительных операций или для объединения случайных значений из таблицы с более сложным алгоритмом, основанным на графики расширения для преобразования ключевых битов в индексы таблиц, для определения схем хеширования, которые k-независимо от любого постоянного или даже логарифмического значения k. Однако количество поисков в таблицах, необходимых для вычисления каждого значения хеш-функции с использованием вариации хеширования табуляции Зигеля, хотя и является постоянным, все же слишком велико, чтобы быть практичным, и использование расширителей в технике Сигеля также делает его не полностью конструктивным.Thorup (2013) предоставляет схему, основанную на хешировании табуляции, которая быстрее достигает высоких степеней независимости более конструктивным способом. Он отмечает, что использование одного раунда простого хеширования табуляции для расширения входных ключей до шести раз их исходной длины, а затем второй раунд хеширования простое хеширование табуляции на расширенных ключах, приводит к схеме хеширования, число независимости которой экспоненциально в параметре р, количество битов в блоке при разбиении ключей на блоки.

Простая табуляция ограничена ключами фиксированной длины, потому что для каждой позиции блока в ключах необходимо инициализировать другую таблицу случайных значений.Лемир (2012) изучает варианты хеширования табуляции, подходящие для ключей переменной длины, таких как символьные строки. Общий тип схемы хеширования, изученный Лемиром, использует одну таблицу Т индексируется значением блока, независимо от его позиции в ключе. Однако значения из этой таблицы могут быть объединены более сложной функцией, чем побитовое исключающее или. Лемир показывает, что никакая схема этого типа не может быть 3-независимой. Тем не менее, он показывает, что достичь 2-независимости все же возможно. В частности, схема табуляции, которая интерпретирует значения Т[Икс_я] (куда Икс_я как и прежде, я-го блока входа) как коэффициенты многочлен над конечным полем, а затем берет остаток от полученного многочлена по модулю другого многочлена, дает 2-независимую хеш-функцию.

Примечания

1. Морин (2014); Митценмахер и Упфаль (2014).
2. Митценмахер и Упфаль (2014).
3. Thorup (2013).
4. Зобрист (1970).
5. Патрашку и Торуп (2012); Митценмахер и Упфаль (2014).
6. Картер и Вегман (1979).
7. О достаточности 5-независимого хеширования для линейного зондирования см. Паг, Паг и Ружич (2009). Примеры более слабых схем хеширования, которые не работают, см. Патрашку и Торуп (2010).
8. Патрашку и Торуп (2012).

Рекомендации

Вторичные источники

• Морен, Пат (22 февраля 2014 г.), «Раздел 5.2.3: Хеширование табуляции», Структуры открытых данных (в псевдокоде) (0,1 гβ ред.), с. 115–116, получено 2016-01-08.
• Митценмахер, Майкл; Упфаль, Эли (2014), «Некоторые практические рандомизированные алгоритмы и структуры данных», Такер, Аллен; Гонсалес, Теофило; Диас-Эррера, Хорхе (ред.), Справочник по вычислительной технике: информатика и разработка программного обеспечения (3-е изд.), CRC Press, стр. 11-1 - 11-23, ISBN  9781439898529. См., В частности, Раздел 11.1.1: Хеширование табуляции, стр. 11-3 - 11-4.

Основные источники

• Картер, Дж. Лоуренс; Вегман, Марк Н. (1979), «Универсальные классы хеш-функций», Журнал компьютерных и системных наук, 18 (2): 143–154, Дои:10.1016/0022-0000(79)90044-8, МИСТЕР  0532173.
• Лемир, Даниэль (2012), «Универсальность итерационного хеширования для строк переменной длины», Дискретная прикладная математика, 160: 604–617, arXiv:1008.1715, Дои:10.1016 / j.dam.2011.11.009, МИСТЕР  2876344.
• Паг, Анна; Паг, Расмус; Ружич, Милан (2009), «Линейное зондирование с постоянной независимостью», SIAM Журнал по вычислениям, 39 (3): 1107–1120, arXiv:cs / 0612055, Дои:10.1137/070702278, МИСТЕР  2538852.
• Пэтрашку, Михай; Торуп, Миккель (2010), «О k-независимости, требуемой линейным зондированием и минимальной независимостью» (PDF), Труды 37-го Международный коллоквиум по автоматам, языкам и программированию (ICALP 2010), Бордо, Франция, 6-10 июля 2010 г., часть I, Конспект лекций по информатике, 6198, Springer, стр. 715–726, arXiv:1302.5127, Дои:10.1007/978-3-642-14165-2_60, МИСТЕР  2734626.
• Пэтрашку, Михай; Торуп, Миккель (2012), «Сила простого хеширования табуляции», Журнал ACM, 59 (3): Ст. 14, arXiv:1011.5200, Дои:10.1145/2220357.2220361, МИСТЕР  2946218.
• Сигел, Алан (2004), "Об универсальных классах чрезвычайно случайных хэш-функций с постоянным временем", SIAM Журнал по вычислениям, 33 (3): 505–543, Дои:10.1137 / S0097539701386216, МИСТЕР  2066640.
• Торуп, М. (2013), «Простое табулирование, быстрое расширение, двойное табулирование и высокая независимость», Материалы 54-го ежегодного IEEE Симпозиум по основам информатики (FOCS 2013), стр. 90–99, arXiv:1311.3121, Дои:10.1109 / FOCS.2013.18, МИСТЕР  3246210.
• Вегман, Марк Н.; Картер, Дж. Лоуренс (1981), «Новые хеш-функции и их использование для аутентификации и установления равенства», Журнал компьютерных и системных наук, 22 (3): 265–279, Дои:10.1016/0022-0000(81)90033-7, МИСТЕР  0633535.
• Зобрист, Альберт Л. (Апрель 1970 г.), Новый метод хеширования с приложением для игры (PDF), Тех. Представитель 88, Мэдисон, Висконсин: Департамент компьютерных наук, Университет Висконсина.