2.3 Обработка коллизий
2.3.1 Основные концепции
Все существующие методы обработки коллизий можно разделить на две основные категории:
- методы, называемые внутренней адресацией, в которых в качестве резервных используются ячейки самой таблицы хеширования;
- методы, в которых для хранения элементов с одинаковыми хеш-адресами отводится специальная область переполнения.
Для внутренней адресации используются различные, часто сложные, алгоритмы, позволяющие повысить эффективность поиска. В отличие от этих методов – методы 2-го типа (переполнения) – достаточно просты.
Если определить эффективность как среднее число операций поиска, необходимых для выборки одного элемента таблицы, то преимущество 2-й группы методов может показаться очевидным. Тем не менее, больше применяются методы 1-й группы (т.е. внутренняя адресация).
Процедура, при помощи которой в методе внутренней адресации отыскиваются резервные ячейки, получила название пробинга. В сущности, пробинг является методом проб и ошибок, примененным к поиску пустой ячейки. Какой бы конкретный алгоритм ни был положен в основу этой процедуры, последовательность определяемых им действий обязательно должна быть детерминированной, т.к. при записи и выборке ЭД выполняются одни и те же операции.
Разработано много различных высокоэффективных алгоритмов пробинга, о некоторых из них кратко будет сказано ниже.
Применение идентификаторов и специальных маркеров в таблице хеширования
Последовательность операций доступа к ячейке с вычисленным адресом или к резервной ячейке выполняется всегда одним и тем же способом, как при записи, так и при считывании (выборке). Отклонения (от этого правила) имеют место при удалении записи из таблицы хеширования.
Процедуры пробинга, как правило, сами по себе не могут дать информации о местонахождении элемента. Для того чтобы определить, в какой из резервных ячеек находится искомый ЭД, в них, а также в вычисленную ячейку, записываются копии соответствующих ключевых слов. В процессе поиска эти копии сравниваются с аргументом (поиска) до тех пор, пока не будет достигнуто совпадение. В некоторых случаях вместо ключевого слова может использоваться более короткий идентификатор (например, при использовании метода деления).
Необходимо также как-то отмечать ячейки, в которых записана информация (по необходимости) – например, записывается ЭД ? 0. Или – один из разрядов ячейки использовать для признака – занято (1-0).
Как правило, неизвестно, в какой из ячеек (записей) содержится требуемое ключевое слово. Поэтому процедуру пробинга приходится выполнять до тех пор, пока оно не будет найдено. Если же требуемого ключевого слова в таблице нет, то это можно будет обнаружить только после перебора всех записей (ячеек).
Чтобы ограничить количество операций поиска, необходимо как-то отмечать конец цепочки резервных ячеек. Для этого используют специальные маркеры. Например, специальный разряд в каждой ячейке, или специальная ячейка на всю цепочку, в которой должен содержаться терминальный идентификатор (например, запрещенное ключевое слово, или ЭД, и др.).
2.3.2 Внутренняя адресация
Основные методы пробинга
В простейшем варианте таблица хеширования занимает одну область памяти, в которой содержатся ячейки с вычисленными адресами, так и резервные ячейки. Такая схема построения таблицы называется внутренней адресацией. Адреса резервных ячеек формируются путем добавления к вычисленному адресу некоторого смещения, величина которого определяется по определенному правилу. Процедуру поиска резервной ячейки, исходя из вычисленного адреса, называют пробингом. Имеется несколько типов пробинга:
- линейный пробинг – к хеш-адресу последовательно прибавляется или вычитается по единице до тех пор, пока не обнаружится пустая ячейка;
- квадратичный пробинг – последовательность резервных адресов определяется с использованием некоторой квадратичной функции;
- случайный пробинг, в котором смещение вычисляется с помощью датчика псевдослучайных чисел (ДПСЧ). Следует иметь в виду, что адреса всегда назначаются по циклическому принципу. Пусть количество ячеек в таблице хеширования равно H, а ее начальный адрес B. Если после добавления смещения получен адрес fi, то в качестве истинного адреса резервной ячейки берется величина
fi mod H + B.
v mod A (fi mod H) – наименьший положительный вычет (v – A)
из v вычтен модуль A(H) =
это остаток от деления v на A(H).
Удаление записей
При работе с таблицей хеширования (ТХ) с течением времени возникает необходимость в удалении из нее неиспользованных элементов. В результате освобождается пространство для записи новой информации, и сокращаются задержки, связанные с обработкой ЭД, тоже не участвующих в решении задачи. При этом ячейку, содержащую неиспользуемый ЭД, нельзя просто пометить – как пустую, иначе она при пробинге будет рассматриваться как конец цепочки резервных ячеек. Поэтому приходится всю последовательность записей сдвигать на одну ячейку в направлении вычисленного адреса. Наиболее удобен в данном отношении линейный пробинг. Случайный пробинг, наоборот, оказывается крайне громоздким, поскольку алгоритмы получения псевдослучайных чисел принципиально необратимы.
Ячейку с ЭД, подлежащему удалению, можно пометить специальным маркером (например, отдельного разряда). Когда такой маркер встречается при выполнении процедуры пробинга, поиск продолжается дальше.
Если вычисленный адрес совпадает с адресом ячейки, помеченной как свободная, она может служить началом новой цепочки. В этом случае резервные ячейки выстраиваются вслед за старой цепочкой, которая обходит эту ячейку. При этом сокращается время операции поиска.
Этот метод (маркерный) особенно удобен при применении линейного пробинга.
Для экономии памяти вместо флажкового разряда можно использовать:
- либо специальное ключевое слово;
- либо данные, которые по какой-то причине не запрещено употреблять.
Ячейки, содержащие подобный код, играют роль маркера.
Проблема первичного группирования. Процедуры квадратичного и случайного пробинга
Основная причина, по которой вместо линейного применяются квадратичный или случайный пробинг, связана с проблемой первичного группирования. При линейном пробинге резервные ячейки часто образуют длинные цепочки. Когда в таблице хеширования остается мало свободного места, подобные цепочки начинают перемешиваться. В результате количество операций поиска возрастает, особенно в тех случаях, когда обследуются все резервные ячейки некоторой цепочки. Иногда количество пересмотров может достигать нескольких сотен.
Сформулируем эту проблему более четко.
Предположим, что хеш-адрес h(k) и адреса резервных ячеек, соответствующих ключу k, образуют последовательность
{ f0(k), f1(k), f2(k),…}, f0(k) = h(k),
где fi(k) = [h(k) + gi] mod H
gi – смещение (1)
(i = 0, 1, 2,…, g0 = 0)
Пусть по какой-либо причине совпали адреса двух ячеек, отвечающих двум различным ключевым словам k1 и k2, т.е.
fi(k1) = fj(k2) (2)
i ? j • mod H и k1 ? k2
Говорят, что имеет место первичное группирование ячеек, если
fi+L (k1) = fj+L (k2) для L = 1, 2, 3,… (3)
Можно утверждать, что группирование характерно для пробинга линейного типа, поскольку условие (3) должно выполняться для любых значений fi(k1) и fj(k2), принадлежащих двум независимым последовательностям резервных адресов.
Первичное группирование можно устранить, если применять нелинейные методы, в частности, квадратичный пробинг. Этот метод удобен, т.к. не требует сложных вычислений.
Процедура квадратичного пробинга может быть описана следующим выражением:
gi = a•i + b•i2 (4)
(Для ЕС ЭВМ-III: a = -787; b = 1.)
Но это выражение накладывает определенные ограничения на длину хеш-таблицы (= степени “2”), выбор значений a и b.
Предлагались и другие выражения для вычисления смещения gi.
Случайный пробинг
В процессе процедуры случайного пробинга алгоритм рандомизации используется дважды:
1) для вычисления функции хеширования h(v), где v – численное значение ключевого слова;
2) для генерации последовательности псевдослучайных чисел { di }.
Адрес первой просматриваемой ячейки определяется по формуле:
f1 = (h + d1) mod H;
адреса остальных резервных ячеек – по формуле
fi = ( fi-1 + di ) mod H, i = 1, 2,…;
di – псевдослучайное число.
Отметим, что наличие операции “mod H” не снимает ограничений, накладываемых на диапазон изменения чисел di, т.к. нежелательно, чтобы в какой-либо части таблицы хеширования поиск стал производиться повторно, прежде, чем будут обследованы все ее H ячеек. Отсутствие повторных (двойных просмотров) гарантируется, если все числа di < H и не имеют с H общих множителей (кроме 1).
Например, если H является степенью числа 2, то di может быть любым нечетным числом, меньшим H, а если H – простое число, то di может быть любым числом, меньшим H.
Вторичное группирование. Двойное хеширование
Одна из проблем, связанных с методом внутренней адресации, заключается в следующем:
Всякий раз, когда двум и более ключевым словам присваиваются одинаковые хеш-адреса, формируется одна и та же последовательность резервных ячеек. Это явление называют вторичным группированием. Оно может снизить эффективное быстродействие процедур квадратичного или случайного пробинга, если средняя длина цепочек резервных ячеек достаточно велика.
Если рассматривать задачу поиска по одному ключу, резонно предположить, что конфликтующим элементам таблицы хеширования должны отвечать различные ключевые слова. При этом можно сделать так, чтобы адресные смещения, формируемые процедурой пробинга, как и хеш-адрес, зависели от числового значения ключа. В результате получается двойное хеширование, в котором участвуют две функции:
h(v) – хеш-адрес, соответствующий численному значению ключевого слова;
i (v) – “хеш-смещение”, соответствующее значению v.
Переменные h и i могут изменяться в пределах [0, H – 1],
где H – число ячеек в таблице хеширования.
Кроме того, величина i не должна иметь общих множителей с числом H.
Если используется алгоритм вычисления хеш-смещения, обеспечивающий равномерное появление любых допустимых пар [ h(v), i(v) ], то такой метод называют независимым двойным хешированием (а также – равномерным хешированием).
Методы устранения группирований
- Квадратичный пробинг с переменным коэффициентом
Используется для устранения вторичного группирования (сам квадратичный пробинг позволяет избавиться от первичного группирования). Для этого предлагается использовать квадратичную функцию с параметрами, зависящими от численного значения ключевого слова. В этом случае алгоритм пробинга имеет вид:
Fi(k) = [ h(k) + gi(k) ] mod H, (6)
где gi(k) = a•i + b(k)•i2,
b(k) – переменный коэффициент.
Для определения b(k) могут использоваться различные методы (деления и др.).
2) Линейный пробинг с переменным смещением
С помощью этого метода удается избавиться также от первичного группирования.
Для этого метода (применительно к хешированию) предложен такой алгоритм пробинга:
fi(k) = [ fi-1(k) + Q ] mod H, (7)
где Q – частное от деления v(k) на H.
Имеются и другие алгоритмы с теми или иными ограничениями на H, …
3) Сокращение числа проб в ходе выборки за счет перестройки ранее сформированных цепочек (на этапе записи)
Идея этого метода заключается в перестройке таблицы хеширования при записи в нее нового ключевого слова. Алгоритмов тоже несколько.
4) Метод пересекающихся цепочек
В большинстве задач управления данными в первую очередь стремятся минимизировать продолжительность выборки ЭД. Что касается записи информации в таблицу (при ее первичном заполнении или в процессе модификации), то обычно на эту операцию отводится больше времени.
Если бы имелась возможность запоминать результаты вычислений, выполненных в ходе пробинга, то было бы нерационально воспроизводить их заново на этапе выборки.
Действительно, последовательность адресов резервных ячеек можно сохранить и затем их использовать для ускорения поиска.
Выделив в каждой ячейке памяти специальное поле, последовательность адресов можно представить в виде структуры типа ЦЕПОЧКА или СВЯЗАННОГО СПИСКА. Начиная с ячейки, расположенной по вычисленному хеш-адресу, в отведенное поле заносится адрес следующей резервной ячейки (который был вычислен в момент записи соответствующего элемента данных).
В результате – на этапе поиска для получения адреса очередной ячейки никаких арифметических операций производить не требуется. Адреса, помещаемые в ячейки, называются указателями. Рассмотренный тип структуры определим как ЦЕПОЧКУ С НЕПОСРЕДСТВЕННЫМИ СВЯЗЯМИ.
Этот метод позволяет значительно сократить количество просмотров в ходе выборки, т.к. на поиск резервных ячеек не тратится лишнее время.
Большим достоинством метода цепочек является простота добавления к связанному списку новых элементов (см. рисунок 2.2).
Предположим, что произошла очередная коллизия. После того, как будет найдена новая резервная ячейка, ее адрес заносится на место старого указателя в точке коллизии, а старый – запоминается в поле указателя новой резервной ячейки. Остальная часть адресной цепочки не меняется, и ни один из ранее записанных ЭД не переносится в другую ячейку.
Заметим, что после очередной коллизии элементы данных располагаются уже в другом порядке, не в том, в котором шел просмотр потенциальных резервных ячеек в процессе пробинга. Но это не усложняет последующего поиска. Более того, элементы, попавшие в таблицу последними, располагаются ближе остальных к вычисленному адресу. И это очень важно, т.к. согласно статистике, новые ЭД запрашиваются чаще старых.
Рассмотренный метод цепочек не исключает возможности того, что несколько цепочек, начинающихся с различных вычисленных адресов, наложатся друг на друга. Учитывая это, в дальнейшем будем называть его методом пересекающихся цепочек.
В отличие от обычных хеш-таблиц процедура удаления ЭД из пересекающихся цепочек осуществляется значительно проще:
Содержимое ячейки памяти, стоящей за той, из которой удаляется запись, копируется в последнюю (удаляемую?), а сама ячейка помечается как свободная. Содержимое остальных ячеек не меняется.
Можно было бы это сделать и по-другому (например, заменить указатель в предыдущей ячейке, но этот способ не практикуется, т.к. в списочных структурах обычно отсутствуют средства прослеживания адресных ячеек в обратном направлении).
Для отмечания ячейки, на которой заканчивается адресная цепочка, в поле указателя заносится специальное условное число (например, 0) – константа, вычисленный адрес, соответствующий данной цепочке или адрес самой ячейки.
Существуют способы сужения поля, предназначенного для записи указателя (методы псевдоцепочек и др.).
Методы борьбы с коллизиями II-й категории
2.3.4 Использование отдельной области переполнения
Метод внутренней адресации дает определенные преимущества при работе с многоуровневой памятью, т.к. в ней обмен данными ведется через буферы, и информация передается поблочно. Поэтому удобно, если все данные, подлежащие пересылке, располагаются в одной локальной области памяти. Но т.к. метод хеширования широко применяется в ассемблерах и компиляторах для формирования таблиц и символов, необходимо рассмотреть и второй основной способ обработки коллизий, более подходящий для таблиц такого типа.
Этот метод основан на использовании отдельной области памяти, именуемой областью переполнения, из которой по мере необходимости берутся резервные ячейки для размещения конфликтующих элементов. И т.к. цепочки, соответствующие различным вычисленным адресам, в соответствии с данным методом формируются независимо друг от друга, чаще всего этот метод называют методом непересекающихся цепочек (рисунок 2.3).
Показан случай двух коллизий в первой ячейке и одной коллизии – в третьей.
Адреса ячеек области переполнения не зависят от вычисленных адресов, поэтому построение цепочек является единственным способом их объединения в последовательность резервных ячеек. Резервные ячейки берутся из области переполнения последовательно в порядке возрастания адресов, поэтому пробинг не требуется. Это позволяет ускорить обработку информации (при записи и при чтении) и сократить среднее количество обращений к памяти. Это особенно проявляется при большом коэффициенте заполнения таблицы хеширования.
На рисунке 2.3 показан простейший способ размещения элементов в области переполнения на практике. Каждый новый элемент, попадающий в эту область, обычно связывается указателем непосредственно с вычисленным адресом. Поэтому при поиске недавно записанной информации не требуется просматривать всю цепочку адресов и кроме того, существенно упрощается процедура записи новых элементов.
Напомним, что для сокращения пространства для хранения ключевой информации в хеш-таблице применяются разные методы, например, замена ключевого слова на частное от деления ключевого слова на что-либо (т.е. идентификатор).
Отметим также, что все преимущества этого метода проявляются и при работе с многоуровневой памятью.
2.3.5 Рехеширование
Применение отдельной области переполнения позволяет устранить проблемы, возникающие при значительной загруженности таблиц хеширования. На практике считается, что коэффициент заполнения не должен быть больше 0,8 – 0,9. Поэтому необходимо иметь автоматическую процедуру, которая помогала бы вовремя приостанавливать рост коэффициента заполнения.
- Одно из возможных решений этой задачи состоит в добавлении новых ячеек в таблицу хеширования путем расширения области значений исходной хеш-функции. Однако с учетом того, что ранее записанные элементы должны оставаться на своих местах, распределение занятых ячеек в целом становится весьма неравномерным.
- Этого недостатка нет у другого метода, в котором место старой ТХ предлагается вводить новую хеш-таблицу, но большего размера и осуществлять ее рехеширование (повторное размещение) всех элементов, содержащихся в старой ТХ. Переход к новой таблице производится после того, как загруженность старой таблицы хеширования достигнет некоторого порогового уровня, например, 80 %. Перезапись информации в новую таблицу производится последовательно, элемент за элементом. Отметим, что для реализации этого метода в ячейках таблицы хеширования должны храниться полные ключевые слова, т.к. они необходимы для вычисления значений новой хеш-функции.
2.3.6 Методы ускорения процедур поиска
а) Флажок коллизии
Предлагается зарезервировать в каждой ячейке таблицы специальный разряд, называемый флажком коллизии, при помощи которого можно определить, имеется ли в таблице требуемый элемент. Существует две причины, по которым поисковый аргумент или заменяющий его идентификатор может не совпадать с записанным по вычисленному адресу ключевым словом (или идентификатором):
- либо элемент с данным ключевым словом содержится в таблице, но вследствие коллизии он записан в резервную ячейку;
- либо его просто нет в таблице.
Предполагается, что во флажковом разряде первоначально записан “0”. После того, как произойдет первая коллизия в данной ячейке, флажок переводится в “1”. Т.о. если по вычисленному адресу ключевое слово не совпадает с аргументом поиска, а флажок = 0, то это означает, что ни в одной из резервных ячеек искомого ключа нет, и поиск надо прекратить.
Флажок коллизии удобно использовать в комбинации с флажком “занято”. В этом случае флажок коллизии в каждой ячейке таблицы, за которой следует резервная ячейка, устанавливается в “1”. После удаления элемента флажок “занято” > 0, который означает, что ячейка свободна. Однако если флажок коллизии в данной ячейке = 1, то это указывает, что цепочка резервных ячеек не закончилась и поиск надо продолжать.
б) Упорядоченные таблицы хеширования
В основе этого метода лежат следующие соображения:
Пусть элементы, образующие цепочку, упорядочены по какому-либо принципу (например, по алфавиту, или в порядке нарастания численных значений ключа). Отсутствие требуемой записи при этом легко установить путем последовательной сверки поискового аргумента с элементами списка. Если результат очередной проверки противоположен результату предыдущему, то в оставшейся части цепочки искомый элемент заведомо отсутствует.
в) Виртуальные хеш-адреса
Еще один прием ускорения процедуры просмотра резервных ячеек.
При использовании принципа внутренней адресации в ходе пробинга среди проверяемых ячеек могут оказаться такие, которые содержат элементы, относящиеся к посторонним вычисленным адресам.
Идея данного метода состоит в том, чтобы быстрее выяснить, принадлежит ли очередной элемент к цепочке, соответствующей требуемому хеш-адресу: если проверка дает отрицательный ответ, то дальнейший поиск не нужен.
С этой целью предлагается использовать функцию хеширования, которая формирует виртуальный хеш-адрес, имеющий на несколько битов больше, чем нужно для обращения к ячейкам таблицы. Дополнительные старшие биты служат идентификатором вычисленного адреса и хранятся в ячейке совместно с ключевым словом. Младшие разряды виртуального хеш-адреса образуют истинный адрес ячейки внутри таблицы.
Вместо ключевых слов вначале сравнивается содержимое дополнительных разрядов. Если длина ключевых слов велика, то указанная операция занимает значительно меньше времени, чем сравнение самих ключей. В итоге увеличивается среднее быстродействие, но ценой затрат на хранение дополнительных битов.