Фундаментальные алгоритмы и структуры данных в 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.

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