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

Автор книги: Джулиан Бакнелл

сообщить о нарушении

Текущая страница: 18 (всего у книги 36 страниц)

Вставим третий элемент. В первом случае это может привести к увеличению размера кластера с вероятность 4/n. Во втором случае это может привести к образованию кластера с вероятностью 5/n. В третьем случае это может привести к образованию кластера с вероятностью 6/n. Продолжая такие логические рассуждения, мы приходим к выводу, что вероятность образования кластера после вставки трех элементов равна 6/n – 8/n(^2^), что приблизительно в два раза больше предыдущего значения вероятности. Можно было бы продолжить вычисление вероятностей для все большего количества элементов, но это лишено особого смысла. Вместо этого обратите внимание, что при вставке элемента и при наличии кластера из двух элементов вероятность увеличения этого кластера равна 4/n. При наличии кластера с тремя элементами вероятность его увеличения возрастает до 5/n и т.д.

Как видите, после образования кластеров вероятность их увеличения все время возрастает.

Кластеры влияют на среднее количество зондирований, требуемых как для обнаружения существующего элемента (попадания), так и для выяснения того, что элемент в хеш-таблице отсутствует (промаха). Кнут показал, что среднее количество зондирований для обнаружения попадания приблизительно равно 1/2(1 + 1/(1 -x)), где x – количество элементов в хеш-таблице, деленное на размер хеш-таблицы (эту величину называют коэффициентом загрузки (load factor)), а среднее количество зондирований для обнаружения промаха приблизительно равно 1/2(1 + 1/(1 -x)(^2^)) [13]. Несмотря на простоту этих выражений, математические выкладки, приводящие к их получению, весьма сложны.

Используя приведенные формулы, можно показать, что если хеш-таблица заполнена примерно наполовину, для обнаружения попадания требуется в среднем приблизительно 1.5 зондирования, а для обнаружения промаха – 2.5 зондирования. Если же таблица заполнена на 90%, для обнаружения попадания требуется в среднем 5.5 зондирований, а для обнаружения промаха – 55.5 зондирований. Как видите, при использовании хеш-таблицы, в которой в качестве схемы разрешения конфликтов применяется линейное зондирование, таблица должна быть заполнена не более чем на две трети, чтобы эффективность оставалась приемлемой. Если это удастся, мы снизим влияние, которое кластеризация оказывает на эффективность хеш-таблицы.

–

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

–

Удаление элементов из хеш-таблицы с линейным зондированием

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

Предположим, что функция хеширования для ключей Smith, Jones и Brown создает следующие хеш-значения: 42, 42 и 43. Их добавление в хеш-таблицу в указанном порядке приводит к возникновению ситуации, показанной ниже:

Элемент 41: <пусто>

Элемент 42: Smith

Элемент 43: Jones

Элемент 44: Brown

Элемент 45: <пусто>

Иначе говоря, элемент Smith вставляется непосредственно в ячейку 42, элемент Jones вступает в конфликт с элементом Smith и попадает в ячейку 43, а элемент Brown вступает в конфликт с элементом Jones и попадает в ячейку 44.

Удалим элемент Jones, используя предложенный алгоритм удаления. В результате возникнет следующая ситуация:

Элемент 41: <пусто>

Элемент 42: Smith

Элемент 43: <пусто>

Элемент 44: Brown

Элемент 45: <пусто>

Теперь возникает проблема: попытайтесь найти элемент Brown. Ему соответствует индекс 43. Однако при просмотре ячейки 43 она оказывается пустой и, в соответствии с применяемым алгоритмом поиска, это означает, что элемент Brown в хеш-таблице отсутствует. Разумеется, это неверно.

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

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

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

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

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

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

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

Класс хеш-таблиц с линейным зондированием

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

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

type

TtdHashFunc = function ( const aKey : string;

aTableSize : integer): integer;

Если вы еще раз взглянете на листинги 7.1 и 7.2, то убедитесь, что в обоих случаях функции имеют этот тип.

Листинг 7.3. Хеш-таблица линейного зондирования TtdHashTableLinear

type

TtdHashTableLinear = class

{хеш-таблица, в которой для разрешения конфликтов используется линейное зондирование}

private

FCount : integer;

FDispose: TtdDisposeProc;

FHashFunc : TtdHashFunc;

FName : TtdNameString;

FTable : TtdRecordList;

protected

procedure htlAlterTableSize(aNewTableSize : integer);

procedure htlError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure htlGrowTable;

function htlIndexOf( const aKey : string; var aSlot : pointer): integer;

public

constructor Create(aTableSize : integer;

aHashFunc : TtdHashFunc;

aDispose : TtdDisposeProc);

destructor Destroy; override;

procedure Delete(const aKey : string);

procedure Empty;

function Find(const aKey : string; var aItem : pointer): boolean;

procedure Insert(const aKey : string; aItem : pointer);

property Count : integer read FCount;

property Name : TtdNameString read FName write FName;

end;

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

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

type

PHashSlot = ^THashSlot;

THashSlot = packed record

{$IFDEF Delphi1}

hsKey : PString;

{$ELSE}

hsKey : string;

{$ENDIF}

hsItem : pointer;

hsInUse: boolean;

end;

Ячейка представляет собой запись с тремя полями: ключом, собственно элементом и состоянием ячейки (независимо от того, используется оно или нет). В Delphi1 ключ – это указатель строки, в то время как в последующих версиях он является длинной строкой (которая, естественно, представляет собой замаскированный указатель).

Конструктор Create выделяет экземпляр списка записей, а деструктор Destroy освобождает его.

Листинг 7.4. Конструктор и деструктор класса TtdHashTableLinear

constructor TtdHashTableLinear.Create( aTableSize : integer;

aHashFunc : TtdHashFunc;

aDispose : TtdDisposeProc );

begin

inherited Create;

FDispose := aDispose;

if not Assigned(aHashFunc) then

htlError(tdeHashTblNoHashFunc, 'Create');

FHashFunc := aHashFunc;

FTable := TtdRecordList.Create(sizeof(THashSlot));

FTable.Name := ClassName + 1 : hash table1;

FTable.Count := TDGetClosestPrime(aTableSize);

end;

destructor TtdHashTableLinear.Destroy;

begin

if (FTable <> nil) then begin

Clear;

FTable.Destroy;

end;

inherited Destroy;

end;

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

Рассмотрим вставку нового элемента. Метод Insert принимает ключ элемента и сам элемент и добавляет их в хеш-таблицу.

Листинг 7.5. Вставка элемента в хеш-таблицу с линейным зондированием

procedure TtdHashTableLinear.Insert(const aKey : string; aItem : pointer);

var

Slot : pointer;

begin

if (htlIndexOf (aKey, Slot) <> -1) then

htlError(tdeHashTblKeyExists, 'Insert');

if (Slot = nil) then

htlError(tdeHashTbllsFull, 'Insert');

with PHashSlot (Slot)^ do

begin

{$IFDEF Delphi1}

hsKey := NewStr(aKey);

{$ELSE}

hsKey := aKey;

{$ENDIF}

hsItem := aItem;

hslnuse := true;

end;

inc(FCount);

{увеличить таблицу, если она заполнена более чем на 2/3}

if ((FCount * 3) > (FTable.Count * 2)) then

htlGrowTable;

end;

В данном случае защищенные вспомогательные методы выполняют несколько задач. Первый из них – htlIndexOf. Этот метод предпринимает попытку найти ключ в хеш-таблице и в случае успеха возвращает его индекс и указатель на ячейку, которая содержит элемент (метод Insert воспринимает это как ошибку). Если ключ не был найден, метод возвращает значение -1, на этот раз с указателем на ячейку, в которую можно поместить элемент, что, собственно, и выполняется на следующем шаге. (Существует также третья возможность: метод htlIndexOf возвращает значение -1 для индекса и ничего для ячейки;

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

Метод Delete удаляет элемент и его ключ из хеш-таблицы. Как мы уже видели, метод должен разрывать любые цепочки линейного зондирования.

Листинг 7.6. Удаление элемента из хеш-таблицы с линейным зондированием

procedure TtdHashTableLinear.Delete(const aKey : string);

var

Inx : integer;

ItemSlot : pointer;

Slot : PHashSlot;

Key : string;

Item : pointer;

begin

{поиск ключа}

Inx := htlIndexOf(aKey, ItemSlot);

if (Inx = -1) then

htlError(tdeHashTblKeyNotFound, 'Delete');

{удалить элемент и его ключ из данной ячейки}

with PHashSlot (ItemSlot)^ do

begin

if Assigned(FDispose) then

FDispose(hsItem);

{$IFDEF Delphi1}

DisposeStr(hsKey);

{$ELSE}

hsKey := '';

{$ENDIF}

hsInUse := false;

end;

dec(FCount);

{повторно вставить все последующие элементы, предшествующие пустой ячейке}

inc(Inx);

if (Inx = FTable.Count) then

Inx := 0;

Slot := PHashSlot(FTable[Inx]);

while Slot^.hsInUse do

begin

{сохранить элемент и ключ; удалить ключ из ячейки}

Item := Slot^.hsItem;

{$IFDEF Delphi1}

Key := Slot^.hsKey^;

DisposeStr(Slot^.hsKey);

{$ELSE}

Key := Slot^.hsKey;

Slot^.hsKey := ''

{$ENDIF}

{пометить ячейку как пустую}

Slot^.hsInUse := false;

dec(FCount);

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

Insert(Key, Item);

{перейти к следующей ячейке}

inc(Inx);

if (Inx = FTable.Count) then

Inx := 0;

Slot := PHashSlot(FTable[Inx]);

end;

end;

Как и в предыдущем листинге, мы вызываем метод htlIndexOf, хотя на этот раз ошибка генерируется, если ключ не был найден. В случае обнаружения ключа метод возвращает указатель на ячейку, что позволяет избавиться от элемента (если это необходимо) и ключа. Состояние ячейки определяется как «не используется».

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

Метод Clear очень похож на метод Delete. Он используется для удаления всех элементов из хеш-таблицы.

Листинг 7.7. Опустошение хеш-таблицы с линейным зондированием

procedure TtdHashTableLinear.Clear;

var

Inx : integer;

begin

for Inx := 0 to pred(FTable.Count) do

begin

with PHashSlot (FTable [Inx])^ do

begin

if hsInUse then begin

if Assigned(FDispose) then

FDispose(hsItem);

{$IFDEF Delphi1}

DisposeStr(hsKey);

{$ELSE}

hsKey := '';

{$ENDIF}

end;

hsInUse := false;

end;

end;

FCount := 0;

end;

Поскольку мы избавляемся от всех элементов в хеш-таблице, состояние всех ячеек можно установить (как только мы избавились от ключей и элементов в тех ячейках, которые используются) как «не используется».

Поиск элемента по его ключу выполняется методом Find уверен, что после ознакомления с методами Insert и Delete читатели догадываются, что это – всего лишь вызовы пресловутого метода htlIndexOf.

Листинг 7.8. Поиск элемента в хеш-таблице по ключу

function TtdHashTableLinear.Find(const aKey : string; var aItem : pointer): boolean;

var

Slot : pointer;

begin

if (htlIndexOf (aKey, Slot)o-1) then begin

Result := true;

aItem := PHashSlot(Slot)^.hsItem;

end

else begin

Result := false;

aItem := nil;

end;

end;

Как видите, все достаточно просто.

Методы, которые выполняют увеличение хеш-таблицы, используют еще один, метод – htlAlterTableSize. Код обоих методов выглядит следующим образом.

Листинг 7.9. Изменение размера хеш-таблицы с линейным зондированием

procedure TtdHashTableLinear.htlAlterTableSize(aNewTableSize : integer);

var

Inx : integer;

OldTable : TtdRecordList;

begin

{сохранить старую таблицу}

OldTable := FTable;

{распределить память под новую таблицу}

FTable := TtdRecordList.Create(sizeof(THashSlot));

try

FTable.Count := aNewTableSize;

{считывать старую таблицу и перенести ключи и элементы}

FCount := 0;

for Inx := 0 to pred(OldTable.Count) do

with PHashSlot (OldTable [ Inx])^ do

if (hsState = hssInUse) then begin

{$IFDEF Delphi1}

Insert(hsKey^, hsItem);

DisposeStr(hsKey);

{$ELSE}

Insert(hsKey, hsItem);

hsKey := '';

{$ENDIF}

end;

except

{при возникновении исключения попытаться очистить хеш-таблицу и оставить ее в непротиворечивом состоянии}

FTable.Free;

FTable :=0ldTable;

raise;

end;

{и, наконец, освободить старую таблицу}

OldTable.Free;

end;

procedure TtdHashTableLinear.htlGrowTable;

begin

{увеличить размер таблицы приблизительно в два раза по сравнению с предыдущим}

htlAlterTableSize(GetClosestPrime(suce(FTable.Count * 2)));

end;

Метод hltAlterTableSize содержит код выполнения этих операций. Он работает, сохраняя текущую хеш-таблицу (т.е. экземпляр списка записей), распределяя память под новую таблицу и, затем, просматривая все элементы в старой таблице (которые находятся в ячейках, помеченных как «используемые») и вставляя их в новую таблицу. В заключение, метод освобождает старую таблицу. Обратите внимание, что блок Try..except предпринимает попытку сохранить непротиворечивое состояние хеш-таблицы в случае возникновения исключения. Естественно, при этом предполагается, что в момент вызова метода хеш-таблица находилась в именно таком состоянии.

Излишне говорить, что расширение хеш-таблицы – довольно-таки трудоемкая операция (которая требует очень большого дополнительного объема свободной памяти – вдвое больше того, который уже был выделен). Всегда желательно приблизительно оценить общее количество строк, которые нужно вставить В хеш-таблицу, и добавить, скажем, еще половину этого количества строк. Результирующее значение можно использовать в качестве расчетного размера хеш-таблицы при ее создании. Такая оценка обеспечит нам определенную свободу действий при использовании хеш-таблицы.

Теперь пора разобраться с последним фрагментом головоломки: рассмотреть "закулисный" метод htlIndexOf – примитив, используемый методами Insert, Delete и Find.

Листинг 7.10. Примитив поиска ключа в хеш-таблице

function TtdHashTableLinear.htlIndexOf(const aKey : string; var aSlot : pointer): integer;

var

Inx : integer;

CurSlot : PHashSlot;

FirstInx : integer;

begin

{вычислить хеш-значение строки, запомнить его, чтобы можно было установить, когда будет (если вообще будет) выполнен просмотр всех записей таблицы}

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

FirstInx := Inx;

{выполнить без каких-либо ограничений – при необходимости, выход из цикла можно будет осуществить всегда}

while true do

begin {для текущей ячейки}

CurSlot := PHashSlot(FTable[Inx]);

with CurSlot^ do

begin

if not hsInUse then begin

{ ячейка "пуста "; необходимо прекратить линейное зондирование и вернуть эту ячейку}

aSlot := CurSlot;

Result := -1;

Exit;

end

else begin

{ ячейка "используется"; необходимо проверить, совпадает ли она с искомым ключом. Если да, то необходимо осуществить выход, возвращая индекс и ячейку}

{$IFDEF Delphi1}

if (hsKey^ = aKey) then begin

{$ELSE}

if (hsKey = aKey) then begin

{$ENDIF}

aSlot := CurSlot;

Result := Inx;

Exit;

end;

end;

end;

{на этот раз ключ или пустая ячейка не были найдены, поэтому необходимо увеличить значение индекса (при необходимости выполнив циклический возврат) и осуществить выход в случае возврата к начальной ячейке}

inc(Inx);

if (Inx = FTable.Count) then

Inx := 0;

if (Inx = First Inx) then begin

aSlot :=nil;

{это сигнализирует о том, что таблица заполнена}

Result := -1;

Exit;

end;

end;

{бесконечный цикл}

end;

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

Метод определяет указатель на начальную ячейку. Мы просматриваем ячейку и выполняем различные операции, зависящие от состояния ячейки. Первый случай – когда ячейка пуста. Достижение этой точки означает, что ключ не был найден, поэтому метод возвращает указатель именно на эту ячейку. Естественно, в этом случае возвращаемое значение функции равно -1, что означает "ключ не найден".

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

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

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

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

Другие схемы открытой адресации

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

Квадратичное зондирование

Первая из таких схем – квадратичное зондирование (quadratic probing). При использовании этого алгоритма контроль и предотвращение создания кластеров осуществляется путем проверки не следующей по порядку ячейки, а ячеек, которые расположены все дальше от исходной. Если первое зондирование оказывается безрезультатным, мы проверяем следующую ячейку. В случае неудачи этой попытки мы проверяем ячейку, которая расположена через четыре ячейки. Если и эта попытка неудачна, мы проверяем ячейку, расположенную через девять ячеек – и т.д., причем последующие зондирования выполняются для ячеек, расположенных через 16, 25, 36 и так далее ячеек. Этот алгоритм позволяет предотвратить образование кластеров, которые могут появляться в результате применения линейного зондирования, однако он может приводить и к ряду нежелательных проблем. Во-первых, если для многих ключей хеширование генерирует один и тот же индекс, все их последовательности зондирования должны будут выполняться вдоль одного и того же пути. В результате они образуют кластер, но такой, который кажется распределенным по хеш-таблице. Однако вторая проблема значительно серьезнее: квадратичное зондирование не гарантирует посещение всех ячеек. Максимум в чем можно быть уверенным, если размер таблицы равен простому числу, это в том, что квадратичное зондирование обеспечит посещение, по меньшей мере, половины ячеек хеш-таблицы. Таким образом, образом, можно говорить о выполнении задачи-минимум, но не задачи-максимум.

В этом легко убедиться. Начнем квадратичное зондирование с 0-й ячейки хеш-таблицы, содержащей 11 ячеек, и посмотрим, какие ячейки будут посещены при этом. Последовательность посещений выглядит следующим образом: 0, 1, 5, 3, 8, после чего зондирование снова начинается с ячейки 0. Мы никогда не посещаем ячейки 2, 4, 7, 9. По-моему, одной этой проблемы достаточно, чтобы в любом случае избегать применения квадратичного зондирования, хотя ее можно было бы избегнуть, не позволяя хеш-таблице заполняться более чем на половину.

Псевдослучайное зондирование

Следующая возможность – применение псевдослучайного зондирования (pseudorandom probing). Этот алгоритм требует использования генератора случайных чисел, который можно сбрасывать в определенный момент. Применительно к рассматриваемому алгоритму, из числа рассмотренных в 6 главе генераторов наиболее подошел бы минимальный стандартный генератор случайных чисел, поскольку его состояние однозначно определяется одним характеристическим значением – начальным числом. Алгоритм определяет следующую последовательность действий. Выполните хеширование ключа для получения хеш-значения, но не выполняйте деление по модулю на размер таблицы. Установите начальное значение генератора равным этому хеш-значению. Сгенерируйте первое случайное число с плавающей точкой (в диапазоне от 0 до 1) и умножьте его на размер таблицы для получения целочисленного значения в диапазоне от 0 до размера таблицы минус 1. Эта точка будет точкой первого зондирования. Если ячейка занята, сгенерируйте следующее случайное число, умножьте его на размер таблицы и снова выполните зондирование. Продолжайте выполнять упомянутые действия до тех пор, пока не найдете свободную ячейку. Поскольку при одном и том же заданном начальном значении генератор случайных чисел будет генерировать одни и те же случайные числа в одной и той же последовательности, для одного и того же хеш-значения всегда будет создаваться одна и та же последовательность зондирования.

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

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

Двойное хеширование

В заключение рассмотрим двойное хеширование (double hashing). На практике эта схема оказывается наиболее удачной из всех альтернативных схем с открытой адресацией. Итак, выполним хеширование ключа элемента в значение индекса. Назовем его h(_1_). Выполним зондирование этой ячейки. Если она занята, выполним хеширование ключа путем применения совершенно иного и независимого алгоритма хеширования для получения другого значения индекса. Назовем его h(_2_). Выполним зондирование ячейки h(_1_) + h(_2_). Если она занята, выполним зондирование ячейки h(_1_) + 2h(_2_), затем h(_1_) + 3h(_2_) и так далее (понятно, что все вычисления выполняются с делением по модулю на размер таблицы). Обоснование этого алгоритма следующее: если первая функция хеширования для двух ключей генерирует один и тот же индекс, очень маловероятно, что вторая функция хеширования сгенерирует для них то же самое значение. Таким образом, два ключа, которые первоначально хешируются в одну и ту же ячейку, затем не будут соответствовать одной и той же последовательности зондирования. В результате мы можем ликвидировать «неизбежную» кластеризацию, сопряженную с линейным зондированием. Если размер таблицы равен простому числу, последовательность зондирования обеспечит посещение всех ячеек, прежде чем начнется сначала, что позволит избежать проблем, связных с квадратичным и псевдослучайным зондированием. Единственная реальная проблема, возникающая при использовании двойного хеширования, – если не принимать во внимание необходимость вычисления дополнительного хеш-значения – состоит в том, что вторая функция хеширования по понятным причинам никогда не должна возвращать значение, равное 0. На практике эту проблему легко решить, выполняя деление по модулю на размер таблицы минус 1 (в результате мы получим значение в диапазоне от 0 до TableSize-2), а затем добавляя к результату единицу.

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