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

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

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

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

Выбор ч2(к)

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

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

На практике:

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

Анализ

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

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

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

Варианты

^{В своей докторской диссертации [3]} Питер Диллинджер указывает, что двойное хеширование создает нежелательные эквивалентные хеш-функции, когда хеш-функции рассматриваются как набор, как в фильтрах Блума : если и , то и наборы хэшей идентичны. Это делает столкновение в два раза более вероятным, чем ожидаемое . ${\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}}$

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

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

Добавление квадратичного члена ^[4] ( треугольного числа ) или даже ( тройного хеширования ) ^[5] к хеш-функции несколько улучшает хеш-функцию ^[4] , но не устраняет эту проблему; если: ${\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)\\&=\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}}}$

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

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

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

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

Смотрите также

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

Ссылки

1. Диллинджер, Питер К.; Манолиос, Панайотис (15–17 ноября 2004 г.). Фильтры Блума в вероятностной верификации (PDF) . 5-я Международная конференция по формальным методам в автоматизированном проектировании (FMCAD 2004). Остин, Техас. CiteSeerX  10.1.1.119.628 . doi :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.01.2016.
3. Диллинджер, Питер С. (декабрь 2010 г.). Адаптивное приближенное хранение состояний (PDF) (диссертация). Северо-Восточный университет. С. 93–112.
4. Кирш, Адам; Митценмахер, Майкл (сентябрь 2008 г.). «Меньше хеширования, та же производительность: создание лучшего фильтра Блума» (PDF) . Случайные структуры и алгоритмы . 33 (2): 187–218. CiteSeerX 10.1.1.152.579 . doi :10.1002/rsa.20208. 
5. Альтернативно определяется с помощью треугольного числа, как в Dillinger 2004.

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

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