Выбор хорошей хеш-функции

Итак, эффективность словаря зависит от выбора хеш-функции h. Как правило, мы будем рассматривать U как большое множество чисел, а затем применять легко вычислимую функцию h, которая отображает каждое число u Ѯ U на некоторое значение из меньшего целочисленного диапазона {0, 1, …, n − 1}.

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

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

Можно предполагать большое количество коллизий в элементах массивов, соответствующих битовым строкам для кодирования часто встречающихся слов (например, «The»), тогда как большие части массива могут быть заняты только абзацами, начинающимися со строк вида «qxf», а следовательно, останутся пустыми.

На практике лучше использовать величину (u mod p) для простого числа p, близкого к n. Хотя в некоторых случаях этот метод порождает хорошие хеш- функции, он не универсален, а некоторые простые числа работают намного лучше других (например, простые числа, очень близкие к степеням 2, работают не так хорошо).

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

Основная идея, как говорилось ранее, заключается в использовании рандомизации при построении h. Начнем с крайнего случая: для каждого элемента u Ѯ U при вставке в S значение h(u) выбирается случайно с равномерным распределением из множества {0,1, …, n − 1}, независимо от всех предшествующих вариантов выбора. В этом случае вероятность того, что два случайно выбранных значения h(u) и h(v) совпадут (а следовательно, вызовут коллизию), достаточно мала.

(13.22) В схеме случайного равномерного хеширования вероятность того, что два случайно выбранных значения h(u) и h(v) образуют конфликт (то есть h(u) = h(v)), равна точно 1/n.

Доказательство. Все n2 возможных вариантов выбора пар (h(u), h(v)) имеют одинаковую вероятность, и ровно n из этих вариантов приводят к коллизии. 

Тем не менее использовать хеш-функцию с независимыми случайными равномерными значениями не получится. Чтобы понять почему, предположим, что элемент u вставляется в S, а потом потребовалось выполнить операцию Delete(u) или Lookup(u).

Спрашивается, где его искать? Нужно знать случайное значение h(u), использованное при вставке, поэтому значение h(u) необходимо где-то сохранить для быстрой выборки. Но ведь это именно та задача, которую мы пытались изначально решить!

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

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