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

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

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

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

Выбор h₂(k)

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

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

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

Анализ

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

${ Displaystyle ч (я, к) = (ч_ {1} (к) + я cdot h_ {2} (к)) { 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 час (я, у) = час (к-я, х)}$ и наборы хешей ${ Displaystyle влево {час (0, х), ..., час (к, х) справа } = слева {час (0, y), ..., час (к, y) правильно}}$ идентичны. Это делает столкновение вдвое более вероятным, чем ожидалось. ${ displaystyle 1 / | T | ^ {2}}$.

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

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

${ 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 {выровнен} ч (ки, у) & = ч_ {1} (у) + (ки) cdot h_ {2} (у) + (ки) ^ {2} cdot h_ {3 } (y) & = h_ {1} (y) + (ki) (- h_ {2} (x) -2kh_ {3} (x)) + (ki) ^ {2} h_ {3} ( x) & = h_ {1} (y) + (ik) h_ {2} (x) + (2ki-2k ^ {2}) h_ {3} (x) + (k ^ {2} -2ki + i ^ {2}) h_ {3} (x) & = h_ {1} (y) + (ik) h_ {2} (x) + (i ^ {2} -k ^ {2}) h_ {3} (x) & = h_ {1} (x) + kh_ {2} (x) + k ^ {2} h_ {3} (x) + (ik) h_ {2} (x) + (i ^ {2} -k ^ {2}) h_ {3} (x) & = h_ {1} (x) + ih_ {2} (x) + i ^ {2} h_ {3} (x) & = h (i, x). конец {выровнено}}}$

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

структура ключ;	// Непрозрачныйвнешний беззнаковый int h1(структура ключ const *), h2(структура ключ const *);// Вычислить k хэш-значений из двух базовых хеш-функций// h1 () и h2 () с использованием расширенного двойного хеширования. По возвращении,// хеши [i] = h1 (x) + i * h2 (x) + (i * i * i - i) / 6// Использует преимущества автоматической упаковки (модульное сокращение)// беззнаковых типов в C.пустота хэш(структура ключ const *Икс, беззнаковый int хеши[], беззнаковый int п){	беззнаковый int а = h1(Икс), б = h2(Икс), я;	для (я = 0; я < п; я++) { 		хеши[я] = а;		а += б;	// Добавляем квадратичную разность, чтобы получить кубическую		б += я;	// Добавляем линейную разницу, чтобы получить квадратичную		       	// i ++ добавляет постоянную разницу, чтобы получить линейную	}}

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

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

использованная литература

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

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