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

Таблица символов – это таблица состоящая из набора полей, количество которых равно числу идентификаторов программы. Каждое поле содержит в себе полную информацию о данном элементе таблицы.

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

Идентификаторы, их описание. Под идентификаторами подразумеваются константы, переменные, имена процедур и функций, формальные и фактические параметры.

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

        Организация такой последовательности идентификаторов, при которой поиск будет наискорейшим, а объем таблицы наименьшим.

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

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

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

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

Таблицы расстановки — (или хеш-таблица). Поиск в такой таблице может быть организован методом повторной расстановки. Таблица символов представляет собой массив фиксированного размера N. Идентификаторы могут храниться как в самой таблице символов, так и в отдельной таблице идентификаторов.

Таблицы на деревьях — организация таблиц символов с использованием двоичных деревьев.

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

Логарифмический поиск (бинарный) используется в основном в упорядоченном списке. Символ S, который следует найти, сравнивается с элементом (n + 1)/2 в середине таблицы. Если этот элемент не является требуемым, мы должны просмотреть только блок элементов, пронумерованных от 1 до (n + 1)/2 — 1, или блок элементов от (n + 1)/2 + 1 до n в зависимости от того, меньше искомый элемент S или больше того, с которым его сравнили. Затем мы повторяем процесс над блоком меньшего размера. Так как на каждом шаге число элементов, которые могут содержать S, сокращается наполовину, то максимальное число сравнений равно 1 + log₂ n. Для сравнения: при для n = 128 бинарный поиск требует самое большее 8 сравнений, поиск в неупорядоченной таблице — в среднем 64 сравнения.

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

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

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

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

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

Хеш-функцией F называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z: F(r) = n, rÎR, nÎZ. При работе с таблицей идентификаторов хеш-функция должна выполнять отображение имен идентификаторов на множество целых неотрицательных чисел. Областью определения хеш-функции будет множество всех возможных имен идентификаторов.

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

+ : поскольку как время размещения элемента в таблице, так и время его поиска определяются только временем, затрачиваемым на вычисление хеш-функции, которое в общем случае несопоставимо меньше времени, необходимого на многократные сравнения элементов таблицы.

— : неэффективное использование объема памяти под таблицу идентификаторов(размер массива для ее хранения должен соответствовать области значений хеш-функции)

— : необходимость соответствующего разумного выбора хеш-функции.

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

Коллизия – когда двум или более идентификаторам соответствует одно и то же значение функции. Это происходит, потому что могут попасться записи с одними и теми же идентификаторам. Полностью избежать коллизий на практике не возможно, т.к. для их размещения нужно использовать память, которая всегда конечна. Избежать коллизий можно только в теории, используя бесконечную память ЭВМ.

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

Согласно этому методу, если для элемента A адрес h(A), вычисленный с помощью хеш-функции h, указывает на уже занятую ячейку, то необходимо вычислить значение функции n₁=h₁(A) и проверить занятость ячейки по адресу n₁. Если и она занята, то вычисляется значение h₂(A) и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение h_i(A) совпадет с h(A). Методы: использовать последовательность псевдослучайных целых чисел; квадратичные вычисления; вычисление по формуле

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

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

 

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

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