Системное программное обеспечение. Лабораторный практикум - страница 7

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. В целом рехэширование позволяет добиться неплохих результатов для эффективного поиска элемента в таблице (лучших, чем бинарный поиск и бинарное дерево), но эффективность метода сильно зависит от заполненности таблицы идентификаторов и качества используемой хэш-функции – чем реже возникают коллизии, тем выше эффективность метода. Требование неполного заполнения таблицы ведет к неэффективному использованию объема доступной памяти.