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

inline int hashtwo(Key v) { return (V % 97) +1; }

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

На рис. 14.9 показан процесс построения небольшой таблицы методом двойного хеширования; из рис. 14.10 видно, что двойное хеширование приводит к образованию значительно меньшего количества кластеров (которые вследствие этого значительно короче), чем в результате линейного зондирования.

aserchingxmpl 739984 11 7 10 12 086 1315553323542

(D а

s а (Е)

(r) s а Е

r s А(с)Е

r S(h) асе

r s Н а с Е (j)

r s Н а с Е (n) i

r sh aceni©

r(x)s Н а с Е n i g

®rxsh acen1g

м r x s Н (р)А с Е n i о м r x s Нфр а се n i g

01 23456789 10 11 12

РИСУНОК 14.9 ДВОЙНОЕ ХЕШИРОВАНИЕ

На этой диаграмме показан процесс вставки ключей А S Е R С НIN G ХМРL в первоначально пустую хеш-таблицу с открытой адресацией с использованием хеш-значений, приведенных вверху, и разрешением конфликтов за счет применения двойного хеширования. Первое и второе хеш-значения каждого ключа отображаются в двух строках под этим ключом. Как и на рис. 14.7, зондируемые позиции таблицы не затенены. А помещается в позицию 7, затем S - в позицию 3, Е - в позицию 9, как и на рис. 14.7, но ключ R помещается в позицию 1 после возникновения конфликта в позиции 9, причем второе хеш-значение этого ключа, равное 5, используется в качестве шага зондирования после возникновения конфликта. Аналогично, ключ Р помещается в позицию 6 при заключительной вставке после возникновения конфликтов в позициях 8, 12, 3, 7, 11 и 2 при использовании его второго хеш-значения, равного 4, как шага зондирования.

Лемма 14.4 При разрешении конфликтов с помощью двойного хеширования среднее количество зондирований, необходимых для выполнения поиска в хеш-таблице размером М, содержащей N = аМ ключей, равно

для обнаружения попаданий и промахов, соответственно.

Эти формулы - результат глубокого математического анализа, выполненного Гю-иба (Guibas) и Шемереди (Szemeredi) {см. раздел ссылок). Доказательство основывается на том, что двойное хеширование почти эквивалентно более сложному алгоритму случайного хеширования, при котором используется зависящая от ключей последовательность позиций зондирования, обеспечиваюшая равную вероятность попадания каждого зондирования в каждую позицию таблицы. По многим причинам этот алгоритм - всего лишь аппроксимация двойного хеширования: например, очень трудно гарантировать, чтобы при двойном хешировании каждая позиция таблицы проверялась хотя бы один раз, но при случайном хешировании одна и та же позиция таблицы может проверяться более одного раза. Тем не менее, для разреженных таблиц вероятность возникновения конфликтов при использовании обоих методов одинакова. Интерес представляют оба метода: двойное хеширование легко реализовать, в то время как случайное хеширование легко анализировать.

№. .J. т.шЫЛ, .Id! Л mm

IJ Л.

РИСУНОК 14.10 КЛАСТЕРИЗАЦИЯ

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

Средние затраты на обнаружение промаха при поиске для случайного хеширования определяются равенством

1 + - + М

\-{N/M) 1-а

Выражение слева - сумма вероятностей использования для обнаружения промахов более к зондирований, при к = О, 1,2, ... (которая на основании элементарной теории вероятностей равна средней вероятности). При поиске всегда используется одно зондирование, затем с вероятностью {N/Mf требуется второе зондирование и т.д. Эту же формулу можно использовать для вычисления следующего приближенного значения средней стоимости попадания при поиске в таблице, содержащей ключей:

\-{\/М) \-{2/М)

\-{{N-\)/M)

Вероятность попадания одинакова для всех ключей в таблице; затраты на отыскание ключа равны затратам на его вставку, а затраты на вставку у-го ключа в таблицу равны затратам на обнаружение промаха в таблице, содержащей j - 1 ключ, следовательно, эта формула определяет среднее значение этих затрат. Теперь можно упростить и вычислить эту сумму, умножив числители и знаменатели всех дробей на М:

] N

м-\ м-1

M-N + \

и выполнив дальнейшее упрощение, получаем

---(Я -Я )==-1п

поскольку Им ~ \пМ.

Точная взаимосвязь между производительностью двойного хеширования и идеальным случаем случайного хеширования, которая была установлена Гюиба и Шемереди - асимптотический результат, который не обязательно должен быть справедлив для используемых на практике размеров таблиц; более того, полученные результаты основываются на предположении, что хеш-функции возвращают случайные значения. Тем не менее, асимптотические формулы, приведенные в лемме 14.5, на практике достаточно точно определяют производительность двойного хеширования, даже при использовании такой просто вычисляемой второй хеш-функции, как (v % 97)+1. Как и в случае соответствующих формул для линейного зондирования, эти формулы стремятся к бесконечности при приближении значения а к 1, но это происходит значительно медленнее.

Различие между линейным зондированием и двойным хешированием наглядно иллюстрируется на рис. 14.11. Двойное хеширование и линейное зондирование имеют одинаковую производительность для разреженных таблиц, но при использовании