Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Второй момент - проблема кластеризации. При использовании линейного зондирования выясняется, что элементы имеют тенденцию к образованию непрерывных групп, или кластеров, занятых ячеек. Добавление новых элементов приводит к увеличению размеров групп, в результате чего конфликт вставленных элементов с элементом в кластере становится все более вероятным. И, конечно, с увеличением вероятности конфликта размеры кластеров также увеличиваются.
Это можно подтвердить математически, используя идеальную функцию хеширования, которая выполняет рандомизацию входных данных. Вставим элемент в пустую хеш-таблицу. Предположим, что в результате генерируется индекс x. Вставим еще один элемент. Поскольку
После вставки второго элемента возможны три ситуации: два элемента образуют кластер, два элемента разделены одной пустой ячейкой или два элемента разделены более чем одной пустой ячейкой. Вероятности этих трех ситуаций соответственно равны 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 зондирований. Как видите, при использовании хеш-таблицы, в которой в качестве схемы разрешения конфликтов применяется линейное зондирование, таблица должна быть заполнена не более чем на две трети, чтобы эффективность оставалась приемлемой. Если это удастся, мы снизим влияние, которое кластеризация оказывает на эффективность хеш-таблицы.
– -----
Описанная особенность очень важна для хеш-таблиц, в которых в качестве метода разрешения конфликтов применяется линейное зондирование. Нельзя допускать, чтобы хеш-таблица заполнялась в значительной степени. В противном случае длина последовательности зондирований становится
– -----
Удаление элементов из хеш-таблицы с линейным зондированием
Прежде чем приступить к рассмотрению конкретного кода, рассмотрим удаление элементов из хеш-таблицы. Эта задача кажется достаточно простой: необходимо выполнить хеширование ключа элемента, который нужно удалить, найти его (используя необходимое количество зондирований), а затем пометить ячейку как пустую. К сожалению, применение этого упрощенного метода приводит к возникновению ряда проблем.
Предположим, что функция хеширования для ключей Smith, Jones и Brown создает следующие хеш-значения: 42, 42 и 43. Их добавление в хеш-таблицу в указанном порядке приводит к возникновению ситуации, показанной ниже:
Элемент 41: <пусто>
Элемент 42: Smith
Элемент 43: Jones
Элемент 44: Brown
Элемент 45: <пусто>
Иначе говоря, элемент Smith вставляется непосредственно в ячейку 42, элемент Jones вступает в конфликт с элементом Smith и попадает в ячейку 43, а элемент Brown вступает в конфликт с элементом Jones и попадает в ячейку 44.
Удалим элемент Jones, используя предложенный алгоритм удаления. В результате возникнет следующая ситуация:
Элемент 41: <пусто>
Элемент 42: Smith
Элемент 43: <пусто>
Элемент 44: Brown
Элемент 45: <пусто>
Теперь возникает проблема: попытайтесь найти элемент Brown. Ему соответствует индекс 43. Однако при просмотре ячейки 43 она оказывается пустой и, в соответствии с применяемым алгоритмом поиска, это означает, что элемент Brown в хеш-таблице отсутствует. Разумеется, это неверно.
Следовательно, при удалении элемента из хеш-таблицы, в которой применяется линейное зондирование, ячейку нельзя помечать как пустую: она может быть частью последовательности линейного зондирования. Вместо этого ячейку необходимо пометить как "удаленную" и слегка изменить алгоритм поиска, чтобы поиск продолжался при обнаружении удаленной ячейки.
Необходимо также слегка изменить и алгоритм вставки. В настоящее время, чтобы вставить элемент, мы осуществляем его поиск (т.е. выполняем хеширование ключа элемента и зондируем результирующий индекс и, возможно, последующие ячейки) до тех пор, пока не найдем элемент или не наткнемся на первую пустую ячейку. Обнаружив пустую ячейку, мы вставляем в нее новый элемент. (при обнаружении элемента можно либо сгенерировать сообщение об ошибке, либо просто заменить существующий элемент.)
Теперь же, ради эффективности, необходимо пометить первую удаленную ячейку, встретившуюся в ходе выполнения последовательности зондирования. Наличие пустой ячейки свидетельствует об отсутствии элемента. Однако мы не вставляем элемент в нее. Вместо этого, мы возвращаемся назад и вставляем элемент в первую пропущенную удаленную ячейку.
Возможность удаления элементов имеет одно важное следствие: слишком частое выполнение этой операции приведет к тому, что хеш-таблица будет заполнена ячейками, которые помечены как удаленные. Это, в свою очередь, увеличит среднее количество зондирований, требуемое для обнаружения попадания или промаха, тем самым снижая эффективность хеш-таблицы. Если количество удаленных ячеек становится слишком большим, весьма желательно выделить новую хеш-таблицу и скопировать все элементы в нее.