Выбор хорошей хеш-функции
На практике лучше использовать величину (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), но при этом приведет к эффективной реализации словаря.
Еще по теме Выбор хорошей хеш-функции:
- Чтобы хорошо говорить, учитесь хорошо писать
- Функции журналистики. Понятие функцию Многообразие социальных и информационных потребностей общества – объективная основа функций журналистики.
- Выбор линейного мышления - это выбор прожить жизнь в танце частиц.
- Выбор есть. Он существует всегда. Сознание - это выбор.
- То, что хорошо для одного, не всегда хорошо для другого.
- “Не язык — функция поэта, а поэт — функция языка”
- Хорошо
- Оранжевый: "Хорошо!"
- Оранжевый: "Хорошо!"
- ХОРОШИЕ ИГРЫ
- ХОРОШИЕ ИГРЫ
- Я ХОРОШИЙ Я ЛЮБИМЫЙ