Jump to content

Идеальная хэш-функция

(Перенаправлено с Perfect hashing )
Идеальная хеш-функция для четырех показанных имен.
Минимальная идеальная хеш-функция для четырех показанных имен.

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

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

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

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

Приложение

[ редактировать ]

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

Выполнение идеальных хэш-функций

[ редактировать ]

Важными параметрами производительности для идеального хеширования являются размер представления, время оценки, время построения и, кроме того, требования к диапазону. (среднее количество сегментов на ключ в хеш-таблице). [4] Время оценки может достигать O ( 1 ) , что является оптимальным. [2] [4] Время построения должно быть не менее O ( n ) , поскольку каждый элемент в S необходимо учитывать , а S содержит n элементов. Эта нижняя граница может быть достигнута на практике. [4]

Нижняя граница размера представления зависит от m и n . Пусть m = (1+ε) n и h — идеальная хеш-функция. Хорошее приближение для нижней границы: Битов на элемент. Для минимального идеального хеширования ε = 0 нижняя граница равна log e ≈ 1,44 бита на элемент. [4]

Строительство

[ редактировать ]

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

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

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

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

Более поздний метод построения идеальной хэш-функции описан Белаццуги, Ботельо и Дитцфельбингером (2009) как «хеширование, смещение и сжатие». хеш-функция первого уровня g Здесь также используется для сопоставления элементов с диапазоном из r целых чисел. Элемент x S хранится в ведре B g(x) . [4]

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

Чтобы оценить идеальную хеш-функцию h ( x ), нужно только сохранить отображение σ индекса сегмента g ( x ) на правильную хеш-функцию в последовательности, в результате чего h(x) = Φ σ(g(x)) . [4]

Наконец, чтобы уменьшить размер представления, ( σ(i)) 0 ≤ i < r сжимаются в форму, которая по-прежнему позволяет выполнять оценку за O ( 1 ) . [4]

Этот подход требует линейного времени по n для построения и постоянного времени оценки. Размер представления находится в O ( n ) и зависит от достигнутого диапазона. Например, при m = 1,23 n Белаццуги, Ботельо и Дитцфельбингер (2009) достигли размера представления от 3,03 бит/ключ до 1,40 бит/ключ для приведенного примера набора из 10 миллионов записей, при этом более низкие значения требуют большего времени вычислений. Нижняя граница пространства в этом сценарии составляет 0,88 бит/ключ. [4]

Псевдокод

[ редактировать ]
algorithm hash, displace, and compress is
(1) Split S into buckets Bi := g−1({i})∩S,0 ≤ i < r
(2) Sort buckets Bi in falling order according to size |Bi|
(3) Initialize array T[0...m-1] with 0's
(4) for all i∈[r], in the order from (2), do
(5)     for l1,2,...
(6)         repeat forming Ki{Φl(x)|xBi}
(6)         until |Ki|=|Bi| and Ki∩{j|T[j]=1}=∅
(7)     let σ(i):= the successful l
(8)     for all jKi let T[j]:=1
(9) Transform (σi)0≤i<r into compressed form, retaining O(1) access.

Нижние границы пространства

[ редактировать ]

Использование O ( n ) слов информации для хранения функции Фредмана, Комлоша и Семереди (1984) почти оптимально: любая идеальная хеш-функция, которую можно вычислить за постоянное время. пропорциональное размеру S. требуется как минимум количество битов , [5]

Для минимальных совершенных хеш-функций нижняя граница теоретико-информационного пространства равна

биты/ключ. [4]

Для идеальных хеш-функций сначала предполагается, что диапазон h ограничен n как m = (1+ε) n . По формуле Белаццуги, Ботельо и Дитцфельбингера (2009) и для Вселенной чей размер | У | = u стремится к бесконечности, нижняя граница пространства равна

бит/ключ, минус log( n ) бит в целом. [4]

Расширения

[ редактировать ]

Идентификатор адреса памяти

[ редактировать ]

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

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

[ редактировать ]

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

Минимальная идеальная хэш-функция

[ редактировать ]

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

k-идеальное хеширование

[ редактировать ]

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

(4) for all i∈[r], in the order from (2), do
(5)     for l1,2,...
(6)         repeat forming Ki{Φl(x)|xBi}
(6)         until |Ki|=|Bi| and Ki∩{j|T[j]=k}=∅
(7)     let σ(i):= the successful l
(8)     for all jKi set T[j]←T[j]+1

Сохранение заказа

[ редактировать ]

Минимальная совершенная хеш-функция F сохраняет порядок, если ключи заданы в некотором порядке 1 , a 2 , ..., a n и для любых ключей a j и a k < j a k подразумевает F ( a j ) < F( а к ) . [9] В этом случае значение функции — это просто позиция каждого ключа в отсортированном порядке всех ключей. Простая реализация сохраняющих порядок минимальных совершенных хэш-функций с постоянным временем доступа заключается в использовании (обычной) идеальной хеш-функции для хранения таблицы поиска позиций каждого ключа. В этом решении используется бит, что оптимально в ситуации, когда функция сравнения ключей может быть произвольной. [10] Однако если ключи a 1 , a 2 , ..., a n являются целыми числами, взятыми из вселенной , то можно построить сохраняющую порядок хеш-функцию, используя только кусочки пространства. [11] Более того, эта оценка, как известно, оптимальна. [12]

[ редактировать ]

В то время как хеш-таблицы с хорошей размерностью имеют амортизированное среднее время O(1) (амортизированное среднее постоянное время) для поиска, вставки и удаления, большинство алгоритмов хеш-таблиц страдают от возможных наихудших случаев, которые занимают гораздо больше времени. Время O(1) в худшем случае (постоянное время даже в худшем случае) будет лучше для многих приложений (включая сетевой маршрутизатор и кэши памяти ). [13] : 41 

Лишь немногие алгоритмы хеш-таблиц поддерживают время поиска O(1) в наихудшем случае (постоянное время поиска даже в худшем случае). Те немногие, которые действительно включают: идеальное хеширование; динамическое идеальное хеширование ; кукушка хэширования ; классическое хеширование ; и расширяемое хеширование . [13] : 42–69 

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

  1. ^ Jump up to: Перейти обратно: а б Дитцфельбингер, Мартин; Карлин, Анна ; Мельхорн, Курт ; Мейер ауф дер Хайде, Фридхельм; Ронерт, Ганс; Тарьян, Роберт Э. (1994), «Динамическое идеальное хеширование: верхняя и нижняя границы», SIAM Journal on Computing , 23 (4): 738–761, doi : 10.1137/S0097539791194094 , MR   1283572 .
  2. ^ Jump up to: Перейти обратно: а б с д и Фредман, Майкл Л .; Комлос, Янош ; Семереди, Эндре (1984), «Хранение разреженной таблицы с временем доступа для наихудшего случая O (1) », Журнал ACM , 31 (3): 538, doi : 10.1145/828.1884 , MR   0819156 , S2CID   5399743
  3. ^ Лу, Йи ; Прабхакар, Баладжи ; Бономи, Флавио (2006), «Идеальное хеширование для сетевых приложений», Международный симпозиум IEEE по теории информации , 2006 г., стр. 2774–2778, doi : 10.1109/ISIT.2006.261567 , ISBN  1-4244-0505-Х , S2CID   1494710
  4. ^ Jump up to: Перейти обратно: а б с д и ж г час я дж к л Белазуги, Джамаль; Ботельо, Фабиано К.; Дитцфельбингер, Мартин (2009), «Хеширование, перемещение и сжатие» (PDF) , Алгоритмы - ESA 2009 (PDF) , Конспекты лекций по информатике , том. 5757, Берлин: Springer, стр. 682–693, CiteSeerX   10.1.1.568.130 , doi : 10.1007/978-3-642-04128-0_61 , ISBN  978-3-642-04127-3 , МР   2557794 .
  5. ^ Фредман, Майкл Л .; Комлос, Янош (1984), «О размере разделяющих систем и семейств совершенных хеш-функций», SIAM Journal on Algebraic and Discrete Methods , 5 (1): 61–68, doi : 10.1137/0605009 , MR   0731857 .
  6. ^ Витольд Литвин; Тадеуш Морзи; Готфрид Воссен (19 августа 1998 г.). Достижения в области баз данных и информационных систем . Springer Science+Business Media . п. 254. ИСБН  9783540649243 .
  7. ^ Хагеруп, Торбен; Толи, Торстен (2001), «Эффективное минимальное идеальное хеширование в почти минимальном пространстве» , STACS 2001 , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 317–326, doi : 10.1007/3-540-44693-1_28 , ISBN  978-3-540-41695-1 , получено 12 ноября 2023 г.
  8. ^ Эспозито, Эммануэль; Мюллер Граф, Томас; Винья, Себастьяно (2020), «RecSplit: минимальное идеальное хеширование посредством рекурсивного разделения», 2020 г., Труды симпозиума по разработке алгоритмов и экспериментам (ALENEX) , Материалы , стр. 175–185, arXiv : 1910.06416 , doi : 10.1137/1.978161 1976007. 14 .
  9. ^ Дженкинс, Боб (14 апреля 2009 г.), «Минимально идеальное хеширование, сохраняющее порядок», в Блэке, Поле Э. (ред.), Словарь алгоритмов и структур данных , Национальный институт стандартов и технологий США , получено 5 марта 2013 г.
  10. ^ Фокс, Эдвард А.; Чен, Ци Фань; Дауд, Амджад М.; Хит, Ленвуд С. (июль 1991 г.), «Сохраняющие порядок минимальные совершенные хэш-функции и поиск информации» (PDF) , Транзакции ACM в информационных системах , 9 (3), Нью-Йорк, Нью-Йорк, США: ACM: 281–308, дои : 10.1145/125187.125200 , S2CID   53239140 .
  11. ^ Белазуги, Джамаль; Болди, Паоло; Паг, Расмус ; Винья, Себастьяно (ноябрь 2008 г.), «Теория и практика монотонного минимально совершенного хеширования», Журнал экспериментальной алгоритмики , 16 , ст. нет. 3.2, 26 стр., doi : 10.1145/1963190.2025378 , S2CID   2367401 .
  12. ^ Ассади, Сепер; Фарах-Колтон, Мартин; Кушмаул, Уильям (январь 2023 г.), «Жесткие границы для монотонного минимального идеального хеширования» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2023 г. , Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, стр. 456–476 , arXiv : 2207.10556 , doi : 10.1137/1.9781611977554.ch20 , ISBN  978-1-61197-755-4 , получено 27 апреля 2023 г.
  13. ^ Jump up to: Перейти обратно: а б Тимоти А. Дэвис. «Глава 5 Хеширование» : подраздел «Хеш-таблицы с наихудшим доступом O(1)»
  14. ^ Паг, Расмус ; Родлер, Флемминг Фриш (2004), «Хеширование с кукушкой», Журнал алгоритмов , 51 (2): 122–144, doi : 10.1016/j.jalgor.2003.12.002 , MR   2050140 .

Дальнейшее чтение

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 63e81b795bf6418ec43c0a56eefc14c1__1721647620
URL1:https://arc.ask3.ru/arc/aa/63/c1/63e81b795bf6418ec43c0a56eefc14c1.html
Заголовок, (Title) документа по адресу, URL1:
Perfect hash function - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)