Тогда поиск элемента А в таблице идентификаторов, организованной таким образом, будет выполняться по следующему алгоритму:
1. Вычислить значение хэш-функции n = h(A) для искомого элемента А.
2. Если ячейка по адресу п пустая, то элемент не найден, алгоритм завершен, иначе необходимо сравнить имя элемента в ячейке n с именем искомого элемента A. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= 1 и перейти к шагу 3.
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).
Этот способ нельзя признать особенно удачным: при совпадении хэш-адресов элементы в таблице начинают группироваться вокруг них, что увеличивает число необходимых сравнений при поиске и размещении. Но даже такой примитивный метод рехэширования является достаточно эффективным средством организации таблиц идентификаторов при неполном заполнении таблицы.
Среднее время на помещение одного элемента в таблицу и на поиск