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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

2.3.2. Случайное рехеширование
Этот метод снимает проблему скопления, которая свойственна линейному рехешированию, за счет
выбора в качестве p
i
достаточно использовать самый элементарный генератор случайных чисел, вы-
дающий все числа в интервале от 0 до n – 1 по одному разу. Каждый раз, когда используется генератор
случайных чисел, он устанавливается в одно и то же состояние. Таким образом, когда происходит об-
ращение к h, генерируется одна и та же последовательность p
1
, p
2
, … .
2.3.3. Рехеширование сложением
В этом случае принимаем p
i
= i * h, где h – исходный хеш-индекс. Таким образом рассматриваются
элементы таблицы с номерами h, 2h, 3h, 4h … . Этот метод хорош, если размерность таблицы n будет
простым числом, то все последовательности полностью покроют все возможные индексы 1, …, n – 1.
Метод описывается формулой:
11,mod))(()(
−
≤
≤
= ninaihah
i
.
2.4. МЕТОД ЦЕПОЧЕК
Метод цепочек использует хеш-таблицу, элементы которой первоначально равны 0, собственно
таблицу символов, вначале пустую, и указатель УК, который указывает на текущее положение послед-
него элемента в таблице символов. Элементы таблицы символов имеют дополнительное поле СНАIN,
которое может содержать 0 или адрес другого элемента таблицы символов. Начальное состояние табли-
цы приведено на рис. 12.
Хеш-функция, примененная к символу, дает индекс указателя в хеш-таблице. Указатель либо равен
0, либо указывает на первый элемент таблицы символов с данным значением хеш-функции. Поле
СНАIN каждого элемента используется для того, чтобы связать в цепочку элементы, для которых хе-
ширование символа приводит к тому же самому указателю. Например, в таблицу необходимо записать
символ S1. Функция хеширования вырабатывает адрес элемента хеш-таблицы, например 4. Содержимое
этой ячейки равно 0. Тогда выполняется следующее:
1. Прибавляем 1 к УК.
2. Вносим элемент (S1, значение, 0) в позицию таблицы символов, на которую указывает УК.
3. Заносим содержимое УК в указатель 4 хеш-таблицы.
№
Хеш-
таблица
№
Аргу-
мент
Значе-
ние
CHAIN
0 1
1 2
… …
N – 1
N
УК = 0
Рис. 12
№
Хеш-
таблица
№
Аргу-
мент
Значе-
ние
CHAIN
0 1 S1 … 0
1 2 2 S2 … 0
2 3 S3 … 0
3 3 4 S4 … 0
4 1
5
6 4
УК = 4
Рис. 13

Страницы