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

Листинг 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.