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

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

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

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

• 1 Выбор h 2 (k)
• 2 Анализ
• 3 Расширенное двойное хеширование
• 4 См. Также
• 5 Ссылки
• 6 Внешние ссылки

Вторичная хеш-функция $h\; 2\; (k)\; \{\backslash \; displaystyle\; h\_\; \{2\}\; (k)\}$должен иметь несколько характеристик:

• он никогда не должен давать нулевой индекс
• он должен циклически проходить через всю таблицу
• он должен быть очень быстрым для вычисления
• его должен быть попарно независимым от $h\; 1\; (k)\; \{\backslash \; displaystyle\; h\_\; \{1\}\; (k)\}$
• Характеристики распределения $h\; 2\; \{\backslash \; displaystyle\; h\_\; \{2\}\}$неактуальны. Это аналогично генератору случайных чисел - необходимо только, чтобы $h\; 2\; \{\backslash \; displaystyle\; h\_\; \{2\}\}$был "относительно простым" с | T |.

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

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

$h\; (i,\; k)\; =\; (h\; 1\; (k)\; +\; i\; \cdot \; h\; 2\; (k))\; mod\; |\; Т\; |.\; \{\backslash \; displaystyle\; h\; (i,\; k)\; =\; (h\_\; \{1\}\; (k)\; +\; i\; \backslash \; cdot\; h\_\; \{2\}\; (k))\; \{\backslash \; bmod\; \{|\}\}\; T\; |.\}$

Пусть $T\; \{\; \backslash \; displaystyle\; T\}$с фиксированным коэффициентом нагрузки $\alpha :\; 1>\alpha >0\; \{\backslash \; displaystyle\; \backslash \; alpha:\; 1>\backslash \; alpha>0\}$.

<12097>Брэдфорд и Катехакис показал ожидаемое количество зондов для неудачного поиска в $T\; \{\backslash \; displaystyle\; T\}$, все еще используя эти изначально выбранные хэш-функции, составляет $1\; 1\; -\; \alpha \; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{1-\; \backslash \; alpha\}\}\}$независимо от распределения входных данных. Достаточно попарной независимости хэш-функций.

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

В диссертации Питера Диллинджера указывается, что двойное хеширование создает нежелательные эквивалентные хеш-функции, когда хеш-функции обрабатываются как набор, как в фильтрах Блума : Если $h\; 2\; (y)\; =\; -\; h\; 2\; (x)\; \{\backslash \; displaystyle\; h\_\; \{2\}\; (y)\; =\; -\; h\_\; \{2\}\; (x)\}$и $h\; 1\; (y)\; знак\; равно\; час\; 1\; (Икс)\; +\; К\; \cdot \; час\; 2\; (Икс)\; \{\backslash \; Displaystyle\; H\_\; \{1\}\; (Y)\; =\; H\_\; \{1\}\; (X)\; +\; К\; \backslash \; CDOT\; H\_\; \{2\}\; (X)\}$, затем $h\; (i,\; y)\; =\; h\; (k\; -\; i,\; x)\; \{\backslash \; displaystyle\; h\; (i,\; y)\; =\; h\; (ki,\; x)\}$и наборы хешей $\{ч\; (0,\; х),...,\; h\; (k,\; x)\}\; =\; \{h\; (0,\; y),...\; час\; (к,\; y)\}\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{h\; (0,\; x),...,\; час\; (k,\; x)\; \backslash \; right\; \backslash \}\; =\; \backslash \; left\; \backslash \; \{h\; (0,\; y),...,\; h\; (k,\; y)\; \backslash \; right\; \backslash \}\}$идентичны. Это увеличивает вероятность столкновения в два раза по сравнению с ожидаемым $1\; /\; |\; Т\; |\; 2\; \{\backslash \; displaystyle\; 1\; /\; |\; T\; |\; ^\; \{2\}\}$.

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

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

$час\; 1\; (y)\; =\; час\; 1\; (x)\; +\; k\; \cdot \; час\; 2\; (x)\; +\; k\; 2\; \cdot \; час\; 3\; (x),\; \{\backslash \; displaystyle\; h\_\; \{1\}\; (y)\; =\; h\_\; \{1\}\; (\; x)\; +\; k\; \backslash \; cdot\; h\_\; \{2\}\; (x)\; +\; k\; ^\; \{2\}\; \backslash \; cdot\; h\_\; \{3\}\; (x),\}$

$h\; 2\; (y)\; =\; -\; h\; 2\; (x)\; -\; 2\; k\; \cdot \; h\; 3\; (х),\; \{\backslash \; displaystyle\; h\_\; \{2\}\; (y)\; =\; -\; h\_\; \{2\}\; (x)\; -2k\; \backslash \; cdot\; h\_\; \{3\}\; (x),\}$и

$h\; 3\; (\; у)\; =\; h\; 3\; (х).\; \{\backslash \; displaystyle\; h\_\; \{3\}\; (y)\; =\; h\_\; \{3\}\; (x).\}$

, тогда

$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)\; -\; 2\; kh\; 3\; (x))\; +\; (k\; -\; i)\; 2\; h\; 3\; (x)\; =\; h\; 1\; (y)\; +\; (i\; -\; k)\; h\; 2\; (x)\; +\; (2\; ki\; -\; 2\; k\; 2)\; h\; 3\; (x)\; +\; (k\; 2\; -\; 2\; ki\; +\; i\; 2)\; h\; 3\; (\; х)\; =\; h\; 1\; (y)\; +\; (i\; -\; k)\; h\; 2\; (x)\; +\; (i\; 2\; -\; k\; 2)\; h\; 3\; (x)\; =\; 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,\; Икс).\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{выровнен\}\; ч\; (ки,\; у)\; =\; ч\_\; \{1\}\; (у)\; +\; (ки)\; \backslash \; cdot\; h\_\; \{2\}\; (у)\; +\; (ки)\; ^\; \{2\}\; \backslash \; cdot\; h\_\; \{3\; \}\; (y)\; \backslash \backslash \; =\; h\_\; \{1\}\; (y)\; +\; (ki)\; (-\; h\_\; \{2\}\; (x)\; -2kh\_\; \{3\}\; (x))\; +\; (ki)\; ^\; \{2\}\; h\_\; \{3\}\; (\; x)\; \backslash \backslash \; =\; h\_\; \{1\}\; (y)\; +\; (ik)\; h\_\; \{2\}\; (x)\; +\; (2ki-2k\; ^\; \{2\})\; h\_\; \{3\}\; (x)\; +\; (k\; ^\; \{2\}\; -2ki\; +\; i\; ^\; \{2\})\; h\_\; \{3\}\; (x)\; \backslash \backslash \; =\; h\_\; \{1\}\; (y)\; +\; (ik)\; h\_\; \{2\}\; (x)\; +\; (i\; ^\; \{2\}\; -k\; ^\; \{2\})\; h\_\; \{3\}\; (x)\; \backslash \backslash \; =\; h\_\; \{1\}\; (x)\; +\; kh\_\; \{2\}\; (x)\; +\; k\; ^\; \{2\}\; h\_\; \{3\}\; (x)\; +\; (ik)\; h\_\; \{2\}\; (x)\; +\; (i\; ^\; \{2\}\; -k\; ^\; \{2\})\; h\_\; \{3\}\; (x)\; \backslash \backslash \; =\; h\_\; \{1\}\; (x)\; +\; ih\_\; \{2\}\; (x)\; +\; i\; ^\; \{2\}\; h\_\; \{3\}\; (x)\; \backslash \backslash \; =\; h\; (i,\; x).\; \backslash \backslash \backslash \; end\; \{align\}\}\}$

Добавление кубического члена $i\; 3\; \{\backslash \; displaystyle\; i\; ^\; \{3\}\}$или $(i\; 3\; -\; i)\; /\; 6\; \{\backslash \; displaystyle\; (i\; ^\; \{3\}\; -i)\; /\; 6\}$(a тетраэдрическое число ), действительно решает проблему, метод, известный как расширенное двойное хеширование . Это может быть эффективно вычислено с помощью прямого дифференцирования :

структурного ключа; // Непрозрачный extern unsigned int h1 (struct key const *), div class="ht" (struct key const *); // Вычислить k хеш-значений из двух базовых хеш-функций // h1 () и div class="ht" () с использованием расширенного двойного хеширования. При возврате // hashes [i] = h1 (x) + i * div class="ht" (x) + (i * i * i - i) / 6 // Использует преимущества автоматической упаковки (модульное сокращение) // беззнаковых типов в C. void hash (struct key const * x, unsigned int hashes, unsigned int n) {unsigned int a = h1 (x), b = div class="ht" (x), я; for (i = 0; i < n; i++) { hashes[i] = a; a += b; // Add quadratic difference to get cubic b += i; // Add linear difference to get quadratic // i++ adds constant difference to get linear } }

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

• Как кеширование влияет на хеширование Грегори Л. Heileman and Wenbin Luo 2005.
• Анимация хеш-таблицы
• klib библиотека C, которая включает функцию двойного хеширования.