Двойное хеширование

Двойное хеширование — это метод компьютерного программирования, используемый в сочетании с открытой адресацией в хеш-таблицах для разрешения коллизий хэшей путем использования вторичного хеша ключа в качестве смещения при возникновении коллизии. Двойное хеширование с открытой адресацией — классическая структура данных в таблице. $T$ .

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

Даны две случайные, однородные и независимые хэш-функции. $h_{1}$ и $h_{2}$ , $i$ место в последовательности сегментов для значения $k$ в хеш-таблице $|T|$ ведра это: $h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.$ В целом, $h_{1}$ и $h_{2}$ выбираются из набора универсальных хэш- функций; $h_{1}$ выбран так, чтобы иметь диапазон $\{0,|T|-1\}$ и $h_{2}$ иметь диапазон $\{1,|T|-1\}$ . Двойное хеширование приближает случайное распределение; точнее, попарно независимые хэш-функции дают вероятность $(n/|T|)^{2}$ что любая пара ключей будет следовать одной и той же последовательности.

Выбор ч ₂ (к)

Вторичная хэш-функция $h_{2}(k)$ должен иметь несколько характеристик:

Он никогда не должен давать нулевой индекс.
Он должен пройти через всю таблицу.
Вычисление должно происходить очень быстро.
Он должен быть попарно независимым от $h_{1}(k)$ .
Характеристики распределения $h_{2}$ не имеют значения. Это аналог генератора случайных чисел.
Все $h_{2}(k)$ должно быть относительно простым | Т |.

На практике:

Если для обеих функций используется хеширование деления, делители выбираются как простые числа.
Если | Т | является степенью двойки, первое и последнее требования обычно удовлетворяются, если сделать $h_{2}(k)$ всегда возвращайте нечетное число. Побочным эффектом этого является удвоение вероятности коллизии из-за одного потерянного бита. ^[1]

Анализ

Позволять $n$ быть числом элементов, хранящихся в $T$ , затем $T$ коэффициент загрузки $\alpha =n/|T|$ . То есть начните со случайного, равномерного и независимого выбора двух универсальных хэш- функций. $h_{1}$ и $h_{2}$ построить таблицу двойного хеширования $T$ . Все элементы вставлены $T$ путем двойного хеширования с использованием $h_{1}$ и $h_{2}$ .Учитывая ключ $k$ , $(i+1)$ -st местоположение хэша вычисляется следующим образом:

$h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.$

Позволять $T$ иметь фиксированный коэффициент нагрузки $\alpha :1>\alpha >0$ .Брэдфорд и Катехакис ^[2]показал ожидаемое количество зондов при неудачном поиске в $T$ , все еще использующий эти изначально выбранные хэш-функции, ${\tfrac {1}{1-\alpha }}$ независимо от распределения входов. Достаточно попарной независимости хеш-функций.

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

Варианты

Кандидатская диссертация Питера Диллинджера ^[3] указывает, что двойное хеширование создает нежелательные эквивалентные хэш-функции, когда хэш-функции рассматриваются как набор, как в фильтрах Блума : Если $h_{2}(y)=-h_{2}(x)$ и $h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)$ , затем $h(i,y)=h(k-i,x)$ и наборы хешей $\left\{h(0,x),...,h(k,x)\right\}=\left\{h(0,y),...,h(k,y)\right\}$ идентичны. Это делает столкновение вдвое более вероятным, чем ожидалось. $1/|T|^{2}$ .

Кроме того, существует значительное количество преимущественно перекрывающихся хеш-наборов; если $h_{2}(y)=h_{2}(x)$ и $h_{1}(y)=h_{1}(x)\pm h_{2}(x)$ , затем $h(i,y)=h(i\pm 1,x)$ и сравнение дополнительных хеш-значений (расширение диапазона $i$ ) бесполезно.

Тройное хеширование

Добавление квадратичного члена $i^{2},$ ^[4] $i(i+1)/2$ ( треугольное число ) или даже $i^{2}\cdot h_{3}(x)$ ( тройное хеширование ) ^[5] к хеш-функции несколько улучшает хеш-функцию ^[4] но не решает эту проблему; если:

h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)+k^{2}\cdot h_{3}(x),

h_{2}(y)=-h_{2}(x)-2k\cdot h_{3}(x),

и

h_{3}(y)=h_{3}(x).

затем

{\begin{aligned}h(k-i,y)&=h_{1}(y)+(k-i)\cdot h_{2}(y)+(k-i)^{2}\cdot h_{3}(y)\\&=h_{1}(y)+(k-i)(-h_{2}(x)-2kh_{3}(x))+(k-i)^{2}h_{3}(x)\\&=\ldots \\&=h_{1}(x)+kh_{2}(x)+k^{2}h_{3}(x)+(i-k)h_{2}(x)+(i^{2}-k^{2})h_{3}(x)\\&=h_{1}(x)+ih_{2}(x)+i^{2}h_{3}(x)\\&=h(i,x).\\\end{aligned}}

Улучшенное двойное хеширование

Добавление кубического члена $i^{3}$ ^[4] или $(i^{3}-i)/6$ ( тетраэдрическое число ), ^[1] Проблему решает метод, известный как улучшенное двойное хеширование . Это можно эффективно вычислить путем прямого дифференцирования :

struct key;	/// Opaque/// Use other data types when needed. (Must be unsigned for guaranteed wrapping.)extern unsigned int h1(struct key const *), h2(struct key const *);/// Calculate k hash values from two underlying hash functions/// h1() and h2() using enhanced double hashing.  On return,///     hashes[i] = h1(x) + i*h2(x) + (i*i*i - i)/6./// Takes advantage of automatic wrapping (modular reduction)/// of unsigned types in C.void ext_dbl_hash(struct key const *x, unsigned int hashes[], unsigned int n){	unsigned int a = h1(x), b = h2(x), i;    hashes[i] = a;	for (i = 1; i < n; i++) {		a += b;	// Add quadratic difference to get cubic		b += i;	// Add linear difference to get quadratic		       	// i++ adds constant difference to get linear		hashes[i] = a;	}}

Помимо устранения проблемы коллизий, улучшенное двойное хеширование также устраняет числовые ограничения двойного хеширования на $h_{2}(x)$ свойства, позволяющие использовать хеш-функцию, аналогичную по свойствам (но все же независимую от нее) $h_{1}$ быть использованным. ^[1]

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с Диллинджер, Питер К.; Манолиос, Панайотис (15–17 ноября 2004 г.). Фильтры Блума в вероятностной проверке (PDF) . 5-я Международная конференция по формальным методам в автоматизированном проектировании (FMCAD 2004). Остин, Техас. CiteSeerX 10.1.1.119.628 . дои : 10.1007/978-3-540-30494-4_26 .
^ Брэдфорд, Филипп Г.; Катехакис, Майкл Н. (апрель 2007 г.), «Вероятностное исследование комбинаторных расширителей и хеширования» (PDF) , SIAM Journal on Computing , 37 (1): 83–111, doi : 10.1137/S009753970444630X , MR 2306284 , заархивировано из оригинал (PDF) от 25 января 2016 г.
^ Диллинджер, Питер К. (декабрь 2010 г.). Адаптивное хранилище приближенных состояний (PDF) (кандидатская диссертация). Северо-Восточный университет. стр. 93–112.
^ Перейти обратно: ^а ^б ^с Кирш, Адам; Митценмахер, Майкл (сентябрь 2008 г.). «Меньше хэширования, та же производительность: создание лучшего фильтра Блума» (PDF) . Случайные структуры и алгоритмы . 33 (2): 187–218. CiteSeerX 10.1.1.152.579 . дои : 10.1002/rsa.20208 .
^ Альтернативно определяется треугольным числом, как у Dillinger 2004.

Внешние ссылки

Как кэширование влияет на хеширование , Грегори Л. Хейлеман и Венбин Луо, 2005.
Анимация хэш-таблицы
klib — библиотека C, включающая функцию двойного хеширования.

[Dillinger04-1] Перейти обратно: ^а ^б ^с Диллинджер, Питер К.; Манолиос, Панайотис (15–17 ноября 2004 г.). Фильтры Блума в вероятностной проверке (PDF) . 5-я Международная конференция по формальным методам в автоматизированном проектировании (FMCAD 2004). Остин, Техас. CiteSeerX 10.1.1.119.628 . дои : 10.1007/978-3-540-30494-4_26 .

[2] Брэдфорд, Филипп Г.; Катехакис, Майкл Н. (апрель 2007 г.), «Вероятностное исследование комбинаторных расширителей и хеширования» (PDF) , SIAM Journal on Computing , 37 (1): 83–111, doi : 10.1137/S009753970444630X , MR 2306284 , заархивировано из оригинал (PDF) от 25 января 2016 г.

[Dillinger10-3] Диллинджер, Питер К. (декабрь 2010 г.). Адаптивное хранилище приближенных состояний (PDF) (кандидатская диссертация). Северо-Восточный университет. стр. 93–112.

[Kirsch08-4] Перейти обратно: ^а ^б ^с Кирш, Адам; Митценмахер, Майкл (сентябрь 2008 г.). «Меньше хэширования, та же производительность: создание лучшего фильтра Блума» (PDF) . Случайные структуры и алгоритмы . 33 (2): 187–218. CiteSeerX 10.1.1.152.579 . дои : 10.1002/rsa.20208 .

[5] Альтернативно определяется треугольным числом, как у Dillinger 2004.

[1]

[2]

[3]

[4]

[5]

Выбор ч 2 (к)