III. Структуры, организация, хранение и поиск данных
Назначение и принципы организации таблиц идентификаторов
Коллизии.
Методы разрешения коллизий
4. Рехеширование (продолжение).
Алгоритм поиска элемента в таблице идентификаторов
· Вычислить значение хеш-функции n = h(A) для искомого элемента A.
· Если ячейка по адресу n пустая, то элемент не найден, алгоритм завершен, иначе – сравнить имя элемента в ячейке n с именем искомого элемента A: если они совпадают, то элемент найден и алгоритм завершен, иначе – i:=1 и перейти к шагу 3.
· Вычислить ni = hi(A). Если ячейка по адресу ni пустая или n = ni, то элемент не найден, и алгоритм завершен, иначе – сравнить имя элемента в ячейке ni с именем искомого элемента A: если они совпадают, то элемент найден и алгоритм завершен, иначе – i:=i+1 и повторить шаг 3.
Алгоритмы размещения и поиска элемента схожи по выполняемым операциям, поэтому они имеют одинаковые оценки времени, необходимого для их выполнения.
При такой организации таблиц идентификаторов в случае возникновения коллизии алгоритм размещает элементы в пустых ячейках таблицы, выбирая их определенным образом: элементы могут попадать в ячейки с адресами, которые потом будут совпадать со значениями хеш-функции, что приведет к возникновению новых, дополнительных коллизий. Таким образом, количество операций, необходимых для поиска или размещения в таблице элемента, зависит от заполненности таблицы.
Для организации таблицы идентификаторов по методу рехеширования необходимо определить все хеш-функции hi для всех i; функции hi определяют как некоторые модификации хеш-функции h. Простым методом вычисления функции hi(A) является ее организация в виде
hi(A) = (h(A) + pi) mod Nm
где pi – некоторое вычисляемое целое число, Nm – максимальное значение из области значений хеш-функции h. При pi = i hi(A) = (h(A)+i) mod Nm
При совпадении значений хеш-функции для каких-либо элементов поиск свободной ячейки в таблице начинается последовательно от текущей позиции, заданной хеш-функцией h(A). Этот способ является не самым удачным (при совпадении хеш-адресов элементы в таблице начинают группироваться вокруг них, что увеличивает число необходимых сравнений при поиске и размещении), но достаточно эффективным при организации таблиц идентификаторов при неполном заполнении таблицы.
Среднее время на помещение одного элемента в таблицу и на поиск элемента в таблице можно снизить, если применить более совершенный метод рехеширования, например, использовать в качестве pi для функции hi(A)=(h(A)+pi) mod Nm последовательности псевдослучайных целых чисел p1, p2, …, pk. При хорошем выборе генератора псевдослучайных чисел длина последовательности k будет k=Nm.
Существуют также другие методы организации функций рехеширования hi(A), основанные на квадратичных вычислениях или, например, на вычислении по формуле:
hi(A) = (h(A)*i) mod Nm
если Nm – простое число.
Рехеширование позволяет добиться лучших результатов для эффективного поиска элемента в таблице, чем бинарный поиск и бинарное дерево, но эффективность метода очень зависит от заполненности таблицы идентификаторов и качества используемой хеш-функции – чем реже возникают коллизии, тем выше эффективность метода. Требование неполного заполнения таблицы ведет к неэффективному использованию объема доступной памяти.
Построение таблиц идентификаторов по методу цепочек.
Неполное заполнение таблицы идентификаторов при применении хеш-функций ведет к неэффективному использованию объема памяти, доступного компилятору; объем неиспользуемой памяти тем выше, чем больше информации хранится для каждого идентификатора. Этот недостаток можно избежать, если дополнить таблицу идентификаторов промежуточной хеш-таблицей.
В ячейках хеш-таблицы может храниться либо пустое значение, либо значение указателя на область памяти из основной таблицы идентификаторов, тогда хеш-функция вычисляет адрес, по которому происходит обращение сначала к хеш-таблице, а потом через нее по найденному адресу – к самой таблице идентификаторов. Если соответствующая ячейка таблицы идентификаторов пуста, то ячейка хеш-таблицы будет содержать пустое значение, и тогда не надо иметь в таблице идентификаторов ячейку для каждого возможного значения хеш-функции, т. е. таблицу можно сделать динамической – ее объем будет расти по мере заполнения (первоначально таблица идентификаторов не содержит ни одной ячейки, а все ячейки хеш-таблицы имеют пустое значение). Этот подход позволяет достичь следующего:
· нет необходимости заполнять пустыми значениями таблицу идентификаторов, поскольку это можно сделать только для хеш-таблицы;
· каждому идентификатору соответствует одна ячейка в таблице идентификаторов (не будет пустых неиспользуемых ячеек);
· пустые ячейки будут только в хеш-таблице, и объем неиспользуемой памяти не будет зависеть от объема информации, хранимой для каждого идентификатора (для каждого значения хеш-функции будет расходоваться только память, необходимая для хранения одного указателя на основную таблицу идентификаторов).
На основе этой схемы можно реализовать уже известный способ организации таблиц идентификаторов с помощью хеш-функций, называемый методом цепочек – в таблицу идентификаторов для каждого элемента добавляется еще одно поле, в котором может содержаться ссылка на любой элемент таблицы; первоначально это поле пустое (никуда не указывает); также необходимо иметь специальную переменную, которая всегда указывает на первую свободную ячейку основной таблицы идентификаторов (первоначально она указывает на начало таблицы).
Алгоритм работы метода цепочек.
· Во все ячейки хеш-таблицы поместить пустое значение, таблица идентификаторов — пуста, переменная HeapPtr (указатель первой свободной ячейки) указывает на начало таблицы идентификаторов; i:=1.
· Вычислить значение хеш-функции ni для нового элемента Ai; если ячейка хеш-таблицы по адресу ni — пустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе – к шагу 3.
· j:=1; выбрать из хеш-таблицы адрес ячейки таблицы идентификаторов mj и перейти к шагу 4.
· Для ячейки таблицы идентификаторов по адресу mj проверить значение поля ссылки; если оно пустое, то записать в него адрес из переменной FreePtr и перейти к шагу 5; иначе – j:=j+1, выбрать из поля ссылки адрес mj и повторить шаг 4.
· Добавить в таблицу идентификаторов новую ячейку, записать в нее информацию для элемента Ai (поле ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки; если больше нет идентификаторов, которые надо разместить в таблице, то выполнение алгоритма закончено, иначе – i:=i+1 и перейти к шагу 2.
Алгоритм поиска элемента в таблице идентификаторов.
· Вычислить значение хеш-функции n=h(A) для искомого элемента A; если ячейка хеш-таблицы по адресу n — пустая, то элемент не найден и алгоритм завершен; иначе – j:=1, выбрать из хеш-таблицы адрес ячейки таблицы идентификаторов mj.
· Сравнить имя элемента в ячейке таблицы идентификаторов по адресу mj с именем искомого элемента A: если они совпадают, то искомый элемент найден и алгоритм завершен, иначе перейти к шагу 3.
· Проверить значение поля ссылки в ячейке таблицы идентификаторов по адресу mj: если оно пустое, то искомый элемент не найден и алгоритм завершен; иначе – j:=j+1, выбрать из поля ссылки адрес mj и перейти к шагу 2.
При такой организации таблиц идентификаторов в случае возникновения коллизии алгоритм размещает элементы в ячейках таблицы, связывая их друг с другом последовательно через поле ссылки; элементы не могут попадать в ячейки с адресами, которые потом будут совпадать со значениями хеш-функции. Таким образом, дополнительные коллизии не возникают. В итоге в таблице возникают своеобразные цепочки связанных элементов.
Метод цепочек является эффективным средством организации таблиц идентификаторов.
Достоинства метода цепочек:
· среднее время на размещение одного элемента и на поиск элемента в таблице для него зависит только от среднего числа коллизий, возникающих при вычислении хеш-функции;
· расходы памяти, связанные с необходимостью иметь одно дополнительное поле указателя в таблице идентификаторов на каждый ее элемент, считается оправданными;
· позволяет более экономно использовать память, но требует организации работы с динамическими массивами данных.