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

В информатике динамическое идеальное хеширование — это метод программирования для разрешения коллизий в структуре данных хеш-таблицы . [ ^{1] [2] [3]} Хотя этот метод потребляет больше памяти, чем его аналоги в хеш-таблицах, ^{[ требуется ссылка ]} этот метод полезен в ситуациях, когда необходимо выполнять быстрые запросы, вставки и удаления для большого набора элементов.

Проблема оптимального статического хеширования была впервые решена в общем виде Фредманом, Комлошем и Семереди. ^[4] В своей статье 1984 года ^[1] они подробно описали двухуровневую схему хеш-таблицы, в которой каждый блок хеш-таблицы (первого уровня) соответствует отдельной хеш-таблице второго уровня. Ключи хешируются дважды — первое значение хеш-функции сопоставляется с определенным блоком в хеш-таблице первого уровня; второе значение хеш-функции дает позицию этой записи в хеш-таблице второго уровня этого блока. Таблица второго уровня гарантированно не содержит коллизий (т. е. идеальное хеширование ) при построении. Следовательно, стоимость поиска гарантированно составляет O(1) в худшем случае . ^[2]

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

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

Квадратичный размер пространства гарантирует, что случайное создание таблицы с коллизиями происходит нечасто и не зависит от размера k , обеспечивая линейное амортизированное время построения. Хотя каждая таблица второго уровня требует квадратичного пространства, если ключи, вставленные в хэш-таблицу первого уровня, распределены равномерно , структура в целом занимает ожидаемое пространство, поскольку размеры сегментов с высокой вероятностью малы . ^[1]${\displaystyle к^{2}}$${\displaystyle O(n)}$

Функция хэширования первого уровня специально выбирается таким образом, чтобы для определенного набора x уникальных значений ключей общее пространство T , используемое всеми таблицами хэширования второго уровня, имело ожидаемое пространство, а точнее . Фредман, Комлош и Семереди показали, что при наличии универсального семейства хэширования хэш-функций по крайней мере половина этих функций обладает этим свойством. ^[2]${\displaystyle O(n)}$${\displaystyle T<s+4\cdot x}$

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

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

Кроме того, окончательные размеры таблицы верхнего уровня или любой из подтаблиц неизвестны в динамическом случае. Один из методов поддержания ожидаемого пространства таблицы заключается в том, чтобы инициировать полную реконструкцию, когда произошло достаточное количество вставок и удалений. Согласно результатам, полученным Dietzfelbinger et al. ^[2] , пока общее количество вставок или удалений превышает количество элементов на момент последнего построения, амортизированная ожидаемая стоимость вставки и удаления сохраняется с учетом полного перехеширования.${\displaystyle O(n)}$${\displaystyle O(1)}$

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

функция Locate( x ) is  j  := h( x ) if (позиция h j ( x ) подтаблицы T j содержит x (не удалено)) return ( x is in S ) end if  else  return ( x is not in S ) end else end

Во время вставки новой записи x в j увеличивается глобальный счетчик операций count .

Если x существует в j , но помечен как удаленный, то отметка удаляется.

Если x существует в j или в подтаблице T _j и не помечен как удаленный, то говорят, что произошла коллизия, и таблица второго уровня j - ^го контейнера T _j перестраивается с другой случайно выбранной хеш-функцией h _j .

функция Вставить( x ) равна  count = count + 1; если ( count > M ) FullRehash( x ); конец if  else  j = h( x ); если (Позиция h j (x) подтаблицы T j содержит x ) если ( x помечен как удаленный) удалить маркер удаления; конец если  конец если  иначе  b j = b j + 1; если ( b j <= m j ) если позиция h j ( x ) из T j пуста сохранить x в позиции h j ( x ) списка T j ; конец if  else Поместить все непомеченные элементы списка T j в список L j ; Добавить x к списку L j ; b j = длина L j ; повторить  h j = случайно выбранная функция в H sj ; пока  h j не станет инъективным для элементов L j ; для всех y в списке L j сохранить y в позиции h j ( y ) из T j ; конец для  конца иначе  конец если  иначе  m j = 2 * max{1, m j }; s j = 2 * m j * ( m j - 1); если сумма всех s j ≤ 32 * M 2 / s ( M ) + 4 * M Выделить s j ячеек для T j ; Поместить все непомеченные элементы T j в список L j ; Добавить x к списку L j ; b j = длина L j ; повторить  h j = случайно выбранная функция в H sj ; пока  h j не станет инъективным для элементов L j ; для всех y в списке L j сохранить y в позиции h j ( y ) из T j ; конец для  конец if  else FullRehash( x ); конец else  конец else  конец else  конец else конец

Удаление x просто помечает x как удаленный без удаления и увеличивает count . В случае как вставок, так и удалений, если count достигает порогового значения M, вся таблица перестраивается, где M — некоторая константа, кратная размеру S в начале новой фазы . Здесь phase относится к времени между полными перестройками. Обратите внимание, что здесь -1 в "Delete( x )" является представлением элемента, который не входит в набор всех возможных элементов U .

Функция Delete( x ) равна  count = count + 1; j = h( x ); если позиция h j ( x ) подтаблицы Tj содержит x, пометить x как удаленный; конец, если  иначе  вернуть (x не является членом S); конец,  если иначе ( count >= M ) ПолныйПерехеш(-1); конец если конец

Полная перестройка таблицы S сначала начинается с удаления всех элементов, помеченных как удаленные, а затем установки следующего порогового значения M на некоторое постоянное значение, кратное размеру S. Хэш-функция, которая разбивает S на s ( M ) подмножеств, где размер подмножества j равен s _j , многократно выбирается случайным образом до тех пор, пока:

${\displaystyle \sum _{0\leq j\leq s(M)}s_{j}\leq {\frac {32M^{2}}{s(M)}}+4M.}$

Наконец, для каждой подтаблицы T _j хэш-функция h _j многократно случайным образом выбирается из H _sj до тех пор, пока h _j не станет инъективной на элементах T _j . Ожидаемое время для полной перестройки таблицы S размером n составляет O( n ). ^[2]

функция FullRehash( x ) — помещает все неотмеченные элементы T в список L ; если ( x находится в U ) добавить x к L ; конец, если  count = длина списка L ; M = (1 + c ) * max{ count , 4}; повторить h = случайно выбранная функция в H s(M) ; для всех j < s ( M ) сформировать список L j для h( x ) = j ; b j = длина L j ; m j = 2 * b j ; s j = 2 * m j * ( m j - 1); закончить  до тех пор, пока сумма всех s j ≤ 32 * M 2 / s ( M ) + 4 * M  для всех j < s ( M ) Выделить место s j для подтаблицы T j ; повторить  h j = случайно выбранную функцию в H sj ; пока  h j не станет инъективным для элементов списка L j ; конец для  для всех x в списке L j сохранить x в позиции h j ( x ) из T j ; конец для конца

• Идеальное хеширование