<<
>>

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

Итак, эффективность словаря зависит от выбора хеш-функции h. Как правило, мы будем рассматривать U как большое множество чисел, а затем применять легко вычислимую функцию h, которая отображает каждое число u U на некоторое значение из меньшего целочисленного диапазона {0, 1, ..., n - 1}.
Это можно сделать многими простыми способами: например, использовать несколько первых или последних цифр u или просто вычислить остаток от деления u на n. Хотя эти про- стые решения хорошо работают во многих ситуациях, они также могут привести к многочисленным коллизиям. В самом деле, фиксированный выбор хеш-функции может создать проблемы из-за особенностей элементов u в приложении: может быть, в конкретных цифрах, используемых в определении хеш-функции, кодиру- ется некоторое свойство u, поэтому количество возможных вариантов невелико. Вычисление остатка от деления u на n может привести к аналогичной проблеме, особенно если n является степенью 2. Рассмотрим конкретный пример: допустим, хеш-функция берет абзац английского текста, использует стандартную кодиров- ку символов (например, ASCII) для преобразования его в последовательность битов, а затем оставляет только несколько начальных битов этой последователь- ности.
Можно предполагать большое количество коллизий в элементах массивов, соответствующих битовым строкам для кодирования часто встречающихся слов (например, «The»), тогда как большие части массива могут быть заняты только аб- зацами, начинающимися со строк вида «qxf», а следовательно, останутся пустыми.

На практике лучше использовать величину (u mod р) для простого числа р, близкого к 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), но при этом приведет к эффективной реализации словаря.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Выбор хорошей хеш-функции:

  1. Чтобы хорошо говорить, учитесь хорошо писать
  2. Функции журналистики. Понятие функцию Многообразие социальных и информационных потребностей общества – объективная основа функций журналистики.
  3. Выбор линейного мышления - это выбор прожить жизнь в танце частиц.
  4. Выбор есть. Он существует всегда. Сознание - это выбор.
  5. То, что хорошо для одного, не всегда хорошо для другого.
  6. “Не язык — функция поэта, а поэт — функция языка”
  7. Хорошо
  8. Оранжевый: "Хорошо!"
  9. Оранжевый: "Хорошо!"
  10. ХОРОШИЕ ИГРЫ
  11. ХОРОШИЕ ИГРЫ
  12. Я ХОРОШИЙ Я ЛЮБИМЫЙ