Динамическое идеальное хеширование - Dynamic perfect hashing - Wikipedia

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

подробности

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

Схема FKS

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

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

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

Квадратичный размер k2 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 (Икс)    если (позиция hj(Икс) подтаблицы Тj содержит Икс (не удалено)) вернуть (Икс в S)    конец, если    еще         вернуть (Икс не в S)    конец ещеконец

Вставить

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

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

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

функция Вставить (Икс) является    считать = считать + 1;    если (считать > M) FullRehash (Икс);    конец, если    еще        j = h (Икс);        если (Позиция hj(x) подтаблицы Тj содержит Икс)            если (Икс помечено как удаленное) убрать маркер удаления; конец, если        конец, если        еще            бj = бj + 1;            если (бj <= мj)                 если позиция hj(Икс) из Тj пустой магазин Икс в позиции hj(Икс) из Тj;                конец, если                еще                    Поместите все неотмеченные элементы Тj в списке Lj; Добавить Икс к списку Lj;                    бj = длина Lj;                    повторение                         часj = случайно выбранная функция в ЧАСsj;                    до тех пор часj инъективен на элементах Lj;                    для все y в списке Lj                        магазин y в позиции hj(y) из Тj;                    конец для                конец еще            конец, если            еще                мj = 2 * макс {1, мj};                sj = 2 * мj * (мj - 1);                если сумма всех sj ≤ 32 * M2 / s(M) + 4 * M                     Выделить sj клетки для Тj; Поместите все неотмеченные элементы Тj в списке Lj; Добавить Икс к списку Lj;                    бj = длина Lj;                    повторение                         часj = случайно выбранная функция в ЧАСsj;                    до тех пор часj инъективен на элементах Lj;                    для все y в списке Lj                        магазин y в позиции hj(y) из Тj;                    конец для                конец, если                еще                    FullRehash (Икс);                конец еще            конец еще        конец еще    конец ещеконец

Удалить

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

функция Удалить(Икс) является    считать = считать + 1;    j = h (Икс);    если позиция hj(Икс) подтаблицы Tj содержит Икс        отметка Икс как удалено; конец, если    еще         вернуть (x не является членом S); конец еще    если (считать >= M) FullRehash (-1); конец, есликонец

Полная перестройка

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

Наконец, для каждой подтаблицы Тj хеш-функция часj неоднократно случайно выбирается из ЧАСsj до тех пор часj инъективен на элементах Тj. Ожидаемое время полной перестройки таблицы S с размером п это O (п).[2]

функция FullRehash (Икс) является    Поместите все неотмеченные элементы Т в списке L;    если (Икс в U) добавить Икс к L;    конец, если    считать = длина списка L;    M = (1 + c) * Максимум{считать, 4};    повторение         h = случайно выбранная функция в ЧАСс (М);        для все j < s(M) сформировать список Lj для ч(Икс) = j;            бj = длина Lj;             мj = 2 * бj;             sj = 2 * мj * (мj - 1);        конец для    до тех пор сумма всех sj ≤ 32 * M2 / s(M) + 4 * M    для все j < s(M) Выделить место sj для подтаблицы Тj;        повторение             часj = случайно выбранная функция в ЧАСsj;        до тех пор часj инъективен для элементов списка Lj;    конец для    для все Икс в списке Lj         магазин Икс в позиции hj(Икс) из Тj;    конец дляконец

Смотрите также

использованная литература

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