В информатике , динамический совершенный хеширования является метод программирования для разрешения коллизий в хэш - таблице структуры данных . [1] [2] [3] Хотя этот метод потребляет больше памяти, чем его аналоги в хэш-таблицах, [ необходима цитата ] , он полезен в ситуациях, когда быстрые запросы, вставки и удаления должны выполняться для большого набора элементов.
Подробности
Статический случай
Схема FKS
Проблема оптимального статического хеширования впервые была решена Фредманом, Комлосом и Семереди. [4] В своей статье 1984 года [1] они подробно описывают схему двухуровневой хеш-таблицы, в которой каждый сегмент хеш-таблицы (первого уровня) соответствует отдельной хеш-таблице второго уровня. Ключи хешируются дважды - первое значение хеш-функции соответствует определенному сегменту в хеш-таблице первого уровня; второе значение хеш-функции дает позицию этой записи в хеш-таблице второго уровня этого сегмента. При построении таблицы второго уровня гарантируется отсутствие конфликтов (т.е. идеальное хеширование ). Следовательно, в худшем случае стоимость поиска гарантированно будет равна O (1) . [2]
В статическом случае нам заранее дается набор из x записей, каждая из которых имеет уникальный ключ. Фредман, Комлос и Семереди выбирают хеш-таблицу первого уровня с размером s = 2 (x-1) ведра. [2]
Для построения x записей разделяются на s сегментов функцией хеширования верхнего уровня, где s = 2 (x-1) . Затем для каждого сегмента с k записями таблица второго уровня выделяется с k 2 слотами, и ее хеш-функция выбирается случайным образом из универсального набора хеш-функций, так что она не имеет коллизий (то есть идеальная хеш-функция ) и сохраняется рядом с хеш-таблицей. Если случайно выбранная хеш-функция создает таблицу с коллизиями, новая хеш-функция выбирается случайным образом до тех пор, пока не будет гарантирована таблица без коллизий. Наконец, с помощью хэша без конфликтов k записей хешируются в таблицу второго уровня.
Квадратичный размер пространства k 2 гарантирует, что случайное создание таблицы с коллизиями происходит нечасто и не зависит от размера k , обеспечивая линейное амортизированное время построения. Хотя каждая таблица второго уровня требует квадратичного пространства, если ключи, вставленные в хэш-таблицу первого уровня, равномерно распределены , структура в целом занимает ожидаемое пространство O ( n ), поскольку размеры корзины с большой вероятностью малы . [1]
Хэш-функция первого уровня специально выбрана таким образом, чтобы для конкретного набора из x уникальных значений ключа общее пространство T, используемое всеми хэш-таблицами второго уровня, ожидало пространства O ( n ), а более конкретно T Фредман, Комлос и Семереди показали, что с учетом универсального семейства хеш-функций по крайней мере половина этих функций обладает этим свойством. [2]
Динамический кейс
Dietzfelbinger et al. представляет алгоритм динамического словаря, который, когда набор из n элементов постепенно добавляется к словарю, запросы членства всегда выполняются в постоянное время и, следовательно, O (1) в худшем случае время, общее требуемое хранилище составляет O (n) (линейно) , и O (1) ожидаемое амортизированное время вставки и удаления ( амортизированное постоянное время ).
В динамическом случае, когда ключ вставляется в хеш-таблицу, если его запись в соответствующей подтаблице занята, то говорят, что происходит коллизия, и подтаблица перестраивается на основе ее нового общего количества записей и случайно выбранной хеш-функции. Поскольку коэффициент загрузки таблицы второго уровня поддерживается низким (1 / k ), перестройка выполняется нечасто, а амортизированная ожидаемая стоимость вставок равна O (1). [2] Аналогично, амортизированная ожидаемая стоимость удалений составляет O (1). [2]
Кроме того, в динамическом случае неизвестны конечные размеры таблицы верхнего уровня или любой из подтаблиц. Один из методов сохранения ожидаемого O ( n ) пространства таблицы - это запрос на полную реконструкцию, когда произошло достаточное количество вставок и удалений. По результатам, полученным Dietzfelbinger et al., [2], пока общее количество вставок или удалений превышает количество элементов на момент последней конструкции, амортизированная ожидаемая стоимость вставки и удаления остается равной O (1) с полным повторным хешированием. принимая во внимание.
Реализация динамического идеального хеширования Дитцфельбингером и соавт. использует эти концепции, а также ленивое удаление , что показано в псевдокоде ниже.
Реализация псевдокода
Найдите
функция Locate ( x ) равна j : = h ( x ) if (позиция h j ( x ) подтаблицы T j содержит x (не удалена)) return ( x находится в S ) end if else return ( x не находится в S ) конец еще конец
Вставлять
Во время вставки новой записи x в j увеличивается счетчик глобальных операций count .
Если x существует в j , но помечен как удаленный, то отметка удаляется.
Если x существует в j или в подтаблице T j и не помечен как удаленный, то говорят, что произошла коллизия, и таблица T j второго уровня j- го сегмента перестраивается с другой случайно выбранной хеш-функцией h j .
функция Insert ( x ) - это count = count + 1; если ( количество > M ) FullRehash ( x ); конец, если иначе j = h ( x ); if (Позиция h j (x) подтаблицы T j содержит x ) if ( x помечен как удаленный) удалить маркер удаления; конец, если конец, если еще b j = b j + 1; if ( b j <= m j ), если позиция h j ( x ) в T j пуста сохранить x в позиции h j ( x ) из T j ; end 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 ; конец за конец, если иначе FullRehash ( x ); конец еще конец еще конец еще конец конец еще конец
Удалить
Удаление x просто помечает x как удаленное без удаления и увеличивает счетчик . В случае как вставок, так и удалений, если счетчик достигает порога M, вся таблица перестраивается, где M является некоторым постоянным кратным размеру S в начале новой фазы . Здесь фаза означает время между полными перестройками. Обратите внимание , что здесь -1 в «Delete ( х )» является представлением элемента , который не находится в множестве всех возможных элементов U .
функция Delete ( x ) равна count = count + 1; j = h ( x ); если положение ч J ( х ) из субтаблицы Tj содержит х метки х как удаленные; end if else return (x не является членом S); конец иначе if ( count > = M ) FullRehash (-1); конец, если конец
Полная перестройка
Полное восстановление из таблицы S первых начинается, удалив все элементы , помеченные как удаленные , а затем установку следующего порогового значения M до некоторых постоянная кратного размера S . Хеш-функция, которая разбивает S на s ( M ) подмножеств, где размер подмножества j равен s j , периодически выбирается случайным образом до тех пор, пока:
Наконец, для каждой подтаблицы T j хеш-функция h j повторно случайным образом выбирается из H sj до тех пор, пока h j не станет инъективным по элементам T j . Ожидаемое время для полного перестроения таблицы S с размером n составляет O ( n ). [2]
функция FullRehash ( x ) : Помещает все неотмеченные элементы T в список L ; если ( x находится в U ) добавить x к L ; конец, если количество = длина списка 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 ; конец для для всех й на список L J магазина х в положении ч J ( х ) от T J ; конец за концом
Смотрите также
Рекомендации
- ^ a b c Фредман, М.Л., Комлос, Дж., и Семереди, Э. 1984. Сохранение разреженной таблицы с 0 (1) временем доступа в наихудшем случае. J. ACM 31, 3 (июнь 1984 г.), 538-544 http://portal.acm.org/citation.cfm?id=1884#
- ^ a b c d e f g h Дицфельбингер, М., Карлин, А., Мельхорн, К., Мейер-ауф-дер-Хайде, Ф., Ронерт, Х. и Тарьян, RE 1994. «Динамическое идеальное хеширование: верхнее и Нижние границы ». Архивировано 4 марта 2016 г. в Wayback Machine . SIAM J. Comput. 23, 4 (август 1994 г.), 738-761. http://portal.acm.org/citation.cfm?id=182370 doi : 10.1137 / S0097539791194094
- ^ Эрик Демейн, Джефф Линд. 6.897: Расширенные структуры данных . Лаборатория компьютерных наук и искусственного интеллекта Массачусетского технологического института. Весна 2003 г.
- ^ Ага, Чи. «Универсальная конструкция для схемы ФКС» . Нью-Йоркский университет . Нью-Йоркский университет . Проверено 15 февраля 2015 года .[ постоянная мертвая ссылка ]