Реферат: Хеш-функции

Как соотносятся методы хеширования с другими стратегиями поиска? Сравнивая их по скорости, можно утверждать, что методы хеширования лучше, если число записей велико, поскольку среднее время поиска для методов хеширования остается ограниченным при N →∞ в случае, когда таблица не становится слишком заполненной. Более того, бинарный поиск годится лишь для фиксированных таблиц, в то время как рассеянные таблицы допускают эффективные процедуры вставки.

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

a) После неудачного поиска в рассеянной таблице мы знаем лишь то, что нужного ключа там нет. Методы поиска, основанные на сравнениях, всегда дают больше информации; они позволяют найти наибольший ключ ≤ K или наименьший ключ ≥ K , что важно во многих приложениях

(например, для интерполяции значений функции по хранящейся таблице).

Эти же методы можно использовать и для нахождения всех ключей, лежащих между двумя заданными величинами K и K'. Далее, алгоритмы поиска по дереву позволяют легко распечатать содержимое таблицы в возрастающем порядке без специальной сортировки, а это иногда бывает нужно.

b) Часто довольно трудно распределить память для рассеянных таблиц; под хеш-таблицу нужно отвести определенную область памяти, а размер ее не всегда ясен. Если отвести слишком много памяти, то такая расточительность отразится на других списках или на других пользователях ЭВМ, но если отвести мало места, таблица переполнится! При переполнении рассеянной таблицы, вероятно, лучше всего "рехешировать" ее, т.е. отвести больше пространства и изменить хеш-функцию, а затем вставить записи в большую таблицу. Ф.~Хопгуд предложил рехешировать таблицу, если коэффициент заполнения достигнет α₀ , заменяя M на d₀ M.

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

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

КАЗАЗСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

им. АЛЬ-ФАРАБИ

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

Поиск.

Хеш-функции.

(курсовая работа)

Выполнил: студент 3 курса

ПМ-97-3А

Амирханов Бауыржан

А е