14.3 Линейное зондирование

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

Простейший метод открытой адресации называется линейным зондированием (linear probing): при наличии конфликта (когда хеширование выполняется в место таблицы, которое уже занято элементом с ключом, не совпадающим с ключом поиска) мы просто проверяем следующую позицию в таблице. Обычно подобную проверку (определяющую, содержит ли данная позиция таблицы элемент с ключом, равным ключу поиска) называют зондированием (рюЬе).

Линейное зондирование характеризуется выявлением одного из трех возможных исходов зондирования: если позиция таблицы содержит элемент, ключ которого совпадает с искомым, имеет место попадание при поиске; в противном случае (если позиция таблицы содержит элемент, ключ которого не совпадает с искомым) мы просто зондируем позицию таблицы со следующим по величине индексом, продолжая этот процесс (возвращаясь к началу таблицы при достижении ее конца) до тех пор, пока не будет найден искомый ключ или пустая позиция таблицы. Если содержащий искомый ключ элемент должен быть вставлен вслед за неудачным поиском, он помещается в пустую область таблицы, в которой поиск был завершен. Программа 14.4 - это реализация АТД таблицы символов, где используется этот метод. Процесс построения хеш-таблицы с использованием линейного зондирования для тестового набора ключей показан на рис. 14.7.

Программа 14.4 Линейное зондирование

Эта реализация таблицы символов хранит элементы в таблице, размер которой вдвое превышает максимально ожидаемое количество элементов и инициализируется значением nullltem. Таблица содержит сами элементы; если элементы велики, тип элемента можно изменить, чтобы он содержал ссылки на элементы.

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

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

private: Item *st; int N, M; Item nullltem;

public: ST(int maxN) {

N = 0; M = 2*maxN; st = new Item[M] ; for (int i = 0; i < M; st[i] = nullltem;

i++)

% M;

int count 0 const { return N; void insert(Item item)

{ int i = hash(item.key 0 , M) ; while (!st[i] .null 0 ) i = (i+1) st[i] = item; N++;

Item search (Key v)

{ int i = hash(v, M) ; while (rst[i] .nullO ) if (v = st[i].key()) return st[i] ; else i = (i+1) % M; re turn nul11tem;

Как и в случае раздельного связывания, производительность методов с открытой адресацией зависит от коэффициента а = N/M, но при этом он интерпретируется иначе. В случае раздельного связывания а - среднее количество элементов в одном списке, которое в общем случае больще 1. В случае открытой адресации а - доля занятых позиций таблицы в процентах; она должна быть меньше 1. Иногда а называют коэффициентом загрузки хеш-таблицы.

В случае разреженной (слабо заполненной) таблицы (значение а мало) можно рассчитывать, что в большинстве случаев поиска пустая позиция будет найдена в результате всего нескольких зондирований. В случае почти полной таблицы (значение а близко к 1) для выполнения поиска могло бы потребоваться очень большое количество зондирований, а когда таблица полностью заполнена, поиск может даже привести к бесконечному циклу. Как правило, при использовании линейного зондирования во избежание больших затрат времени при поиске стремятся к тому, чтобы не допустить заполнения таблицы. То есть, вместо того, чтобы использовать дополнительный объем памяти для связей, задействуется дополнительное пространство в хеш-таблице, что позволяет сократить последовательности зондирования. При использовании линейного зондирования размер таблицы больше, чем при раздельном связывании, поэтому необходимо, чтобы Л/ > 7V, но общий используемый объем памяти может быть меньше, поскольку никаких связей не используется.

РИСУНОК 14.7 ХЕШИРОВАНИЕ МЕТОДОМ ЛИНЕЙНОГО ЗОНДИРОВАНИЯ

На этой диаграмме показан процесс вставки ключей Л S Е RCHINGXMPe первоначально пустую хеш-таблицу с открытой адресацией, размер которой равен 13, при использовании показанных вверху хеш-значений и разрешении конфликтов за счет применения линейного зондирования. Вначале А помещается в позицию 7, затем S помещается в позицию 3, Е - в позицию 9, далее, после конфликта в позиции 9, R помещается в позицию 10 и т.д. При достижении правого конца таблицы зондирование продолжается с левого конца: например, последний вставленный ключ Р помещается в позицию 8, затем после возникновения конфликта в позициях 8 - 12 и 0-5 выполняется зондирование позиции 5. Все позиции таблицы, которые не зондировались, затенены.

Вопросы сравнения используемого объема памяти подробно рассматриваются в разделе 14.5. Пока же давайте проанализируем время выполнения линейного зондирования как функцию а.

Средние затраты на выполнение линейного зондирования зависят от способа объединения элементов в непрерывные группы занятых ячеек таблицы, называемые кластерами (clusters), при их вставке. Давайте рассмотрим следующие два крайних случая заполненной наполовину {М - IN) таблицы линейного зондирования: в лучщем случае позиции таблицы с четными индексами могли бы быть пустыми, а с нечетными - занятыми. В худшем случае первая половина позиций таблицы могла бы быть пустой, а вторая - заполненной. Средняя длина кластеров в обоих случаях равна N/{2N) = 1/2, но среднее количество зондирований для безуспешного поиска равно 1 (все поиски требуют, по меньшей мере, одного зондирования) плюс

(0+1+0+1 + ...)/{2N)= 1/2 в лучшем случае и 1 плюс

{N + {N- 1) + {N-2) + ...) / (2Л0 - ЛУ4 в худшем случае.

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

{t+{t-\) + ... + 2 + \)/ M=t{t + I) / {2М)

определяет вклад этого кластера в общую сумму. Сумма длин кластеров равна N, поэтому суммируя эти затраты для всех ячеек в таблице, находим, что общие средние затраты на обнаружение промаха при поиске равны 1 + N/{2M) плюс сумма квадратов длин кластеров, деленная на 2М. Имея заданную таблицу, можно быстро вычислить средние затраты на безуспешный поиск в этой таблице (см. упражнение 14.28), но кластеры образуются в результате сложного динамического процесса (алгоритма линейного зондирования), который трудно охарактеризовать аналитически.

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

1-ь

(1-а)

для попаданий и промахов, соответственно.

Несмотря на сравнительно простую форму полученных результатов, точный анализ линейного зондирования - сложная задача. Вывод, полученный Кнутом (КпЩЬ) в 1962 г., явился значительной вехой в анализе алгоритмов {см. раздел ссылок).