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

В заключение рассмотрим основной метод, используемый многими методами класса хеш-таблицы - htcFindPrim (листинг 7.19).

Листинг 7.19. Примитив для поиска элемента в хеш-таблице со связыванием

function TtdHashTableChained.htcFindPrim( const aKey : string;

var aInx : integer;

var aParent : pointer): boolean;

var

Inx : integer;

Head, Walker, Parent : PHashedItem;

begin

{вычислить хеш-значение для строки}

Inx := FHashFunc(aKey, FTable.Count);

{предположить, что связный список существует в Inx-ой ячейке}

Head := PHashedItem(FTable.List^[Inx]);

{начать просмотр связного списка с целью поиска ключа}

Parent := Head;

Walker := Head^.hiNext;

while (Walker <> nil) do

begin

{$lFDEFDelphi1}

if (Walker^.hiKey^ = aKey) then begin

{$ELSE}

if (Walker^.hiKey = aKey) then begin

{$ENDIF}

if (ChainUsage = hcuFirst) and (Parent = Head) then begin

Parent^.hiNext := Walker^.hiNext;

Walker^.hiNext := Head^.hiNext;

Head^.hiNext := Walker;

Parent := Head;

end;

aInx := Inx;

aParent := Parent;

Result := true;

Exit;

end;

Parent := Walker;

Walker := Walker^.hiNext;

end;

{достижение этой точки свидетельствует о том, что ключ не найден}

aInx := Inx;

if ChainUsage = hcuLast then

aParent := Parent else

aParent := Head;

Result := false;

end;

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

Если ключ не был найден, мы возвращаем узел в конце списка или заглавный узел - это определяется свойством ChainUsage. Если его значение установлено равным hcuLast, мы возвращаем последний узел, если оно установлено равным hcuFirst - заглавный узел. Таким образом, если вызывающим методом был метод Insert, можно быть уверенным, что новый элемент будет вставлен в требуемое место. Метод возвращает также индекс ячейки.

Если ключ был найден и значением свойства ChainUsage является hcuFirst, необходимо воспользоваться методологией "перемещения в начало" и переместить найденный элемент в первую позицию связного списка. Конечно, в случае использования односвязного списка эта операция проста и эффективна. И, наконец, мы возвращаем родительский узел и индекс ячейки.

Полный исходный код класса TtdHashTableChained можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshChn.pas.

Разрешение конфликтов посредством группирования

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

Чтобы вставить элемент, мы хешируем ключ элемента с целью определения номера ячейки. Затем мы просматриваем все элементы в группе, пока не обнаружим элемент, помеченный как пустой, и присваиваем его элементу, который пытаемся вставить (понятно, что в случае присутствия элемента в группе генерируется ошибка).

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

Если в нужной группе не хватает места, первая возможность заключается в просмотре группы в следующей ячейке и проверке наличия в ней свободного места. Мы продолжаем выполнять эти действия, пока не отыщем пустой элемент, после чего вставляем в него элемент. Этот метод является прямой аналогией алгоритма линейного зондирования (действительно, если длина всех групп равна одному элементу, этот метод является методом линейного зондирования). Следовательно, он сопряжен с такими же проблемами. Например, удаление элементов из хеш-таблицы требует разрыва цепочек зондирования. Если группа не заполнена полностью, можно просто удалить из нее элемент и по одному переместить вверх элементы в группе. Если группа заполнена полностью, элементы этой группы могут вызывать переполнение, переходя в следующую, поэтому мы вынуждены либо помечать элемент как удаленный, либо повторять вставку последующих элементов, включая элементы в следующих группах, пока не встретится пустой элемент группы.

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

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

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

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

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

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