Войти
В информатике динамическое идеальное хеширование - это метод программирования для разрешения коллизий в хэш-таблице структура данных. Хотя этот метод потребляет больше памяти, чем его аналоги из хэш-таблицы, он полезен в ситуациях, когда быстрые запросы, вставки и удаления должны выполняться для большого набора элементов.
Проблема оптимального статическое хеширование было впервые решено Фредманом, Комлосом и Семереди. В своей статье 1984 года они подробно описывают схему двухуровневой хеш-таблицы, в которой каждый сегмент хеш-таблицы (первого уровня) соответствует отдельной хеш-таблице второго уровня. Ключи хешируются дважды - первое значение хеш-функции соответствует определенному сегменту в хеш-таблице первого уровня; второе значение хеш-функции указывает позицию этой записи в хеш-таблице второго уровня этого сегмента. При построении таблицы второго уровня гарантируется отсутствие конфликтов (т.е. идеальное хеширование ). Следовательно, стоимость поиска гарантированно будет O(1) в наихудшем случае.
В статическом случае нам дается набор из x записей, каждая один с уникальным ключом, заблаговременно. Фредман, Комлос и Семереди выбирают хеш-таблицу первого уровня с размером s = 2 (x-1) сегментов.
Для построения x записей разделяются на s сегментов функцией хеширования верхнего уровня, где s = 2 (х-1). Затем для каждого сегмента с k записями таблица второго уровня выделяется с k слотами, и ее хэш-функция выбирается случайным образом из набора универсальной хеш-функции, так что это коллизия -free (т.е. идеальная хэш-функция ) и сохраняется вместе с хеш-таблицей. Если случайно выбранная хеш-функция создает таблицу с коллизиями, новая хеш-функция выбирается случайным образом до тех пор, пока не будет гарантирована таблица без коллизий. Наконец, с помощью хэша без конфликтов k записей хешируются в таблицу второго уровня.
Квадратичный размер k-пространства гарантирует, что случайное создание таблицы с коллизиями происходит нечасто и не зависит от размера k, обеспечивая линейное амортизированное время построения. Хотя каждая таблица второго уровня требует квадратичного пространства, если ключи, вставленные в хэш-таблицу первого уровня, равномерно распределены, структура в целом занимает ожидаемое пространство O (n), поскольку размеры ведра малы с высокая вероятность.
Хэш-функция первого уровня специально выбрана так, чтобы для конкретного набора из x уникальных значений ключа общее пространство T, используемое всеми хэш-таблицами второго уровня, ожидало O (n) пространства, и более конкретно T < s + 4*x. Fredman, Komlós and Szemerédi showed that given a семейство хэш-функций универсального хеширования, по крайней мере половина из этих функций имеет это свойство.
Dietzfelbinger et al. представляет алгоритм динамического словаря, который, когда набор из n элементов постепенно добавляется к словарю, запросы членства всегда выполняются в постоянное время и, следовательно, O (1) в худшем случае время, общее требуемое хранилище составляет O (n) (линейно), и O (1) ожидаемое амортизированное время вставки и удаления (амортизированное постоянное время ).
В динамическом случае, когда ключ вставляется в хэш-таблицу, если его запись в соответствующей подтаблице занята, то считается, что происходит коллизия, и подтаблица перестраивается на основе нового общего количества записей. и случайно выбранная хеш-функция. Поскольку значение таблицы второго уровня остается низким (1 / k), перестройка выполняется нечасто, и амортизированная ожидаемая стоимость вставок составляет O (1). Точно так же амортизированная ожидаемая стоимость удалений равна O (1).
Кроме того, в динамическом случае невозможно определить конечный размер таблицы верхнего уровня или любой из подтаблиц. Один из методов сохранения ожидаемого пространства O (n) таблицы - это запрос на полную реконструкцию, когда произошло достаточное количество вставок и удалений. По результатам, полученным Dietzfelbinger et al., До тех пор, пока общее количество вставок или удалений превышает количество элементов на момент последнего построения, амортизированная ожидаемая стоимость вставки и удаления остается равной O (1) с учетом полного повторного хеширования..
Реализация динамического идеального хеширования Дицфельбингером и др. использует эти концепции, а также отложенное удаление, и это показано в псевдокоде ниже.
Locate (x) is j: = h (x) if(position h j (x) подтаблицы T j содержит x (не удалено)) return (x находится в S) end if else return (x отсутствует в S) end else end
Во время вставки новой записи x в j, счетчик глобальных операций, count увеличивается на единицу.
Если x существует в j, но помечен как удаленный, то метка удаляется.
Если x существует в j или в подтаблице T j, и не помечен как удаленный, то считается, что произошла коллизия, и таблица второго уровня J-сегмента T j перестраивается с другой случайно выбранной хеш-функцией h j.
function Insert (x) is count = count + 1; if (count>M) FullRehash (x); end if else j = h (x);, если (Позиция h j (x) подтаблицы T j содержит x), если (x равно помечено как удаленное) удалить маркер удаления; конец, если конец, если иначе bj= b j + 1; if(bj<= mj) ifпозиция 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; повторения hj= случайно выбранная функция в H sj; до тех пор, пока hjне станет инъективным для элементов L j; для всех y в списке L j сохранить y в позиции h j (y) из T j; end for end else end if else mj= 2 * max {1, m j }; s j = 2 * m j * (m j - 1); if сумма всех s j ≤ 32 * M / s (M) + 4 * M Выделить s j ячеек для T j ; Поместите все немаркированные элементы T j в список L j ; Добавить x в список L j ; b j = длина L j; повторения hj= случайно выбранная функция в H sj; до тех пор, пока hjне станет инъективным для элементов L j; для всех y в списке L j сохранить y в позиции h j (y) из T j; end для end if else FullRehash ( Икс); end else end else end else end else endУдаление x просто отмечает x как удаленный без удаления и увеличивает счетчик. В случае как вставок, так и удалений, если счетчик достигает порога M, вся таблица перестраивается, где M является некоторым постоянным кратным размеру S в начале новой фазы. Здесь фаза означает время между полными перестройками. Обратите внимание, что здесь -1 в «Delete (x)» - это представление элемента, который не входит в набор всех возможных элементов U.
function Delete (x) is count = количество + 1; j = h (x); если позиция h j (x) подтаблицы Tj содержит x, отметить x как удаленное; end if else return (x не является членом S); конец else if(количество>= M) FullRehash (-1); end if end
Полное перестроение таблицы S сначала начинается с удаления всех элементов, помеченных как удаленные, а затем установки следующего порогового значения M на некоторое константа, кратная размеру S. Хеш-функция, которая разбивает S на s (M) подмножеств, где размер подмножества j равен s j, повторно выбирается случайным образом до тех пор, пока:
Наконец, для каждой подтаблицы T j хеш-функция h j многократно случайным образом выбирается из H sj до тех пор, пока h j не станет инъективным для элементов Т к. Ожидаемое время для полного перестроения таблицы S с размером n равно O (n).
function FullRehash (x) is Поместить все немаркированные элементы T в список L; если (x находится в U), добавить x к L; конец, если count = длина списка L; M = (1 + c) * max {count, 4}; repeat h = случайно выбранная функция в H s (M) ; для все j < s(M) form a list Lj для h (x) = j; b j = длина L j ; m j = 2 * b j ; s j = 2 * m j * (m j - 1); конец для до сумма всех s j ≤ 32 * M / s (M) + 4 * M для всех j < s(M) Allocate space sjдля подтаблицы T j; повторение hj= случайно выбранная функция в H sj; до тех пор, пока hjне станет инъективным в элементах списка L j; конец для для все x в списке L j сохранить x в позиции h j (x) из T j; end для end