Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Алгоритм, который нам нужно использовать, называется расширяемым хешированием (extendible hashing), и чтобы им можно было воспользоваться, необходимо вернуться к функции хеширования.

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

Теперь функция хеширования будет возвращать значение типа longint. Если вернуться к первоначальной хеш-функции PJW, можно убедиться, что она вычисляла 32-разрядное хеш-значение (фактически, 28-разрядное значение, поскольку значения четырех старших разрядов всегда устанавливались равными 0), а затем выполнялось деление по модулю этого значения на размер таблицы. При использовании расширяемого хеширования заключительное деление по модулю не выполняется. Вместо этого мы используем все хеш-значение полностью.

Означает ли это, что мы получаем хеш-таблицу с 268 миллионами ячеек? Нет, и это вполне согласуется со здравым смыслом. Мы используем только несколько разрядов хеш-значения, и по мере того, как таблица заполняется, мы начинаем использовать все больше разрядов хеш-значения.

Посмотрим, как работает этот алгоритм, на примере заполнения гипотетической хеш-таблицы. Первоначально в таблице имеется одна группа. Предположим, что каждая группа будет содержать 10 хеш-значений и номер записи каждого хеш-значения, чтобы ее можно было извлечь. Обратите внимание, что мы не помещаем в группы сами ключи. При использовании 28-разрядных хеш-значений, маловероятно, чтобы два ключа хешировались в одно и то же значение. (Фактически это будет происходить настолько редко, что для проверки ключей можно извлечь саму запись без заметного замедления всего процесса. Естественно, при этом предполагается, что используемая хеш-функция успешно справляется с рандомизацией.)

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

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

Предположим, что мы продолжаем вставку и заполняем группу 10. Мы снова разбиваем заполненную группу на две и повторяем вставку ее элементов в две новые группы. На этот раз две новые группы будут принимать элементы, завершающиеся разрядами 010 и 110. Таким образом, теперь у нас имеются четыре группы: одна с разрядной глубиной, равной 1, в которую выполняется вставка хеш-значений, завершающихся 1, одна с разрядной глубиной равной 2, содержащая хеш-значения, которые завершаются разрядами 00, и две группы с разрядной глубиной, равной 3, которые предназначены для хеш-значений, завершающихся разрядами 010 и 110.

Почему-то есть уверенность, что читатели уже получили представление о работе расширяемого хеширования, - все остальное не представляет сложности.

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

В рассмотренном нами примере максимальная разрядная глубина группы была равна 3, поэтому разрядная глубина каталога также равна этому значению. Три разряда позволяют образовать восемь комбинаций разрядов: 000, 001, 010, 011, 100, 101, 110 и 111. Все комбинации, которые завершаются 1 (т.е. вторая, четвертая, шестая и восьмая), указывают на одну и ту же группу, принимающую элементы, хеш-значения которых завершаются 1. Аналогично, записи каталога для значений 000 и 100 указывают на одну и ту же группу, в которую помещаются элементы с хеш-значениями, завершающимися разрядами 00.

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

Для достижения этого следует инвертировать последние разряды хеш-значения при вычислении индексной записи каталога. Так, например, если хеш-значение завершается разрядами 001, при поиске мы обратимся не к записи 001 каталога, а к записи 100 (4, которая соответствует инвертированному значению 001). В результате использование каталога значительно упрощается. В нашем примере хеш-значения, которые завершаются разрядами 00, помещаются в запись каталога 000 (0) или 001 (1). Хеш-значения, которые завершаются разрядами 010, помещаются в запись каталога 010 (2). Хеш-значения, которые завершаются разрядами 011, помещаются в запись каталога 011 (3). И, наконец, хеш-значения, которые завершаются разрядом 1, помещаются в записи 100, 101, 110 или 111 (4, 5, 6, 7).