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

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

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

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

Выбор h ₂ (k) [ править ]

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

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

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

Анализ [ править ]

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

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

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

В этой статье отсутствует информация о том, где остальные доказательства / аргументы ?. Пожалуйста, разверните статью, чтобы включить эту информацию. Более подробная информация может быть на странице обсуждения . ( Сентябрь 2019 г. )

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

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

Улучшенное двойное хеширование [ править ]

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

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

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

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

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

${\displaystyle h_{3}(y)=h_{3}(x).}$

тогда

${\displaystyle {\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)\\&=h_{1}(y)+(i-k)h_{2}(x)+(2ki-2k^{2})h_{3}(x)+(k^{2}-2ki+i^{2})h_{3}(x)\\&=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,x).\\\end{aligned}}}$

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

 ключ структуры ; // Непрозрачный extern  unsigned  int  h1 ( struct  key  const  * ),  h2 ( struct  key  const  * );// Вычислить k хеш-значений из двух базовых хеш-функций // h1 () и h2 () с использованием расширенного двойного хеширования. При возврате // hashes [i] = h1 (x) + i * h2 (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  =  h2 ( x ),  i ;для  ( я  =  0 ;  я  <  п ;  я ++ )  {  хеши [ я ]  =  а ; а  + =  Ь ; // Добавляем квадратичную разность, чтобы получить кубический b  + =  i ; // Добавляем линейную разницу, чтобы получить квадратичную  // i ++ добавляет постоянную разницу, чтобы получить линейную } }

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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