Поэтому нельзя организовать таблицу идентификаторов непосредственно на основе одной только хэш-адресации. Но существуют методы, позволяющие использовать хэш-функции для организации таблиц идентификаторов даже при наличии коллизий.
Хэш-адресация с рехэшированием
Для решения проблемы коллизии можно использовать много способов. Одним из них является метод рехэширования (или расстановки). Согласно этому методу, если для элемента А адрес 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