Расширяемое хеширование

Метод расширяемого хеширования (англ. extendable hashing) заключается в том, что мы представляем хеш-таблицу в качестве нескольких групп, которые имеют определенное количество ячеек. При переполнении группы нам не требуется перехешировать всю таблицу, а лишь перехешировать заполненную группу, разделив ее при этом на две группы. Таким образом вся хеш-таблица никогда не будет полностью заполнена. К тому же при использовании данного метода использование памяти будет наиболее экономичным.

Алгоритм

В начале у нас есть хеш-таблица с первоначальным количеством ячеек. Все эти ячейки будут являться первой группой.Предположим, что каждая группа будет содержать [math] 10 [/math] значений и номер записи каждого значения, чтобы ее можно было извлечь.

Начнем вставлять в таблицу значения вместе с номерами их записей. При наличии только одной группы их можно вставить только в одно место, поэтому после 10 вставок группа заполняется. Разобьем заполненную группу на две группы одинаковых размеров и повторим вставку всех элементов исходной группы в две новые группы. Причем все элементы, которые завершаются нулевым разрядом, поместим в одну группу, а завершающиеся единичным разрядом — в другую. Эти две группы имеют так называемую разрядную глубину (англ. bit—depth), равную одному разряду. Теперь при каждой вставке пары значение/номер записи она будет помещаться в первую или во вторую группу, в зависимости от последнего разряда значения.

Со временем мы заполним еще одну группу. Предположим, что это группа, в которую мы вставляли все значения, завершающиеся 0. Снова разобьем группу на две отдельные группы. На этот раз все элементы, значения которых заканчиваются двумя нулевыми разрядами, т.е. [math]00[/math], будут помещаться в первую группу, а завершающиеся разрядами [math]10[/math] — во вторую группу. Обе группы имеют разрядную глубину, равную 2. Поэтому для определения места вставки необходимо проверять два младших разряда значения. Теперь у нас имеются три группы: в первую вставляются элементы, завершающиеся разрядами [math]00[/math], во вторую — разрядами [math]10[/math], а в третью — просто [math]1[/math]. И так далее.

Для поддержания отображения того, какие значения помещаются в те или иные группы, используется структура, называемая каталогом (англ. catalogue). По существу каталог содержит список всех возможных окончаний групп и связных с ними номеров групп. Вместо того чтобы поддерживать какой—либо причудливый набор значений разрядной глубины и номеров групп, выбранный методом проб и ошибок, каталог поддерживает собственное значение разрядной глубины, равное максимальной разрядной глубине группы, и имеет ячейку для каждого значения этой разрядной глубины.

Вставка в расширяемую хеш-таблицу

При разбиении группы дополняющие друг друга группы не будут размещаться в каталоге по соседству. Для дальнейших рассуждений было бы проще предположить, что записи каталога, соответствующие одной группе, располагаются по соседству, чтобы при разбиении группы дополняющая первую группа помещалась непосредственно за ней.

Для достижения этого следует инвертировать последние разряды хеш-значения при вычислении индексной записи каталога. Так, например, если хеш-значение завершается разрядами [math]001[/math], при поиске мы обратимся не к записи [math]001[/math] каталога, а к записи [math]100[/math] ([math]4[/math], которая соответствует инвертированному значению [math]001[/math]). В результате использование каталога значительно упрощается.

Пример

Рассмотрим выполнение алгоритма на примере, выполняемые при этом действия показаны на рис. Мы начинаем с каталога только с одной записью с индексом [math]0[/math] (a). Принято считать, что в подобной ситуации разрядная глубина равна [math]0[/math]. Мы заполняем единственную группу (назовем ее [math] A [/math] ) и теперь ее нужно разбить. Вначале мы увеличиваем разрядную глубину каталога до [math]1[/math]. Иначе говоря, теперь он будет содержать две записи (b). В результате будут созданы две группы, на первую из которых указывает запись [math]0[/math] (исходная запись [math] A [/math] ), а на вторую — запись [math]1[/math], [math] B [/math] (c). Все элементы, значения которых завершаются разрядом [math]0[/math], помещаются в группу [math] A [/math] , а остальные — в группу [math] B [/math] . Снова заполним группу [math] A [/math] . Теперь разрядную глубину каталога необходимо увеличить с [math]1[/math] до [math]2[/math], чтобы получить четыре группы, доступных для вставки. Перед разделением заполненной группы записи каталога [math]00[/math] и [math]01[/math] будут указывать на исходную группу [math] A [/math] , а записи [math]10[/math] и [math]11[/math] — на группу [math] B [/math] (d). Группа [math] A [/math] разбивается на группу, которая принимает значения с окончанием [math]00[/math] (снова [math] A [/math] ), и группу, которая принимает значения с окончанием [math]10[/math], [math] C [/math] . На группу [math] A [/math] будет указывать запись [math]00[/math] каталога, а на группу [math] C [/math] — запись [math]01[/math] (e). И, наконец, группа [math] C [/math] (на которую указывает запись 01 каталога) заполняется. Нужно снова увеличить разрядную глубину каталога, на этот раз до трех разрядов.

Использование

Чаще всего расширяемое хеширование используется в базах данных т.к. БД могут быть крайне большими и перехеширование всей БД займет продолжительное время при этом лишая пользователей доступа к БД. А при использовании расширяемого хеширования перехешировать придется только малые группы, что не сильно замедлит работу БД.

См. также

• Хеш-таблица
• Разрешение коллизий
• Хеширование кукушки
• Идеальное хеширование
• Перехеширование

Источники информации

• Бакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.
• Дейт К. Дж. — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.