Основы разработки трансляторов в САПР. Коробова И.Л - 25 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

лица состоит из N элементов, где N заранее фиксировано. Метод хеш-адресации заключается в преоб-
разовании символа в индекс элемента в таблице. Индекс получается хешированием символа, т.е. вы-
полнением над ним некоторых операций. Если в процессе компиляции встретился объект а, то для
поиска его в таблице можно воспользоваться следующим алгоритмом: если объект уже встречался
ранее, то h(а) – ячейка в таблице, в которой хранится а. Если объект а ранее не встречался, то h(а) –
пустая ячейка, в которую заносится информация для а.
Таблица 7
№ Аргумент Значение
0
1
… … …
h(a)
… … …
N – 1
Возникает, однако, затруднение, если результаты хеширования двух разных символов совпадают.
Это называется коллизией. Очевидно, в данной позиции таблицы может быть помещен только один из
этих символов, так что мы должны найти свободное место для второго. Желательно иметь такую хеш-
функцию, которая распределяла бы объекты равномерно по всей таблице, так чтобы коллизии не воз-
никали слишком часто. Но избежать их совсем практически не удается, поэтому разработчику компиля-
тора следует предусмотреть способы решения задачи коллизии. Существует два таких способа – рехе-
ширование и метод цепочек.
Для простоты предположим, что каждый табличный элемент занимает одно слово. Тогда для таб-
лицы с n элементами значениями функции хеширования h являются целые числа 0, 1, 2, …, n – 1. Если
табличный элемент состоит из k слов, то для вычисления его адреса, необходимо к базовому адресу
таблицы добавить произведение значения хеш-функции h на k.
2.3. РЕХЕШИРОВАНИЕ
Предположим, что мы хешируем символ S и обнаруживаем, что другой символ уже занял элемент с
номером h. Возникает коллизия. Тогда сравниваем S c элементом в ячейке h + p
1
(для некоторого целого
p
1
). Если снова возникает коллизия, сравниваем S с элементом h + p
2
. Это продолжается до тех пор, пока
не встретится ячейка h + p
i
, которая либо пуста, либо содержит S, либо совпадает с ячейкой h (p
i
= 0). В
последнем случае считаем, что таблица переполнена.
Таким образом, если возникло i коллизий, будет выполнено i + 1 сравнение с элементами таблицы.
Элементы p
i
должны выбираться так, чтобы ожидаемое число сравнений было невелико, но при этом
рассматривалось большее число элементов. В идеальном случае p
i
должны охватывать целые числа 0, 1,
…, n – 1.
Существуют несколько способов рехеширования. Рассмотрим некоторые из них.
2.3.1. Линейное рехеширование
Это простейший метод рехеширования, состоящий в том, чтобы принять p
1
= 1, p
2
= 2, p
3
= 3 и так
далее. В этом случае мы двигаемся по таблице вперед относительно значения h(a) до тех пор, пока не
исчезнет коллизия. Если достигнута позиция n – 1, переходим на позицию 0. Метод прост для выполне-
ния, однако, если уже возник конфликт, то занятые позиции имеют тенденцию скапливаться. Метод вы-
ражается формулой
11,mod))(()(
−
≤
≤
+
= niniahah
i

Страницы