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

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

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

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

type

TtdSkipList = class private

FCompare : TtdCompareFunc;

FCount : integer;

FCursor : PskNode;

FDispose : TtdDisposeProc;

FHead : PskNode;

FMaxLevel : integer;

FName : TtdNameString;

FPRNG : TtdMinStandardPRNG;

FTail : PskNode;

protected

class function slAllocNode(aLevel : integer): PskNode;

procedure slError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure slFreeNode(aNode : PskNode);

class procedure slGetNodeManagers;

function slSearchPrim(aItem : pointer;

var aBeforeNodes : TskNodeArray): boolean;

public

constructor Create( aCompare : TtdCompareFunc;

aDispose : TtdDisposeProc);

destructor Destroy; override;

procedure Add(aItem : pointer);

procedure Clear;

procedure Deleter-function Examine : pointer;

function IsAfterLast : boolean;

function IsBeforeFirst : boolean;

function IsEmpty : boolean;

procedure MoveAfterLast;

procedure MoveBeforeFirst;

procedure MoveNext;

procedure MovePrior;

procedure Remove(aItem : pointer);

function Search(aItem : pointer): boolean;

property Count : integer read FCount;

property MaxLevel : integer read FMaxLevel;

property Name : TtdNameString read FName write FName;

end;

Назначение большинства методов и свойств станет понятным, если вы вернетесь к описанию методов класса связных списков, которое приводится в главе 3.

Как и для классов связных списков, используется диспетчер узлов, который позволяет эффективно выделять и освобождать узлы. Тем не менее, для списков с пропусками имеется небольшое, однако важное отличие: узлы в списке с пропусками имеют разные размеры. Фактически в списке может быть до 12 видов узлов. Следовательно, для работы с узлами потребуется 12 диспетчеров. Процедура класса slGetNodeManagers выполняет инициализацию 12 диспетчеров узлов. Она вызывается в конструкторе Create класса списка с пропусками. Все объекты списков будут пользоваться одними и теми же диспетчерами. В заключительной части модуля все диспетчеры узлов удаляются.

Листинг 6.19. Конструктор и деструктор класса списка с пропусками

constructor TtdSkipList.Create(aCompare : TtdCompareFunc;

aDispose : TtdDisposeProc);

var

i : integer;

begin

inherited Create;

{функция сравнения не может быть nil}

if not Assigned(aCompare) then

slError(tdeSkpLstNoCompare, 'Create');

{создать диспетчеры узлов}

slGetNodeManagers;

{выделить начальный узел}

FHead := slAllocNode (pred( tdcMaxSkipLevels));

FHead^.sknData := nil;

{выделить конечный узел}

FTail := slAllocNode (0);

FTail^.sknData := nil;

{задать прямые и обратные указатели для начального и конечного узлов}

for i := 0 to pred(tdcMaxSkipLevels) do

FHead^.sknNext[i] := FTail;

FHead^.sknPrev := nil;

FTail^.sknNext[0] :=nil;

FTail^.sknPrev := FHead;

{установить курсор на начальный узел}

FCursor := FHead;

{сохранить функцию сравнения и процедуру dispose}

FCompare := aCompare;

FDispose :=aDispose;

{создать генератор случайных чисел}

FPRNG := TtdMinStandardPRNG.Create(0);

end;

destructor TtdSkipList.Destroy;

begin

Clear;

slFreeNode(FHead);

slFreeNode(FTail);

FPRNG.Free;

inherited Destroy;

end;

Конструктор использует функцию сравнения, что позволяет корректно выбирать позицию вставляемых узлов (конечно, функция сравнения не может быть nil). Кроме того, в качестве входного параметра присутствует процедура dispose. Если она содержит nil, список с пропусками не является владельцем хранящихся в нем данных, поэтому при удалении списка данные удаляться не будут. В противном случае список является владельцем данных, и при его удалении данные также будут удаляться. Конструктор Create создает начальный и конечный узлы и устанавливает их указатели. И, наконец, создается генератор случайных чисел. Он впоследствии будет использоваться в методе Add.

Деструктор Destroy очищает содержимое списка с помощью метода Clear, освобождает начальный и конечный узлы и уничтожает генератор случайных чисел.

Метод Clear предназначен для очистки содержимого всех узлов, находящихся между начальным и конечным узлами, путем прохождения списка по указателям нижнего уровня и уничтожения узлов.

Листинг 6.20. Очистка содержимого списка с пропусками

procedure TtdSkipList.Clear;

var

i : integer;

Walker, Temp : PskNode;

begin

{пройти по узлам уровня 0, освобождая все узлы}

Walker := FHead^.sknNext[0];

while (Walker <> FTail) do

begin

Temp Walker;

Walker := Walker^.sknNext[0];

slFreeNode(Temp);

end;

{восстановить начальный и конечный узлы}

for i := 0 to pred(tdcMaxSkipLevels) do

FHead^.sknNext[i] := FTail;

FTail^.sknPrev := FHead;

FCount := 0;

end;

Методы выделения и уничтожения узлов достаточно просты. Они пользуются диспетчерами узлов класса и определяют требуемый диспетчер на основе значения уровня. Для метода выделения узла уровень передается в качестве входного параметра, для метода уничтожения оно определяется исходя из значения, полученного из освобождаемого узла.

Листинг 6.21. Выделение и уничтожение узлов в списке с пропусками

class function TtdSkipList.slAllocNode(aLevel : integer): PskNode;

begin

Result := SLNodeManager[aLevel].AllocNode;

Result^.sknLevel := aLevel;

end;

procedure TtdSkipList.siFreeNode(aNode : PskNode);

begin

if (aNode <> nil) then begin

if Assigned(FDispose) then

FDispose(aNode^.sknData);

SLNodeManager[aNode^.sknLevel].FreeNode(aNode);

end;

end;

class procedure TtdSkipList.slGetNodeManagers;

var

i : integer;

begin

{если диспетчеры узлов еще не созданы, создать их}

if (SLNodeManager[0] =nil) then

for i := 0 to pred(tdcMaxSkipLevels) do SLNodeManager[i] := TtdNodeManager.Create(NodeSize[i]);

end;

Обратите внимание, что метод уничтожения освобождает узлы только в том случае, когда список с пропусками создан в качестве владельца данных.

Остальные методы класса списка с пропусками еще проще – все они содержат всего несколько строк кода.

Листинг 6.22. Остальные методы класса списка с пропусками

procedure TtdSkipList.Delete

begin

{начальный и конечный узлы удалять нельзя}

if (FCursor = FHead) or (FCursor = FTail) then

slError(tdeListCannotDelete, 'Delete');

{удалить узел в позиции курсора}

Remove(FCursor^.sknData);

end;

function TtdSkipList.Examine : pointer;

begin

Result := FCursor^.sknData;

end;

function TtdSkipList.IsAfterLast : boolean;

begin

Result := FCursor = FTail;

end;

function TtdSkipList.IsBeforeFirst : boolean;

begin

Result := FCursor = FHead;

end;

function TtdSkipList.IsEmpty : boolean;

begin

Result := Count = 0;

end;

procedure TtdSkipList.MoveAf terLast;

begin

FCursor := FTail;

end;

procedure TtdSkipList.MoveBeforeFirst;

begin

FCursor := FHead;

end;

procedure TtdSkipList.MoveNext;

begin

if (FCursor <> FTail) then

FCursor := FCursor^.sknNext[0];

end;

procedure TtdSkipList.Move Prior;

begin

if (FCursor <> FHead) then

FCursor := FCursor^.sknPrev;

end;

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

Резюме

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

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

И, наконец, был рассмотрен список с пропусками – структура данных, используемая для хранения данных в отсортированном порядке. Было показано, каким образом случайные числа позволяют повысить характеристики быстродействия списков с пропусками.

Глава 7. Хеширование и хеш-таблицы

В главе 4 были рассмотрены алгоритмы поиска элемента в массиве (например, TList) или в связном списке. Наиболее быстрым из рассмотренных методов был бинарный поиск, для выполнения которого требовался отсортированный контейнер. Бинарный поиск представляет собой алгоритм класса O(log(n)). Так, чтобы установить наличие или отсутствие заданного элемента в списке из 1000 элементов, требуется выполнить приблизительно 10 сравнений (поскольку 2(^10^) = 1024). Возможен ли еще более эффективный подход?

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

Однако если бы элемент можно было связать с уникальным индексом, его можно было бы найти посредством однонаправленного действия: просто извлекая элемент, расположенный в позиции MyList[ItemIndex]. Это пример поиска с использованием индексирования по ключу, когда ключ элемента преобразуется в индекс, и элемент извлекается из массива с помощью этого индекса. Такой подход кардинально отличается от бинарного поиска, при котором, по существу, ключ элемента используется для перемещения по структуре с применением метода, в основе которого лежит сравнение.

Преобразование ключа элемента в значение индекса называется хешированием (hashing) и оно выполняется с помощью функции хеширования (hash function). Массив, используемый для хранения элементов, с которым используется значение индекса, называют хеш-таблицей (hash table).

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

Хеш-таблица – прекрасный пример достижения компромисса между быстродействием и занимаемым объемом памяти. Если бы ключи элементов были уникальными значениями типа word, нужно было бы всего лишь создать 65536 элементов, и при этом можно было бы гарантировать нахождение элемента с конкретным ключом в результате выполнения одной операции. Однако если нужно хранить, скажем, не более 100 элементов, подобный подход оказывается чрезмерно расточительным. Да, возможно, этот метод работает достаточно быстро, но 99.85% области памяти массива пребывает пустой. Впадая в другую крайность, можно было бы выделить только необходимый объем памяти, выделяя массив требуемого размера, храня элементы в отсортированном порядке и используя бинарный поиск. Согласен, этот метод работает медленнее, но зато отсутствует бесполезно расходуемая память. Хеширование и хеш-таблицы позволяют выбрать золотую середину между этими двумя диаметрально противоположными подходами. Хеш-таблицы будут занимать больше места, причем некоторые элементы окажутся пустыми, тем не менее, использование функции хеширования позволяет найти элемент в результате очень небольшого числа обращений – обычно одного при тщательном выполнении хеширования.

Время от времени, с хеш-таблицами придется выполнять следующие операции:

* вставлять элементы в хеш-таблицу;

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

* удалять элементы из хеш-таблицы.

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

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

–

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

–

Однако вначале давайте проведем исследование функций хеширования, которые делают возможным выполнение указанных операций.

Функции хеширования

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

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

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

Простейший случай – использование целочисленный ключей, когда элемент уникально идентифицируется целочисленным значением. Простейшей функцией хеширования, которую можно было бы использовать в этом случае, является операция деления по модулю. Если хеш-таблица содержит n элементов, хеш-значение ключа k вычисляется путем вычисления k по модулю n (если результат этой операции оказывается отрицательным, нужно просто добавить к нему n). Например, если n равно 16, то ключу 6 будет соответствовать индекс 6, ключу 44 – индекс 12 и т.д. В случае равномерного распределения значений ключей эта функция вполне подходила бы для работы, но в общем случае множество значений ключей не столь равномерно распределенное, и поэтому в качестве размера хеш-таблицы необходимо использовать простое число.

На практике можно сформулировать следующее правило создания хеш-таблиц: количество записей в хеш-таблице всегда должно быть равно простому числу. Для ознакомления с полным математическим обоснованием этого утверждения обратитесь к [13].

Для строковых ключей следует использовать метод, заключающийся в преобразовании строки в целочисленное значение с последующим применением операции деления по модулю для получения значения индекса, лежащего в диапазоне от 0 до n – 1.

Так как же преобразовать строку в целочисленное значение? Один из возможных способов предполагает использование длины строкового ключа. Преимущество применения этого метода состоит в простоте и высокой скорости выполнения. Однако его недостатком является генерирование множества конфликтов. На практике таких конфликтов возникает слишком много. Например, предположим, что нужно создать хеш-таблицу, которая должна содержать названия альбомов коллекции компакт-дисков. В частности, в принадлежащей автору коллекции компакт-дисков, насчитывающей несколько сот наименований, названия подавляющего большинства альбомов содержат от 2 до 20 символов. Использование длины названия альбома привело бы к возникновению множества конфликтов: альбом Bilingual в исполнении Pet Shop Boys конфликтовал бы с Technique в исполнении New Order и с Mind Bomb в исполнении The The. Таким образом, подобная функция хеширования совершенно неприемлема.

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

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

Простая функция хеширования для строк

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

Листинг 7.1. Простая функция хеширования строковых ключей

function TDSimpleHash( const aKey : string;

aTableSize : integer): integer;

var

i : integer;

Hash : longint;

begin

Hash := 0;

for i := 1 to length (aKey) do

Hash := ((Hash * 17) + ord(aKey[i])) mod aTableSize;

Result := Hash;

if (Result < 0) then

inc(Result, aTableSize);

end;

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

Эта подпрограмма достаточно удачна. В ней для каждого символа выполняется всего несколько арифметических операций – к сожалению, в их числе и операция деления – и поэтому она достаточно эффективна. В реальных ситуациях строковые ключи оказываются в значительной степени подобными друг другу (вспомните, например, названия классических музыкальных произведений), а подпрограмма из похожих входных значений создает хеш-значения, которые выглядят случайными. Заключительный оператор if требуется потому, что промежуточное значение переменной Hash может быть отрицательным (такова неприятная "особенность" операции деления по модулю Delphi), а программа, вызывающая эту подпрограмму, будет ожидать результат, значение которого лежит в диапазоне от 0 до TableSize-1.

Функции хеширования PJW

В разделе, посвященном хеш-таблицам, книги «Compilers: Principles, Techniques, and Tools» («Компиляторы: принципы, технологии, инструменты»), Ахо (Aho) и других, которая была издана Addison-Wesley [2], описана функция хеширования, созданная П. Дж. Вайнбергером (P. J. Weinberger). Эту подпрограмму называют также хешем Executable and Linking Format (формат исполняемых и компонуемых модулей), или ELF-хешем. Используемый в ней алгоритм аналогичен тому, что применяется в подпрограмме листинга 7.1. Единственное исключение состоит в том, что в этом алгоритме реализован эффект рандомизации, когда операция XOR снова загружает старший полубайт действующей рабочей переменной хеша (полубайт, который должен исчезнуть в результате переполнения при выполнении следующей операции умножения), если он не равен нулю, в младшую часть переменной. Затем алгоритм устанавливает значение старшего полубайта равным нулю, в результате чего конечное хеш-значение всегда будет неотрицательным. (Исходный код функции можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshBse.pas.)

Листинг 7.2. Функция PJW хеширования строковых ключей

function TDPJWHash( const aKey : string;

aTableSize : integer): integer;

var

G : longint;

i : integer;

Hash : longint;

begin

Hash := 0;

for i := 1 to length (aKey) do

begin

Hash := (Hash shl 4) + ord(aKey[i]);

G := Hash and longint ($F0000000);

if (G <> 0) then

Hash := (Hash xor (G shr 24)) xor G;

end;

Result := Hash mod aTableSize;

end;

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

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

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

Но предположим, что у нас имеется известный список 100 строковых ключей. Существует ли какая-либо функция хеширования, которая будет генерировать уникальное хеш-значение для каждого из этих известных ключей, чтобы можно было разработать хеш-функцию, содержащую ровно 100 элементов? Функции хеширования такого типа называют совершенными. Безусловно, теоретически это возможно. Существует очень много таких функций (по существу, это равнозначно определению перестановок исходных ключей). Но как найти одну из таких функций? К сожалению, ответ на данный вопрос выходит за рамки этой книги. Даже Кнут (Knuth) [13] обходит эту тему. На практике совершенные функции хеширования представляют лишь теоретический интерес. Как только возникает потребность в другом ключе, совершенная функция хеширования разрушается и нам приходится разрабатывать следующую. Значительно удобнее считать, что никаких совершенных функций хеширования не существует, и иметь дело с неизбежными конфликтами, которые будут периодически возникать.

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

Если количество элементов, которые, скорее всего, должна содержать хеш-таблица, известно, можно выделить место для хеш-таблицы, содержащей это количество элементов и небольшое число свободных ячеек «на всякий случай». Было разработано несколько алгоритмов, которые позволяют хранить элементы в таблице, используя пустые ячейки таблицы для хранения элементов, которые конфликтуют с уже имеющимися. Этот класс алгоритмов называют схемами с открытой адресацией (open-addressing schemes). Простейшая схема с открытой адресацией – это линейное зондирование (linear probing).

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

Для начала вставим в пустую хеш-таблицу фамилию "Smith" (т.е. вставим элемент, ключом которого является "Smith"). Выполним хеширование ключа Smith с помощью функции хеширования и получим значение индекса, равное 42. Установим значение 42-го элемента хеш-таблицы равным Smith. Теперь записи хеш-таблицы вблизи этого элемента выглядят следующим образом:

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

Элемент 42: Smith

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

Это было достаточно просто. Теперь вставим фамилию "Jones". Необходимо выполнить те же действия, что и в предыдущем случае: следует вычислить хеш-значение ключа Jones, а затем вставить значение Jones по результирующему индексу. К сожалению, используемая функция хеширования имеет неизвестное происхождение и для фамилии Jones генерирует хеш-значение, которое также равно 42. Если теперь обратиться к хеш-таблице, выясняется, что имеет место конфликт: ячейка 42 уже занята фамилией Smith. Что же делать? Используя линейное зондирование, мы проверяем следующую ячейку, чтобы выяснить, пуста ли она. Если да, то мы устанавливаем значение 43-го элемента хеш-таблицы равным Jones. (Если бы 43-я ячейка оказалась занятой, пришлось бы проверить следующую ячейку и т.д., возвращаясь к началу хеш-таблицы по достижении ее конца. Со временем мы нашли бы пустую ячейку либо вернулись бы к исходному состоянию, выяснив, что таблица заполнена.) Действие по проверке ячейки в хеш-таблице называется зондированием (probing), отсюда и название самого алгоритма – линейное зондирование.

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

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

Элемент 42: Smith

Элемент 43: Jones

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

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

А как насчет поиска элемента, который отсутствует в таблице? Выполним поиск элемента "Brown". Реализуем хеширование, в результате чего будет получено значение индекса, равное 43. При обращении к 43-му элементу выясняется, что он соответствует элементу Jones. При переходе к следующему, 44-му, элементу выясняется, что он пуст. Теперь можно сделать вывод, что элемент Brown в хеш-таблице отсутствует.

Преимущества и недостатки линейного зондирования

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

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

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

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

После вставки второго элемента возможны три ситуации: два элемента образуют кластер, два элемента разделены одной пустой ячейкой или два элемента разделены более чем одной пустой ячейкой. Вероятности этих трех ситуаций соответственно равны 3/n, 2/n и (n – 5)/n.