Лекция 17. Погрешность численного интегрирования

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

Построение таблиц идентификаторов по методу цепочек.

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

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

· нет необходимости заполнять пустыми значениями таблицу идентификаторов, поскольку это можно сделать только для хеш-таблицы;

· каждому идентификатору соответствует одна ячейка в таблице идентификаторов (не будет пустых неиспользуемых ячеек);

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

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

Алгоритм работы метода цепочек.

· Во все ячейки хеш-таблицы поместить пустое значение, таблица идентификаторов — пуста, переменная HeapPtr (указатель первой свободной ячейки) указывает на начало таблицы идентификаторов; i:=1.

· Вычислить значение хеш-функции n_i для нового элемента A_i; если ячейка хеш-таблицы по адресу n_i — пустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе – к шагу 3.

· j:=1; выбрать из хеш-таблицы адрес ячейки таблицы идентификаторов m_j и перейти к шагу 4.

· Для ячейки таблицы идентификаторов по адресу m_j проверить значение поля ссылки; если оно пустое, то записать в него адрес из переменной FreePtr и перейти к шагу 5; иначе – j:=j+1, выбрать из поля ссылки адрес m_j и повторить шаг 4.

· Добавить в таблицу идентификаторов новую ячейку, записать в нее информацию для элемента A_i (поле ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки; если больше нет идентификаторов, которые надо разместить в таблице, то выполнение алгоритма закончено, иначе – i:=i+1 и перейти к шагу 2.

Алгоритм поиска элемента в таблице идентификаторов.

· Вычислить значение хеш-функции n=h(A) для искомого элемента A; если ячейка хеш-таблицы по адресу n — пустая, то элемент не найден и алгоритм завершен; иначе – j:=1, выбрать из хеш-таблицы адрес ячейки таблицы идентификаторов m_j.

· Сравнить имя элемента в ячейке таблицы идентификаторов по адресу m_j с именем искомого элемента A: если они совпадают, то искомый элемент найден и алгоритм завершен, иначе перейти к шагу 3.

· Проверить значение поля ссылки в ячейке таблицы идентификаторов по адресу m_j: если оно пустое, то искомый элемент не найден и алгоритм завершен; иначе – j:=j+1, выбрать из поля ссылки адрес m_j и перейти к шагу 2.

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

Метод цепочек является эффективным средством организации таблиц идентификаторов.

Достоинства метода цепочек:

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

· расходы памяти, связанные с необходимостью иметь одно дополнительное поле указателя в таблице идентификаторов на каждый ее элемент, считается оправданными;

· позволяет более экономно использовать память, но требует организации работы с динамическими массивами данных.

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

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

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

Недостатком метода является необходимость работы с динамически распределяемыми областями памяти.

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

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

Дата добавления: 2014-01-11