Хеш-функции

Хеш-функции

ХЕШИРОВАНИЕ

До сих пор мы рассматривали методы поиска, основанные на сравнении

данного аргумента K с имеющимися в таблице ключами или на использовании его

цифр для управления процессом разветвления. Но есть и третий путь: не

рыскать вокруг да около, а произвести над K некоторое арифметическое

вычисление и получить функцию f(K), указывающую адрес в таблице, где

хранится K и ассоциированная с ним информация.

К сожалению, находить подобные функции f(K) довольно сложно.

Функции, дающие неповторяющиеся значения, неожиданно редки даже в случае

довольно большой таблицы. Например, знаменитый парадокс дней рождения

утверждает, что, если в комнате присутствует не менее 23 человек, имеется

хороший шанс на то, что у двух из них совпадет день рождения! Иными

словами, если мы выбираем случайную функцию, отображающую 23 ключа в 365-

элементную таблицу, то с вероятностью 0.4927 (менее половины) все ключи

попадут в разные места.

Разумеется, такой метод имеет существенный недостаток, ибо содержимое

таблицы должно быть известно заранее; добавление хотя бы одного ключа может

все испортить, и нам придется начинать фактически на пустом месте.

Можно получить гораздо более гибкий метод, если отбросить идею

однозначности, допуская совпадения значений f(K) для различных

аргументов, и использовать особый метод разрешения неопределенности после

вычисления f(K).

Наши рассмотрения приводят к широко известному классу методов, обычно

называемых хешированием или рассеянной памятью. Английский

глагол "to hash" имеет смысл нарезать, раскрошить что-либо или сделать из

этого месиво; идея хеширования состоит в том, чтобы взять некоторые

характеристики ключа и использовать полученную частичную информацию в

качестве основы поиска. Мы вычисляем хеш-функцию h(K) и берем это значение

в качестве адреса начала поиска.

Парадокс дней рождения служит для нас предостережением, что, вероятно,

найдутся различные ключи Ki ( Kj , для которых h(Ki)=h(Kj). Подобное

событие называется коллизией; для разрешения коллизий были разработаны

интересные подходы. Чтобы использовать рассеянную таблицу, программист

должен принять два почти независимых решения: он должен выбрать хеш-

функцию h(K) и метод разрешения коллизий. Эти два аспекта задачи поиска мы

и рассмотрим по очереди.

Хеш-функции. Для определенности будем полагать, что хеш-функция h(K)

имеет не более M различных значений и, что эти значения удовлетворяют

условию

0( h(K) h(K) вычисляется следующим образом

rX < K

rA < 0 (3)

rA < K mod 1009

Мультипликативную схему хеширования также легко реализовать, но

несколько труднее описать, так как нужно представить, что мы работаем с

дробями, а не с целыми числами. Пусть w есть размер машинного слова; целое

число A можно рассматривать как дробь A/w, если мысленно поставить

десятичную (или двоичную) точку слева от машинного слова, в котором

записано A. Метод состоит в том, чтобы выбрать A взаимно простым с w и

положить

h(K)=[M(((A/w)K) mod 1)]. (4)

В двоичной системе M обычно берут равным степени двойки, так что

h(K) состоит из старших битов правой значащей половины произведения AK. В

двоичном виде при M=2m мультипликативная хеш-функция вычисляется так:

rA ? в случае, когда таблица не

становится слишком заполненной. Более того, бинарный поиск годится лишь для

фиксированных таблиц, в то время как рассеянные таблицы допускают

эффективные процедуры вставки.

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

поиск в рассеянных таблицах все же уступает изученным ранее методам по трем

важным пунктам.

a) После неудачного поиска в рассеянной таблице мы знаем лишь то, что

нужного ключа там нет. Методы поиска, основанные на сравнениях, всегда дают

больше информации; они позволяют найти наибольший ключ ? K или

наименьший ключ ? K , что важно во многих приложениях

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

Эти же методы можно использовать и для нахождения всех ключей,

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

дереву позволяют легко распечатать содержимое таблицы в возрастающем

порядке без специальной сортировки, а это иногда бывает нужно.

b) Часто довольно трудно распределить память для рассеянных таблиц; под хеш-

таблицу нужно отвести определенную область памяти, а размер ее не всегда

ясен. Если отвести слишком много памяти, то такая расточительность

отразится на других списках или на других пользователях ЭВМ, но если

отвести мало места, таблица переполнится! При переполнении рассеянной

таблицы, вероятно, лучше всего "рехешировать" ее, т.е. отвести больше

пространства и изменить хеш-функцию, а затем вставить записи в большую

таблицу. Ф.~Хопгуд предложил рехешировать таблицу, если коэффициент

заполнения достигнет ?0 , заменяя M на d0M.

Алгоритмы поиска со вставкой по дереву не изобилуют тягостными

рехешированиями; деревья растут не больше, чем это необходимо. При работе с

виртуальной памятью нужно, по всей вероятности, использовать поиск по

дереву или цифровой поиск по дереву вместо создания больших рассеянных

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

ключа.

c) Наконец, при использовании методов хеширования нужно свято верить в

теорию вероятностей, ибо они эффективны лишь в среднем, а наихудший случай

просто ужасен! Как и в ситуации с датчиками случайных чисел, мы не можем

быть полностью уверенными в том, что при применении к новому множеству

данных хеш-функция будет работать удовлетворительно. Поэтому рассеянная

память не всегда подходит для работы в реальном масштабе времени, например

для управления движением транспорта, поскольку на карту поставлены

человеческие жизни. Алгоритмы сбалансированного дерева гораздо безопаснее,

ведь они имеют гарантированную верхнюю границу времени поиска.

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

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

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

Поиск.

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

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

Выполнил: студент

3 курса

ПМ-97-3А

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

А е

-----------------------

С2. Список ?

C3.Сравнение

С4. Переход к следующему

С5.Найти сво-

бодный узел.

С6.Вставить

новый ключ

С1. Хеширование