Идеальное динамическое хеширование - Википедия - Dynamic perfect hashing

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

подробности

Статический случай

Схема FKS

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

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

Строить, Икс записи разделены на s ведра функцией хеширования верхнего уровня, где s = 2 (х-1). Затем для каждого ведра с k записей, таблица второго уровня выделяется с k² слоты, и его хеш-функция выбирается случайным образом из универсальная хеш-функция установить так, чтобы он не сталкивался (т. е. идеальная хеш-функция ) и хранится рядом с хеш-таблицей. Если случайно выбранная хеш-функция создает таблицу с коллизиями, новая хеш-функция выбирается случайным образом до тех пор, пока не будет гарантирована таблица без коллизий. Наконец, с хешем без коллизий k записи хешируются в таблицу второго уровня.

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

Хэш-функция первого уровня специально выбрана так, чтобы для конкретного набора из x значений уникального ключа общее пространство T, используемое всеми хэш-таблицами второго уровня, ожидалось O (п) пространство, а точнее, T универсальное хеширование семейство хэш-функций, по крайней мере, половина этих функций имеет это свойство.^[2]

Динамический случай

Dietzfelbinger et al. представляет алгоритм динамического словаря, который, когда набор из n элементов постепенно добавляется к словарю, запросы членства всегда выполняются в постоянное время и, следовательно, O (1) в худшем случае время, общее требуемое хранилище составляет O (n) (линейно) , и O (1) ожидаемое амортизированное время вставки и удаления (амортизированное постоянное время ).

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

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

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

Реализация псевдокода

Найдите
функция Найдите (Икс) является j : = h (Икс) если (позиция h_j(Икс) подтаблицы Т_j содержит Икс (не удалено)) вернуть (Икс в S) конец, если еще вернуть (Икс не в S) конец ещеконец
Вставить
Во время вставки новой записи Икс в j, счетчик глобальных операций, считать, увеличивается.
Если Икс существует в j, но помечен как удаленный, затем отметка снимается.
Если Икс существует в j или в подтаблице Т_j, и не помечен как удаленный, то считается, что произошла коллизия, и j^th стол второго уровня ведра Т_j перестраивается с помощью другой случайно выбранной хеш-функции час_j.
функция Вставить (Икс) является считать = считать + 1; если (считать > M) FullRehash (Икс); конец, если еще j = h (Икс); если (Позиция h_j(x) подтаблицы Т_j содержит Икс) если (Икс помечено как удаленное) убрать маркер удаления; конец, если конец, если еще б_j = б_j + 1; если (б_j <= м_j) если позиция h_j(Икс) из Т_j пустой магазин Икс в позиции h_j(Икс) из Т_j; конец, если еще Поместите все неотмеченные элементы Т_j в списке L_j; Добавить Икс к списку L_j; б_j = длина L_j; повторение час_j = случайно выбранная функция в ЧАС_sj; до тех пор час_j инъективен на элементах L_j; для все y в списке L_j магазин y в позиции h_j(y) из Т_j; конец для конец еще конец, если еще м_j = 2 * макс {1, м_j}; s_j = 2 * м_j * (м_j - 1); если сумма всех s_j ≤ 32 * M² / s(M) + 4 * M Выделить s_j клетки для Т_j; Поместите все неотмеченные элементы Т_j в списке L_j; Добавить Икс к списку L_j; б_j = длина L_j; повторение час_j = случайно выбранная функция в ЧАС_sj; до тех пор час_j инъективен на элементах L_j; для все y в списке L_j магазин y в позиции h_j(y) из Т_j; конец для конец, если еще FullRehash (Икс); конец еще конец еще конец еще конец ещеконец
Удалить
Удаление Икс просто флаги Икс как удалено без удаления и приращений считать. В случае как вставок, так и удалений, если считать достигает порога M перестраивается вся таблица, где M - некоторое постоянное кратное размеру S в начале нового фаза. Вот фаза относится ко времени между полными перестройками. Обратите внимание, что здесь -1 в "Удалить (Икс) "представляет собой представление элемента, который не входит в набор всех возможных элементов U.
функция Удалить(Икс) является считать = считать + 1; j = h (Икс); если позиция h_j(Икс) подтаблицы Tj содержит Икс отметка Икс как удалено; конец, если еще вернуть (x не является членом S); конец еще если (считать >= M) FullRehash (-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.}$
Наконец, для каждой подтаблицы Т_j хеш-функция час_j неоднократно случайно выбирается из ЧАС_sj до тех пор час_j инъективен на элементах Т_j. Ожидаемое время полной перестройки таблицы S с размером п это O (п).^[2]
функция FullRehash (Икс) является Поместите все неотмеченные элементы Т в списке L; если (Икс в U) добавить Икс к L; конец, если считать = длина списка L; M = (1 + c) * Максимум{считать, 4}; повторение h = случайно выбранная функция в ЧАС_{с (М)}; для все j < s(M) сформировать список L_j для ч(Икс) = j; б_j = длина L_j; м_j = 2 * б_j; s_j = 2 * м_j * (м_j - 1); конец для до тех пор сумма всех s_j ≤ 32 * M² / s(M) + 4 * M для все j < s(M) Выделить место s_j для подтаблицы Т_j; повторение час_j = случайно выбранная функция в ЧАС_sj; до тех пор час_j инъективен для элементов списка L_j; конец для для все Икс в списке L_j магазин Икс в позиции h_j(Икс) из Т_j; конец дляконец
Смотрите также

Идеальное хеширование
использованная литература

^ ^а ^б ^c Фредман, М. Л., Комлос, Дж., И Семереди, Э. 1984. Сохранение разреженной таблицы с 0 (1) временем доступа в наихудшем случае. J. ACM 31, 3 (июнь 1984 г.), 538-544 http://portal.acm.org/citation.cfm?id=1884#
^ ^а ^б ^c ^d ^е ^ж ^г ^час Дицфельбингер, М., Карлин, А., Мельхорн, К., Мейер-ауф-дер-Хайде, Ф., Ронерт, Х. и Тарьян, Р. Е. 1994.«Динамическое идеальное хеширование: верхняя и нижняя границы» В архиве 2016-03-04 в Wayback Machine.SIAM J. Comput. 23, 4 (август 1994 г.), 738-761.http://portal.acm.org/citation.cfm?id=182370 Дои:10.1137 / S0097539791194094
^ Эрик Демейн, Джефф Линд.6.897: Расширенные структуры данных.MIT Лаборатория компьютерных наук и искусственного интеллекта. Весна 2003 г.
^ Яп, Чи. «Универсальная конструкция для схемы ФКС». Нью-Йоркский университет. Нью-Йоркский университет. Получено 15 февраля 2015.^{[постоянная мертвая ссылка ]}

[inventor-1] а ^б ^c Фредман, М. Л., Комлос, Дж., И Семереди, Э. 1984. Сохранение разреженной таблицы с 0 (1) временем доступа в наихудшем случае. J. ACM 31, 3 (июнь 1984 г.), 538-544 http://portal.acm.org/citation.cfm?id=1884#

[dietzfelbinger-2] а ^б ^c ^d ^е ^ж ^г ^час Дицфельбингер, М., Карлин, А., Мельхорн, К., Мейер-ауф-дер-Хайде, Ф., Ронерт, Х. и Тарьян, Р. Е. 1994.«Динамическое идеальное хеширование: верхняя и нижняя границы» В архиве 2016-03-04 в Wayback Machine.SIAM J. Comput. 23, 4 (август 1994 г.), 738-761.http://portal.acm.org/citation.cfm?id=182370 Дои:10.1137 / S0097539791194094

[3] Эрик Демейн, Джефф Линд.6.897: Расширенные структуры данных.MIT Лаборатория компьютерных наук и искусственного интеллекта. Весна 2003 г.

[4] Яп, Чи. «Универсальная конструкция для схемы ФКС». Нью-Йоркский университет. Нью-Йоркский университет. Получено 15 февраля 2015.^{[постоянная мертвая ссылка ]}

[1]

[2]

[3]

[4]