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

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

Так зачем же вообще рассматривать группирование? Что ж, вероятно, это лучшая структура данных для хеш-таблиц, хранящихся на диске.

Хеш-таблицы на диске

Контроллеры для таких устройств постоянного хранения данных, как жесткие и гибкие диски, дисководы Iomega Zip и ленточные накопители разработаны для поблочного считывания и записи данных. Обычно размер этих блоков равен какой-то степени двойки, например, 512, 1024 или 4096 байт. Поскольку контроллер должен выполнить считывание всего блока даже в том случае, когда требуется всего несколько байт, имеет смысл попытаться извлечь выгоду из подобного поведения.

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

Примером такого применения служит система пункта продажи в большом продуктовом супермаркете. В магазине могут продаваться сотни тысяч различных наименований товаров, из которых средний покупатель приобретает, скажем, не больше сотни (а то и десятка). Это идеальное применение для хеш-таблицы: каждый товар в магазине известен по его всемирному шифру продукта (UPC -Universal Product Code), т.е. 12-значному строковому значению, которое представляет собой уникальный ключ каждого товара. С учетом этого, приложение в кассовом пункте использует сканированный универсальный код товара с целью его хеширования в хеш-таблицу, а затем в запись, соответствующую товару.

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

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

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

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

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