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

Double hashing

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

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

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

Выбор h2(k)

Вторичная хеш-функция должен иметь несколько характеристик:

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

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

Анализ

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

Позволять иметь фиксированный коэффициент загрузки .

Брэдфорд и Катехакис[1]показал ожидаемое количество зондов для неудачного поиска в , все еще используя эти изначально выбранные хэш-функции, независимо от распределения входов. Достаточно попарной независимости хеш-функций.

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

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

Кандидатская диссертация Питера Диллинджера[2] указывает, что двойное хеширование создает нежелательные эквивалентные хеш-функции, когда хеш-функции рассматриваются как набор, как в Фильтры Блума: Если и , тогда и наборы хешей идентичны. Это делает столкновение вдвое более вероятным, чем ожидалось. .

Кроме того, имеется значительное количество в основном перекрывающихся хэш-наборов; если и , тогда , и сравнение дополнительных хеш-значений (расширение диапазона ) не помогает.

Добавление квадратичного члена [3] треугольное число) или даже (тройное хеширование) к хеш-функции несколько улучшает хеш-функцию[3] но не решает эту проблему; если:

и

тогда

Добавление кубический член [3] или тетраэдрическое число),[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 ++ добавляет постоянную разницу, чтобы получить линейную	}}

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

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

  1. ^ Брэдфорд, Филип Дж .; Катехакис, Майкл Н. (Апрель 2007 г.), «Вероятностное исследование комбинаторных расширителей и хеширования» (PDF), SIAM Журнал по вычислениям, 37 (1): 83–111, Дои:10.1137 / S009753970444630X, Г-Н 2306284, заархивировано из оригинал (PDF) на 2016-01-25.
  2. ^ Диллинджер, Питер С. (декабрь 2010 г.). Адаптивное приблизительное хранилище состояний (PDF) (Кандидатская диссертация). Северо-Восточный университет. С. 93–112.
  3. ^ а б c Кирш, Адам; Митценмахер, Майкл (Сентябрь 2008 г.). «Меньше хеширования, та же производительность: создание лучшего фильтра Блума» (PDF). Случайные структуры и алгоритмы. 33 (2): 187–218. CiteSeerX 10.1.1.152.579. Дои:10.1002 / rsa.20208.
  4. ^ Диллинджер, Питер С .; Манолиос, Панайотис (15–17 ноября 2004 г.). Фильтры Блума в вероятностной проверке (PDF). 5-я международная конференция по формальным методам автоматизированного проектирования (FMCAD 2004). Остин, Техас. CiteSeerX 10.1.1.119.628. Дои:10.1007/978-3-540-30494-4_26.

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