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

В информатике , идеальный хэш - функция для множества S является хэш - функция , которая отображает различные элементы S на множество целых чисел, без каких - либо столкновений . С математической точки зрения это инъективная функция .

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

Заявление [ править ]

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

Строительство [ править ]

Идеальная хеш-функция для определенного набора S, которая может быть оценена за постоянное время и со значениями в небольшом диапазоне, может быть найдена с помощью рандомизированного алгоритма в количестве операций, пропорциональных размеру S. Fredman, Komlós & Szemerédi (1984) используют двухуровневую схему для сопоставления набора S из n элементов с диапазоном индексов O ( n ) , а затем сопоставляют каждый индекс с диапазоном хеш-значений. Первый уровень их построения выбирает большое простое число p (больше, чем размер вселенной, из которой извлекается S ), и параметр k, и отображает каждый элемент x из S в индекс

Если k выбирается случайным образом, на этом шаге, вероятно, будут коллизии, но количество элементов n i , которые одновременно отображаются на один и тот же индекс i , вероятно, будет небольшим. На втором уровне их построения каждому индексу i присваиваются непересекающиеся диапазоны из O ( n i 2 ) целых чисел . Он использует второй набор линейных модульных функций, по одной для каждого индекса i , для отображения каждого члена x из S в диапазон, связанный с g ( x ) . [1]

Как показывают Фредман, Комлос и Семереди (1984) , существует такой выбор параметра k , что сумма длин диапазонов для n различных значений g ( x ) равна O ( n ) . Кроме того, для каждого значения g ( x ) существует линейная модульная функция, которая отображает соответствующее подмножество S в диапазон, связанный с этим значением. И k , и функции второго уровня для каждого значения g ( x ) могут быть найдены за полиномиальное времяпутем случайного выбора значений, пока не будет найдено подходящее. [1]

Сама хэш-функция требует пространства памяти O ( n ) для хранения k , p и всех линейных модульных функций второго уровня. Вычисление хеш-значения заданного ключа x может выполняться в постоянное время путем вычисления g ( x ) , поиска функции второго уровня, связанной с g ( x ) , и применения этой функции к x . Модифицированная версия этой двухуровневой схемы с большим количеством значений на верхнем уровне может использоваться для построения идеальной хеш-функции, которая отображает S в меньший диапазон длины n.+ о ( п ) . [1]

Нижняя граница пробела [ править ]

Использование O ( n ) слов информации для хранения функции Fredman, Komlós & Szemerédi (1984) почти оптимально: любая идеальная хеш-функция, которая может быть вычислена за постоянное время, требует, по крайней мере, количества битов, которое пропорционально размер S . [2]

Расширения [ править ]

Динамическое идеальное хеширование [ править ]

Основная статья: Динамическое идеальное хеширование

Использование идеальной хеш-функции лучше всего в ситуациях, когда есть часто запрашиваемый большой набор S , который редко обновляется. Это связано с тем, что любая модификация набора S может привести к тому, что хеш-функция больше не будет идеальной для измененного набора. Решения , которые обновляют хэш - функции в любое время множество модифицируется известны как динамический совершенный хеширования , [3] , но эти методы достаточно сложно реализовать.

Минимальная идеальная хеш-функция [ править ]

Минимальная идеальная хеш-функция - это идеальная хеш-функция, которая сопоставляет n ключей с n последовательными целыми числами - обычно числами от 0 до n - 1 или от 1 до n . Более формальный способ выражения этого: Пусть J и K являются элементами некоторого конечного множества S . Тогда F является минимальной совершенной хеш-функцией тогда и только тогда, когда из F ( j ) = F ( k ) следует j = k ( инъективность ) и существует целое числоa такой, что диапазон F равен a .. a + | S | - 1 . Было доказано, что минимальная совершенная хеш-схема общего назначения требует не менее 1,44 бита на ключ. [4] Наиболее известные в настоящее время схемы минимального идеального хеширования могут быть представлены с использованием менее 1,56 битов на ключ, если дать им достаточно времени.[5]

Сохранение заказа [ править ]

Минимальный идеальный хэш - функция F является порядок сохранения , если ключи приведены в определенном порядке 1 , а 2 , ..., а п и для любых ключей J и K , J < к означает F ( J ) <F ( а к ) . [6]В этом случае значение функции - это просто позиция каждого ключа в отсортированном порядке всех ключей. Простая реализация сохраняющих порядок минимальных совершенных хэш-функций с постоянным временем доступа заключается в использовании (обычной) идеальной хеш-функции или хеширования кукушки для хранения таблицы поиска позиций каждого ключа. Если ключи, подлежащие хешированию, сами хранятся в отсортированном массиве, можно сохранить небольшое количество дополнительных битов на ключ в структуре данных, которая может использоваться для быстрого вычисления хеш-значений. [7] Сохраняющие порядок минимальные совершенные хеш-функции обязательно требуют представления Ω ( n log n ) битов. [8]

Связанные конструкции [ править ]

Простая альтернатива идеальному хешированию, которая также допускает динамические обновления, - это хеширование с кукушкой . Эта схема сопоставляет ключи с двумя или более местоположениями в пределах диапазона (в отличие от идеального хеширования, которое сопоставляет каждый ключ с одним местоположением), но делает это таким образом, что ключи могут быть назначены один к одному местоположениям, в которых они были нанесен на карту. Поиск по этой схеме выполняется медленнее, потому что необходимо проверять несколько местоположений, но, тем не менее, для худшего случая требуется постоянное время. [9]

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

  1. ^ a b c d Фредман, Майкл Л .; Комлос, Янош ; Семереди, Эндре (1984), "Сохранение разреженной таблицы с O (1) В худшем случае время доступа", Журнал ACM , 31 (3): 538, DOI : 10,1145 / 828,1884 , МР  0819156
  2. ^ Фредман, Майкл Л .; Комлоша, Янош (1984), «О величине разделения систем и семейств совершенных хэш - функций», SIAM журнал на алгебраических и дискретных методов , 5 (1): 61-68, DOI : 10,1137 / 0605009 , МР 0731857 .
  3. ^ Дицфельбингер, Мартин; Карлин, Анна ; Мельхорн, Курт ; Мейер ауф дер Хайде, Фридхельм; Ронерт, Ганс; Тарьян, Роберт Е. (1994), "Динамический совершенный хеширования: верхняя и нижняя границы", SIAM журнал по вычислениям , 23 (4): 738-761, DOI : 10,1137 / S0097539791194094 , MR 1283572 .
  4. ^ Belazzougui, Djamal; Ботельо, Фабиано К.; Дицфельбингер, Мартин (2009 г.), «Хеширование, смещение и сжатие» (PDF) , Алгоритмы - ESA 2009: 17-й ежегодный европейский симпозиум, Копенгаген, Дания, 7-9 сентября 2009 г., Proceedings (PDF) , Lecture Notes in Computer Science , 5757 , Берлин:. Springer, С. 682-693, CiteSeerX 10.1.1.568.130 , DOI : 10.1007 / 978-3-642-04128-0_61 , MR 2557794   .
  5. ^ Эспозито, Эммануэль; Мюллер Граф, Томас; Винья, Себастьяно (2020), «RecSplit: Minimal Perfect Hash via Recursive Splitting», 2020 Труды симпозиума по разработке алгоритмов и экспериментам (ALENEX) , Proceedings , стр. 175–185, arXiv : 1910.06416 , doi : 10.1137 / 1.9781611976007. 14.
  6. ^ Дженкинс, Боб (14 апреля 2009 г.), «Минимальное идеальное хеширование с сохранением порядка», в Блэке, Пол Э. (редактор), Словарь алгоритмов и структур данных , Национальный институт стандартов и технологий США , извлечено 2013-03- 05
  7. ^ Belazzougui, Djamal; Болди, Паоло; Паг, Расмус ; Винья, Себастьяно (ноябрь 2008 г.), «Теория и практика монотонного минимального совершенного хеширования», Журнал экспериментальной алгоритмики , 16 , ст. нет. 3,2, 26pp, DOI : 10,1145 / 1963190,2025378.
  8. ^ Фокс, Эдвард А .; Чен, Ци Фань; Daoud, Amjad M .; Хит, Ленвуд С. (июль 1991 г.), «Минимальные совершенные хеш-функции с сохранением порядка и поиск информации» (PDF) , ACM Transactions on Information Systems , Нью-Йорк, Нью-Йорк, США: ACM, 9 (3): 281–308, DOI : 10,1145 / 125187,125200 .
  9. ^ Паг, Расмус ; Rodler, Флемминг Фриче (2004), "Кукушка хэширования", журнал алгоритмов , 51 (2): 122-144, DOI : 10.1016 / j.jalgor.2003.12.002 , МР 2050140 .

Дальнейшее чтение [ править ]

  • Ричард Дж. Чичелли. Minimal Perfect Hash Functions Made Simple , Communications of the ACM, Vol. 23, номер 1, январь 1980 г.
  • Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , третье издание. MIT Press, 2009. ISBN 978-0262033848 . Раздел 11.5: Идеальное хеширование, стр. 267, 277–282. 
  • Фабиано К. Ботельо, Расмус Паг и Нивио Зивиани. «Идеальное хеширование для приложений управления данными» .
  • Фабиано К. Ботельо и Нивио Зивиани . «Внешнее идеальное хеширование для очень больших наборов ключей» . 16-я конференция ACM по управлению информацией и знаниями (CIKM07), Лиссабон, Португалия, ноябрь 2007 г.
  • Джамал Белаццуги, Паоло Болди, Расмус Паг и Себастьяно Винья. «Монотонное минимальное совершенное хеширование: поиск в отсортированной таблице с O (1) обращениями» . В материалах 20-го ежегодного симпозиума ACM-SIAM по дискретной математике (SODA), Нью-Йорк, 2009. ACM Press.
  • Дуглас С. Шмидт, GPERF: A Perfect Hash Function Generator , Отчет C ++, SIGS, Vol. 10, No. 10, ноябрь / декабрь 1998 г.

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

  • gperf - генератор идеальных хеш-кодов C и C ++ с открытым исходным кодом (очень быстрый, но работает только для небольших наборов)
  • Минимальное идеальное хеширование (алгоритм Боба ) Боба Дженкинса
  • cmph : C Minimal Perfect Hashing Library, реализация с открытым исходным кодом для многих (минимальных) идеальных хэшей (работает для больших наборов)
  • Sux4J : монотонное минимальное идеальное хеширование с открытым исходным кодом в Java
  • MPHSharp : идеальные методы хеширования в C #
  • BBHash : минимальная идеальная хеш-функция в C ++ только для заголовков
  • Perfect :: Hash , идеальный генератор хешей на Perl, который делает код C. Имеет раздел "предшествующий уровень техники", на который стоит обратить внимание.