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

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

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

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

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

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