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

Двойное хеширование — это метод компьютерного программирования, используемый в сочетании с открытой адресацией в хеш-таблицах для разрешения коллизий хэшей путем использования вторичного хеша ключа в качестве смещения при возникновении коллизии. Двойное хеширование с открытой адресацией — классическая структура данных в таблице. $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)$ всегда возвращайте нечетное число. Побочным эффектом этого является удвоение вероятности коллизии из-за одного потерянного бита.

Анализ

Позволять $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$. Брэдфорд и Катехакис показал ожидаемое количество зондов при неудачном поиске в $T$, все еще использующий эти изначально выбранные хэш-функции, ${\tfrac {1}{1-\alpha }}$ независимо от распределения входов. Достаточно попарной независимости хэш-функций.

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

Варианты

Кандидатская диссертация Питера Диллинджера указывает, что двойное хеширование создает нежелательные эквивалентные хэш-функции, когда хэш-функции рассматриваются как набор, как в фильтрах Блума : Если $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},$ $i(i+1)/2$ ( треугольное число ) или даже $i^{2}\cdot h_{3}(x)$ ( тройное хеширование ) к хеш-функции несколько улучшает хеш-функцию но не решает эту проблему; если:

$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}$ или $(i^{3}-i)/6$ ( тетраэдрическое число ), Проблему решает метод, известный как улучшенное двойное хеширование . Это можно эффективно вычислить путем прямого дифференцирования :

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}$ быть использованным.

См. также

• Хеширование с кукушкой
• 2-вариантное хеширование

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

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