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