Комбинированные способы построения таблиц идентификаторов

Выше в примере была рассмотрена весьма примитивная хеш-функция, которую никак нельзя назвать удовлетворительной. Хорошая хеш-функция распределяет поступающие на ее вход идентификаторы равномерно на все имеющиеся в распоряжении адреса, так что коллизии возникают не столь часто. Существует большое множество хеш-функций. Каждая из них стремится распределить адреса под идентификаторы по своему алгоритму, но, как было показано выше, идеального хеширования достичь невозможно.

То, какой конкретно метод применяется в компиляторе для организации таблиц идентификаторов, зависит от реализации компилятора. Один и тот же компилятор может иметь даже несколько разных таблиц идентификаторов, организованных на основе различных методов.

Как правило, применяются комбинированные методы. В этом случае, как и для метода цепочек, в таблице идентификаторов организуется специальное дополнительное поле ссылки. Но в отличие от метода цепочек оно имеет несколько иное значение. При отсутствии коллизий для выборки информации из таблицы используется хеш-функция, поле ссылки остается пустым. Если же возникает коллизия, то через поле ссылки организуется поиск идентификаторов, для которых значения хеш-функции совпадают по одному из рассмотренных выше методов: неупорядоченный список, упорядоченный список или же бинарное дерево. При хорошо построенной хеш-функции коллизии будут возникать редко, поэтому количество идентификаторов, для которых значения хеш-функции совпали, будет не столь велико. Тогда и время поиска одного среди них будет незначительным (в принципе, при высоком качестве хеш-функции подойдет даже перебор по неупорядоченному списку).

Такой подход имеет преимущество по сравнению с методом цепочек, поскольку не требует использования промежуточной хеш-таблицы. Недостатком метода является необходимость работы с динамически распределяемыми областями памяти. Эффективность такого метода, очевидно, в первую очередь зависит от качества применяемой хеш-функции, а во вторую — от метода организации дополнительных хранилищ данных.

Хеш-адресация — это метод, который применяется не только для организации таблиц идентификаторов в компиляторах. Данный метод нашел свое применение и в операционных системах, и в системах управления базами данных.

Порядок выполнения работы

1. Получить вариант задания у преподавателя.

2. Подготовить и защитить отчет.

3. Написать и отладить программу на ЭВМ.

4. Сдать работающую программу преподавателю.

Требования к оформлению отчета

Отчет по лабораторной работе должен содержать следующие разделы:

• Задание по лабораторной работе.

• Схему организации хеш-таблицы (в соответствии с вариантом задания).

• Описание алгоритма поиска в хеш-таблице (в соответствии с вариантом задания).

• Текст программы (оформляется после выполнения программы на ЭВМ по согласованию с преподавателем).

• Выводы по проделанной работе.

Основные контрольные вопросы

1. Что такое таблица символов и для чего она предназначена?

2. Какая информация может хранится в таблице символов?

3. Какие цели преследуются при организации таблицы символов?

4. Какими характеристиками могут обладать константы, переменные?

5. Какие существуют способы организации таблиц символов?

6. В чем заключается алгоритм логарифмического поиска? Какие преимущества он дает по сравнению с простым перебором и какие он имеет недостатки?

7. Расскажите о древовидной организации таблиц идентификаторов. В чем ее преимущества и недостатки?

8. В чем суть хеш-адресации ?

9. Что такое хеш-функции и для чего они используются?

10. Расскажите о преимуществах и какие недостатках организации таблицы идентификаторов с помощью хеш-функции.

11. Что такое коллизия? Почему она происходит? Можно ли полностью избежать коллизий?

12. Что такое рехеширование? Какие методы рехеширования существуют?

13. В чем заключается метод цепочек ?

14. Как могут быть скомбинированы различные методы организации хеш-таблиц ?