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

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

Прежде всего, создадим файл данных, состоящий из множества записей одинакового размера, каждая из которых описывает отдельный элемент. Естественно, для этого мы будем использовать класс TtdRecordFile, описанный в главе 2.

Файл индексов - это, по сути дела, второй файл базы данных хеш-информации. Как и в предыдущем случае, нам не нужно считывать в память весь файл индексов. Например, если бы каждый ключ содержал 10 цифр, а связанный с каждым ключом номер записи имел бы длину, равную 4 байтам, для хранения одного ключа требовалось бы 15 байт (исходя из предположения, что ключ содержит либо ноль в качестве символа-ограничителя, либо байт-префикс, определяющий его длину). Если бы хеш-таблица содержала 100 000 элементов, то для хранения ее индексов в памяти потребовалось бы минимум 1 500 000 байт. Разумеется, мы еще и выделяем дополнительную память под хранение строк ключей хеш-таблицы в куче, что приведет к еще большим накладным расходам (например, в 32-разрядной системе каждая строка кучи содержит три дополнительных символа типа longint). Значительно целесообразнее было бы считывать фрагменты индекса, когда в них возникает необходимость.

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

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

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

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

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

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