Организация информационных таблиц транслятора с хеш-адресацией
В основе организации таблиц с хеш-адресацией лежит процедура хеширования. Хеширование – преобразование символьного имени идентификатора в числовой индекс элемента таблицы с помощью простых арифметических и логических операций.
Конкретный способ хеширования задает хеш-функция., аргументом которой является символьная величина, т.е. имя идентификатора, а значение – числовой индекс элемента таблицы.
Простейший вариант таблицы с хеш-адресацией может служить использованием кода внутреннего представления 1-го символа имени. В этом случае: ABD-01000001ый соответствует предствавлению символа – «А» Схематично такой способ адресации можно представить след-м образом:
С помощью хеш-функции каждое имя само указывает свое место в таблице. До тех пор, пока для двух различных имен результаты хеширования отличаются, время поиска элемента в таблице равно времени вычисления хеш-функции. Хеш-функция задает отображение множества имен на множество индексов элементов таблицы и в идеале должна давать различные значения для двух любых отличающихся имен. Но это невозможно, т.к. любой язык допускает бесконечное количество имен, а объем таблицы ограничен. Т.о. всегда возможен конфликт при попытке записи двух отличающихся имен в одну ячейку таблицы. Такой конфликт называется коллизией и возникает, когда для отличающихся имен значения хеш-функции совпадают. Коллизии можно разрешить 2 методами:
- рехеширование и
- методом цепочек.
Т.о. результат хеширования имени, записанного в таблицу, определяет начальный индекс, начиная с которого в таблице производится поиск этого имени.
Главная
Каталог файлов
