3.7.1. Рехеширование
Предположим, что мы хешируем слово S и обнаруживаем, что другое слово уже заняло элемент h. Возникает коллизия. Тогда сравниваем S с элементом h+P1 (по модулю N, где N – длина таблицы) для некоторого целого P1. Если снова возникает коллизия, сравниваем S с элементом h+P2 и т.д. Это продолжается до тех пор, пока не встретится какой-либо элемент h+Pi (по модулю N), который либо пуст, либо содержит S, либо снова является элементом h (Pi=0). В последнем случае мы прекращаем выполнение программы, поскольку таблица полна.
Таким образом, если возникло i коллизий, будет выполнено i+1 сравнений с элементами hi=h+Pi (по модулю N). Величины Pi должны выбираться так, чтобы ожидаемое число сравнений Е было невелико и чтобы по возможности было рассмотрено большее число элементов.
Рехеширование обычно связывается с термином рассеянной памяти, так как заполненные элементы таблицы оказываются рассеянными по ней. Чтобы отличать пустые элементы от заполненных, все элементы должны быть первоначально заполнены каким–либо значением, которое не может встречаться как символ (слово). Кроме того, таблица должна быть сразу рассчитана на максимальное число элементов. Это объясняется тем, что нет простого способа расширения таблицы (массива), если она заполнена, без повторного вычисления хеш–адресов для всех записанных элементов и занесения их в соответствующие новые позиции. Имеются несколько способов рехеширования, которые и будут рассмотрены ниже.
Линейное рехеширование – старейший и, вероятно, наименее эффективный из них. Он состоит в том, чтобы положить P1=1, P2=2, P3=3 и т. д. То есть сравниваются последовательные элементы. Предположим, например, что символы S1 и S2 были хешированны и записаны в элементы 2 и 4 соответственно (см. рис. 3.8 а)
Теперь предположим, что символ S3 также ссылается на элемент 2. Вследствие коллизии он будет занесен в элемент 3 (рис. 3.8 б). Наконец, предположим, что S4 также ссылается на элемент 2. Возникают последовательно 3 коллизии – с S1, S3 и S2 – прежде чем S4 заносится в элемент 5 (рис. 3.8 в). Причина низкой эффективности этого метода становится достаточно ясной из этого примера; после нескольких коллизий, разрешенных таким образом, элементы скапливаются вместе, образуя длинные цепочки заполненных элементов.
Оценка среднего числа сравнений Е для поиска одного элемента, полученная эмпирическим путем, составляет:
Е = (1 – Lf / 2) / (1 – Lf),
где Lf – коэффициент загрузки. Таким образом, если таблица заполнена на 10% мы можем ожидать 1.06 сравнений, если наполовину – 1.5 сравнений, если на 90%, то – 5.5 сравнений. Заметим, что Е не зависит от размера таблицы, а только от степени заполнения.
Случайное рехеширование снимает проблему скопления за счет выбора в качестве Pi псевдослучайных чисел. Если размер таблицы представляется степенью двойки (N = 2k, для произвольного k), то хорошие результаты дает следующий способ вычислений Pi :
1. При вызове программы положить целое R, равным 1.
2. Вычислить каждое Pi следующим образом
а) установить R=R5;
b) выделить младшие k+2 разряда R, и поместить результат в R;
с) взять величину из R, сдвинуть ее вправо на 2 разряда и результат назвать Pi.
Важнейшее свойства этого метода, предотвращающего скопление, состоит в том, что все числа Pi+k – Pi различны. Хорошее приближение ожидаемого числа сравнений в этом случае дает формула:
E = – (1 / Lf) log (1–Lf),
где Lf – коэффициент загрузки. Так, если таблица заполнена на 10% ожидается 1.05 сравнений, если наполовину – то 1.39, если на 90% – 2.56.
Рехеширование сложением
Положим Pi=ih, где h – искомый хеш–индекс. Таким образом мы будем пробовать элементы h, 2h, 3h, 4h и т.д.(все значения вычисляются по модулю, равному размеру таблицы). Этот метод хорош, когда размер таблицы N является простым числом, так как все последовательности накрывают полностью все возможные индексы от 1 до N–1.
Очевидный недостаток рассмотренных методов рехеширования – неизменный, рассчитанный на максимум размер таблицы и это скорее не руководство к действию, а экскурс в историю, хотя подобные подходы и до сих пор практикуются при размещении информации на дисках.
3.7.2. Хеш–функция
Как уже отмечалось, выбор хеш–функции очень сильно влияет на эффективность рассматриваемых методов организации таблиц. Обычно, если слово S, являющееся аргументом хеширования, занимает более одного машинного слова, то на первом шаге хеширования по S формируется одно машинное слово S /. Как правило, S / вычисляется суммированием всех слов из S при помощи поразрядного сложения по модулю 2 (то есть при помощи операция XOR – исключающее или).
На втором шаге из S / вычисляется окончательный индекс, причем это можно сделать несколькими способами:
1. Умножить S / само на себя и использовать n средних битов в качестве значения функции хеширования (если таблица имеет 2n элементов). Поскольку n средних битов зависит от каждого бита S /, этот метод дает очень хорошие результаты.
2. Использовать какую–либо логическую операцию, например тот же XOR, над некоторыми частями S /.
3. Если в таблице имеется 2n элементов, расщепить S / на n частей и просуммировать их. Использовать n правых крайних битов результата.
4. Разделить S / на длину таблицы и остаток использовать в качестве хеш–индекса.
Все эти методы применялись и давали удовлетворительные результаты. Можно предложить и другие методы. Нужно только быть уверенным, что на множестве аргументов, к которому будет применяться функция хеширования, она даст достаточно случайные адреса. Это легко проверить, формируя таким образом таблицу терминалов (ключевых, зарезервированных слов языка). В принципе, выделение ключевых слов в отдельную таблицу вовсе необязательно. Их можно поместить в общую таблицу идентификаторов при начальной загрузке компилятора, снабдив соответствующим признаком. Стоит проверить эту первоначальную таблицу на число возникших коллизий. Хеш–функция может быть достаточно хорошей с точки зрения статистики, но может как раз случиться, что 20 зарезервированных слов ссылается на один и тот же адрес.
Например, в компилятора PL/1 F фирмы IBM, реализованного в начале 70–х годов, использовалось следующая хеш–функция:
1. Суммировались последовательные части идентификатора, содержащие по 4 символа, в один 4–байтовый регистр.
2. Результат делился на 211 и определялся остаток R.
3. Значение 2R использовалось в качестве индекса для ссылки на таблицу из 211 указателей (каждый указателей имеет длину 2 байта).
В этом компиляторе для разрешения коллизии использовался не метод рехеширования, а метод цепочек (гроздей), который, конечно же, предпочтительнее в системах с динамическим распределением памяти.