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

Листинг 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). Вместо помещения связного списка в каждую ячейку, в нее помещается группа, которая по существу представляет собой массив элементов фиксированного размера. При создании хеш-таблицы необходимо выделить группу для каждой ячейки и пометить все элементы в каждой группе как "пустые".

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

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

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