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

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

Подробности

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

Схема ФКС

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

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

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

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

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

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

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

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

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

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

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

Найдите

function Locate(x) is
    j := h(x)
    if (position h_j(x) of subtable T_j contains x (not deleted))
        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 .

function Insert(x) is
    count = count + 1;
    if (count > M) 
        FullRehash(x);
    end if
    else
        j = h(x);
        if (Position h_j(x) of subtable T_j contains x)
            if (x is marked deleted) 
                remove the delete marker;
            end if
        end if
        else
            b_j = b_j + 1;
            if (b_j <= m_j) 
                if position h_j(x) of T_j is empty 
                    store x in position h_j(x) of T_j;
                end if
                else
                    Put all unmarked elements of T_j in list L_j;
                    Append x to list L_j;
                    b_j = length of L_j;
                    repeat 
                        h_j = randomly chosen function in H_sj;
                    until h_j is injective on the elements of L_j;
                    for all y on list L_j
                        store y in position h_j(y) of T_j;
                    end for
                end else
            end if
            else
                m_j = 2 * max{1, m_j};
                s_j = 2 * m_j * (m_j - 1);
                if the sum total of all s_j ≤ 32 * M² / s(M) + 4 * M 
                    Allocate s_j cells for T_j;
                    Put all unmarked elements of T_j in list L_j;
                    Append x to list L_j;
                    b_j = length of L_j;
                    repeat 
                        h_j = randomly chosen function in H_sj;
                    until h_j is injective on the elements of L_j;
                    for all y on list L_j
                        store y in position h_j(y) of T_j;
                    end for
                end if
                else
                    FullRehash(x);
                end else
            end else
        end else
    end else
end

Удалить

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

function Delete(x) is
    count = count + 1;
    j = h(x);
    if position h_j(x) of subtable Tj contains x
        mark x as deleted;
    end if
    else 
        return (x is not a member of S);
    end else
    if (count >= M)
        FullRehash(-1);
    end if
end

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

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

$\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]

function FullRehash(x) is
    Put all unmarked elements of T in list L;
    if (x is in U) 
        append x to L;
    end if
    count = length of list L;
    M = (1 + c) * max{count, 4};
    repeat 
        h = randomly chosen function in H_s(M);
        for all j < s(M) 
            form a list L_j for h(x) = j;
            b_j = length of L_j; 
            m_j = 2 * b_j; 
            s_j = 2 * m_j * (m_j - 1);
        end for
    until the sum total of all s_j ≤ 32 * M² / s(M) + 4 * M
    for all j < s(M) 
        Allocate space s_j for subtable T_j;
        repeat 
            h_j = randomly chosen function in H_sj;
        until h_j is injective on the elements of list L_j;
    end for
    for all x on list L_j 
        store x in position h_j(x) of T_j;
    end for
end

См. также

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

Ссылки

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

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

[dietzfelbinger-2] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Дитцфельбингер М., Карлин А., Мельхорн К., Мейер ауф дер Хайде Ф., Ронерт Х. и Тарьян Р.Э. 1994. «Динамическое идеальное хеширование: верхняя и нижняя границы». Архивировано 4 марта 2016 г. на Wayback Machine . СИАМ Дж. Компьютер. 23, 4 (август 1994 г.), 738–761. http://portal.acm.org/citation.cfm?id=182370 дои : 10.1137/S0097539791194094

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

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

[1]

[2]

[3]

[4]