Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
После вставки второго элемента возможны три ситуации: два элемента образуют кластер, два элемента разделены одной пустой ячейкой или два элемента разделены более чем одной пустой ячейкой. Вероятности этих трех ситуаций соответственно равны 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 в хеш-таблице отсутствует. Разумеется, это неверно.
Следовательно, при удалении элемента из хеш-таблицы, в которой применяется линейное зондирование, ячейку нельзя помечать как пустую: она может быть частью последовательности линейного зондирования. Вместо этого ячейку необходимо пометить как "удаленную" и слегка изменить алгоритм поиска, чтобы поиск продолжался при обнаружении удаленной ячейки.
Необходимо также слегка изменить и алгоритм вставки. В настоящее время, чтобы вставить элемент, мы осуществляем его поиск (т.е. выполняем хеширование ключа элемента и зондируем результирующий индекс и, возможно, последующие ячейки) до тех пор, пока не найдем элемент или не наткнемся на первую пустую ячейку. Обнаружив пустую ячейку, мы вставляем в нее новый элемент. (при обнаружении элемента можно либо сгенерировать сообщение об ошибке, либо просто заменить существующий элемент.)
Теперь же, ради эффективности, необходимо пометить первую удаленную ячейку, встретившуюся в ходе выполнения последовательности зондирования. Наличие пустой ячейки свидетельствует об отсутствии элемента. Однако мы не вставляем элемент в нее. Вместо этого, мы возвращаемся назад и вставляем элемент в первую пропущенную удаленную ячейку.
Возможность удаления элементов имеет одно важное следствие: слишком частое выполнение этой операции приведет к тому, что хеш-таблица будет заполнена ячейками, которые помечены как удаленные. Это, в свою очередь, увеличит среднее количество зондирований, требуемое для обнаружения попадания или промаха, тем самым снижая эффективность хеш-таблицы. Если количество удаленных ячеек становится слишком большим, весьма желательно выделить новую хеш-таблицу и скопировать все элементы в нее.
Итак, если принять, что удаление элементов приведет к снижению эффективности хеш-таблицы, нельзя ли воспользоваться каким-то другим алгоритмом? Ответ, как это ни удивительно, положителен. Таким алгоритмом может быть следующий. Удалим элемент в соответствии с упрощенной схемой удаления;
иначе говоря, пометим ячейку как пустую. Как только это выполнено, последующие элементы могут быть недоступны для этой операции, - точнее говоря, не все последующие элементы, а только те, которые находятся в том же кластере, что и только что удаленный элемент. Таким образом, мы всего лишь временно удаляем все элементы кластера, которые располагаются за полностью удаленным элементом, и снова их вставляем. Понятно, что обработка этих элементов выполняется по одному. При создании кода программы, нужно было бы начать с ячейки, расположенной за той, которая только что была помечена как пустая, и выполнять цикл до тех пор, пока не встретится пустая ячейка (обратите внимание, что в данном случае не следует беспокоиться о возникновении бесконечного цикла - известно, что с момента создания хеш-таблицы в ней появилась, по меньшей мере, одна пустая ячейка). Мы помечаем ячейку каждого элемента как пустую, а затем повторяем его вставку.
В заключение рассмотрим возможность преобразования хеш-таблицы в динамическую хеш-таблицу. Эта задача достаточно проста, хотя и трудоемка. Если коэффициент загрузки становится слишком большим, мы выделяем новую хеш-таблицу, которая больше старой (скажем, в два раза), переносим элементы исходной хеш-таблицы в новую (обратите внимание, что хеш-значения изменятся, поскольку новая хеш-таблица больше) и, наконец, освобождаем старую хеш-таблицу. Это все. Единственное небольшое "но" заключается в том, что в идеале желательно, чтобы размер новой хеш-таблицы был простым числом, как и размер исходной таблицы.
Класс хеш-таблиц с линейным зондированием
В листинге 7.3 приведен код интерфейса для хеш-таблицы с линейным зондированием (полный исходный код этого класса можно найти на web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshLnP.pas). По поводу этой реализации следует привести ряд замечаний. Во-первых, мы принимаем соглашение, что ключом элемента является строка, отдельная от самого элемента. Это существенно упрощает как понимание кода, так и разработку и использование хеш-таблицы. В подавляющем большинстве случаев ключи все равно будут строками, а преобразование других типов данных в строки обычно не представляет особой сложности.
