Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

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

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

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

Для решения проблемы коллизии можно использовать много способов. Одним из них является метод рехэширования (или расстановки). Согласно этому методу, если для элемента А адрес n 0= h(A), вычисленный с помощью хэш-функции h, указывает на уже занятую ячейку, то необходимо вычислить значение функции n 1= h 1(A) и проверить занятость ячейки по адресу п 1. Если и она занята, то вычисляется значение h 2(A), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение h i(А) не совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет – выдается информация об ошибке размещения идентификатора в таблице.

Тогда поиск элемента А в таблице идентификаторов, организованной таким образом, будет выполняться по следующему алгоритму:

1. Вычислить значение хэш-функции n = h(A) для искомого элемента А.

2. Если ячейка по адресу п пустая, то элемент не найден, алгоритм завершен, иначе необходимо сравнить имя элемента в ячейке n с именем искомого элемента A. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= 1 и перейти к шагу 3.

3. Вычислить n i= h i(A). Если ячейка по адресу n iпустая или n = n i, то элемент не найден и алгоритм завершен, иначе – сравнить имя элемента в ячейке n iс именем искомого элемента A. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= i + 1 и повторить шаг 3.

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

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

Для организации таблицы идентификаторов по методу рехэширования необходимо определить все хэш-функции h iдля всех i. Чаще всего функции h iопределяют как некоторые модификации хэш-функции h. Например, самым простым методом вычисления функции h i(A) является ее организация в виде h i(A) = (h(A) + p i) mod N m, где p i– некоторое вычисляемое целое число, а N m– максимальное значение из области значений хэш-функции h. В свою очередь, самым простым подходом здесь будет положить p i= i. Тогда получаем формулу h i(A) = (h(A) + i) mod N m. В этом случае при совпадении значений хэш-функции для каких-либо элементов поиск свободной ячейки в таблице начинается последовательно от текущей позиции, заданной хэш-функцией h(A).

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

Среднее время на помещение одного элемента в таблицу и на поиск элемента в таблице можно снизить, если применить более совершенный метод рехэширования. Одним из таких методов является использование в качестве p iдля функции h i(A) = (h(A) + p i) mod N mпоследовательности псевдослучайных целых чисел p 1, p 2, …, p k. При хорошем выборе генератора псевдослучайных чисел длина последовательности k = N m.

Существуют и другие методы организации функций рехэширования h i(A), основанные на квадратичных вычислениях или, например, на вычислении произведения по формуле: h i(A) = (h(A)N·i) mod N' m, где N' m– ближайшее простое число, меньшее N m. В целом рехэширование позволяет добиться неплохих результатов для эффективного поиска элемента в таблице (лучших, чем бинарный поиск и бинарное дерево), но эффективность метода сильно зависит от заполненности таблицы идентификаторов и качества используемой хэш-функции – чем реже возникают коллизии, тем выше эффективность метода. Требование неполного заполнения таблицы ведет к неэффективному использованию объема доступной памяти.

Оценки времени размещения и поиска элемента в таблицах идентификаторов при использовании различных методов рехэширования можно найти в [1, 3, 7].

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