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

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

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