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

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

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

Как видите, после образования кластеров вероятность их увеличения все время возрастает.

Кластеры влияют на среднее количество зондирований, требуемых как для обнаружения существующего элемента (попадания), так и для выяснения того, что элемент в хеш-таблице отсутствует (промаха). Кнут показал, что среднее количество зондирований для обнаружения попадания приблизительно равно 1/2(1 + 1/(1 -x)), где x - количество элементов в хеш-таблице, деленное на размер хеш-таблицы (эту величину называют коэффициентом загрузки (load factor)), а среднее количество зондирований для обнаружения промаха приблизительно равно 1/2(1 + 1/(1 -x)(^2^)) [13]. Несмотря на простоту этих выражений, математические выкладки, приводящие к их получению, весьма сложны.

Используя приведенные формулы, можно показать, что если хеш-таблица заполнена примерно наполовину, для обнаружения попадания требуется в среднем приблизительно 1.5 зондирования, а для обнаружения промаха - 2.5 зондирования. Если же таблица заполнена на 90%, для обнаружения попадания требуется в среднем 5.5 зондирований, а для обнаружения промаха - 55.5 зондирований. Как видите, при использовании хеш-таблицы, в которой в качестве схемы разрешения конфликтов применяется линейное зондирование, таблица должна быть заполнена не более чем на две трети, чтобы эффективность оставалась приемлемой. Если это удастся, мы снизим влияние, которое кластеризация оказывает на эффективность хеш-таблицы.

------

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

------