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

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

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

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

Метод

Основная идея заключается в следующем:

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

Более формально:

Пусть p — количество битов в ключе, подлежащем хешированию, а q — количество бит, которое требуется в выходной хэш-функции. Выберите размер блока r ≤ p ; компьютера выбор размера блока контролирует компромисс между временем и использованием памяти, поэтому его следует делать так, чтобы таблицы не были слишком большими, например, чтобы таблицы помещались в кэш-память . Меньшие блоки используют меньше памяти, но замедляют работу хеш-функции. Вычислите t = ceil( p / r ), количество r -битных блоков, необходимых для представления ключа.

Создайте двумерную 2 ^р × t массив T и заполните его случайными q -битными числами. Теперь T можно использовать для вычисления хэш-значения h ( x ) любого заданного ключа x . Для этого разделите x на r -битовые значения, где x ₀ состоит из младших r бит x , x ₁ состоит из следующих r бит и т. д. Например, если r = 8, то x _i — это просто i -й байт x . Затем используйте эти значения r -бита и позиции в качестве индексов в T и объедините результаты с помощью исключающей операции или:

час ( Икс ) знак равно Т [0][ Икс ₀ ] ⊕ Т [1][ Икс ₁ ] ⊕ Т [2][ Икс ₂ ] ⊕ ... ⊕ Т [т-1][ Икс _т-1 ].

Обратите внимание, что недопустимо использовать одну и ту же таблицу (например, T[0] для каждого xi ₎ , так как тогда хэш-функция не сможет различать строки с одинаковыми , _xi но переставленными по-разному.

код типичного примера с r = t = 8 и q = p Ниже приведен = 64.

// Secret table of random numbers
uint64_t T[8][256];
for (int i = 0; i < 8; i++)
   for (int j = 0; j < 256; j++)
      T[i][j] = getRandomUInt64();

// Simple Tabulation Hash function
uint64_t hash(uint64_t x) {
   uint64_t res = 0;
   for (int i = 0; i < 8; i++)
      res ^= T[i][(char)(x >> 8*i)];
   return res;
}

История

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

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

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

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

Как отмечают Патрашку и Торуп (2012) , хеширование табуляции является независимым от 3, но не от 4. Для любого отдельного ключа x T T [ x ₀ ,0] с равной вероятностью может принимать любое значение хеш-функции, а исключающее или [ x 0 _, 0] с остальными значениями таблицы не меняет это свойство. Для любых двух ключей и y x x с равной вероятностью будет сопоставлен с любым значением хеш-функции, как и раньше, и существует хотя бы одна позиция i , где x _i ≠ y _i ; табличное значение T [ yi _, ), поэтому даже после того, как i ] используется при вычислении h ( y ), но не при вычислении h ( x значение h ( x ) было определено, h ( y ) равно с равной вероятностью может быть любое допустимое значение хеш-функции. Аналогично, для любых трех ключей x , y и z по крайней мере один из трех ключей имеет позицию i , где его значение z _i отличается от двух других, так что даже после значений h ( x ) и h ( y ) определены, h ( z ) с равной вероятностью будет любым действительным значением хеш-функции.

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

Приложение

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

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

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

Расширения

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

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

Смешанная табуляция

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

Идея состоит в том, чтобы выбрать номер $d$ и хешировать $2^{rd+q}$ бит, а не просто $2^{q}$. Это дает $d$ новые «производные символы», которые хэшируются второй хэш-функцией, и два значения объединяются вместе. Формально мы имеем $h_{1}:[2^{p}]\to [2^{rd}]\times [2^{q}]$ и $h_{2}:[2^{rd}]\to [2^{q}]$, обе простые функции табуляции. Если $(v_{1},v_{2})=h_{1}(x)$, то хеш смешанной таблицы определяется как $h(x)=h_{2}(v_{1})\oplus v_{2}.$

В следующем примере показан алгоритм с $p=q=64$, $r=8$ и $d=2$:

int D = 2;
uint128_t T1[8][256];
uint64_t T2[D][256];

// Fill tables with random values
for (int j = 0; j < 256; j++) {
   for (int i = 0; i < 8; i++)
      T1[i][j] = getRandomUInt128();
   for (int i = 0; i < D; i++)
      T2[i][j] = getRandomUInt64();
}

// Compute Mixed Tabulation of x with D derived characters
uint64_t hash(uint64_t x) {
   uint128_t v1v2 = 0;
   for (int i = 0; i < 8; i++)
      v1v2 ^= T1[i][(char)(x >> 8*i)];
   uint64_t v1 = v1v2 >> 64;     // Take v1 from low bits
   uint64_t h = (uint64_t) v1v2; // Take v2 from high bits
   for (int i = 0; i < D; i++)
      h ^= T2[i][(char)(v1 >> 8*i)];
   return h;
}

Смешанная таблица была показана в 2016 году. иметь сильную концентрацию в отношении k -разделов, которые полезны в алгоритмах подсчета отдельных элементов, таких как классический метод Флажоле и Мартина .

Ссылки

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

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

Первоисточники

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