.

Хеш-функции

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 1721
Скачать документ

ХЕШИРОВАНИЕ

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

аргумента 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 ?K.

rAX ?AK.

rAX ? AK mod w.

Сдвиг rAX на m битов влево.

Результат получается в регистре A.

Одна из привлекательных черт мультипликативной схемы состоит в том, что

в (5) не происходит потери информации; мы могли бы вновь найти K, зная

лишь содержимое rAX после выполнения инструкций (5). Дело в том, что

A взаимно просто с w, и при помощи алгоритма Евклида можно найти

Константу A’: AA’ mod w = 1 ; отсюда следует, что K=(A'(AK mod w)) mod
w. Иными словами,

K1 ? K2 влечет f(K1 ) ? f(K2 ). (6)

Конечно, f(K)принимает значения в диапазоне от 0 до w-1 и не является

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

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

Хорошая хеш-функция должна удовлетворять двум требованиям:

a)ее вычисление должно быть очень быстрым;

b)она должна минимизировать число коллизий.

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

До сих пор мы рассматривали хеширование ключей, состоящих из одного

слова. С ключами, состоящими из нескольких слов или имеющими переменную

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

можно использовать сложение по модулю w или операцию “исключающее или”

(на двоичных ЭВМ). Достоинством обеих операций является их обратимость,

т.е. их результат зависит от всех битов аргументов, причем “исключающее

или” иногда предпочтительнее, так как не может привести к

арифметическому переполнению. Заметим, что обе операции коммутативны,

поэтому ключи (X, Y) и (Y, X) будут “брошены” по одному адресу. Чтобы

избежать этого, Г.Д. Кнотт предложил предварительно делать циклический
сдвиг.

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

является способ, основанный на алгебраической теории кодирования. Идея

аналогична методу деления, только вместо деления на целое число

используется деление на многочлен по модулю 2. Для предлагаемого метода
M должно

быть степенью 2: M=2m ; кроме того, используется многочлен

m-й степени P(x)=xm + pm-1 xm-1 + … + p0. Двоичный ключ K=(kn-1 … k1 k0
)2 можно рассматривать как многочлен K(x)=kn-1 xn-1+…+ k1x+ k0, и
вычислить

остаток

K(x) mod P(x) = hm-1 xm-1+…+ k1 x+ k0,

используя полиномиальную арифметику по модулю 2: h(K)=( hm-1… h1 h0)2.
При правильном выборе P(x) такая хеш-функция позволяет избежать
коллизий, между почти равными ключами.

Разрешение коллизий методом цепочек. Мы уже говорили,

что некоторые адреса могут порождаться несколькими ключами. Пожалуй,

наиболее очевидный способ решения проблемы состоит в том, чтобы

поддерживать M связанных списков, по одному на каждый возможный

хеш-адрес. Все записи должны содержать поля LINK; кроме того, нужно

иметь M головных узлов списков HEAD[i], где i меняется от 1

до M . После хеширования

HEAD[1]: [__] [ TO ][ ] [ FIRE ][ ? ]

HEAD[2]: [__] [ SYV ][ ? ]

HEAD[3]: [__] [ EN ][ ? ]

HEAD[4]: [__] [ TRE ][ ? ]

HEAD[5]: [__] [ FEM ][ ? ]

HEAD[6]: [_?_]

HEAD[7]: [_?_]

HEAD[8]: [_? ]

HEAD[9]: [__] [ SEKS ][ ? ]

Рис. Раздельные цепочки.

ключа мы просто выполняем последовательный поиск в списке с

номером h(K)+1.

Рисунок иллюстрирует этот простой метод цепочек при M=9 для

последовательности семи ключей

K=|EN|, |TO|, |TRE|, |FIRE|, |FEM|, |SEKS|, |SYV|

(так называются числа от~1 до~7 по-норвежски), имеющих соответственные

хеш-коды

h(K)+1 = 3, 1, 4, 1, 5, 9, 2.

Первый список содержит два элемента, три списка пусты.

Метод цепочек является весьма быстрым, поскольку списки коротки. Если в

одной комнате собрать 365~человек, то найдется много пар, имеющих один

и тот же день рождения, но данный день рождения в среднем имеет лишь
один

человек! Вообще, если имеется N ключей и M списков, средний

размер списка равен N/M; таким образом, хеширование уменьшает количество

работы, требуемое на последовательный поиск, примерно в M раз.

В целях экономии времени желательны большие M , но в этом случае многие

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

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

напрашивается другой подход: можно наложить пространство для записей на

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

M записей и M ссылок, а не под N записей и M+N ссылок.

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

узлы будут использоваться, вставляя на следующем проходе “переполняющие”

записи в свободные щели. Часто, однако, это нежелательно или невозможно;

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

лишь один раз, при первом поступлении в систему. Следующий алгоритм,

принадлежащий Ф.~Уильямсу,является общепринятым способом решения этой
задачи.

alg C.(Поиск с вставкой по рассеянной таблице с цепочками.) Предлагаемый

алгоритм позволяет отыскать в таблице из M элементов данный ключ K.

Если K нет в таблице и она не полна, K вставляется в нее.

Элементы таблицы обозначаются через TABLE[i], 0?i? M, и могут

быть двух различных типов: свободный и занятый. Занятый узел

содержит ключевое поле KEY[i], поле ссылки LINK[i] и, возможно,

другие поля.

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

пространства используется вспомогательная переменная R; если таблица

пуста, R=M+1; по мере проведения вставок будет оставаться в силе

утверждение, что узлы TABLE|[j] заняты для всех j в диапазоне R?j?M.

Условимся, что узел TABLE[0] всегда будет свободен.

C1.[Хеширование.] Установить i?h(K)+1. (Теперь 1?i?M.)

C2.[Список?] Если узел TABLE[i] свободен, то перейти на C6.

(В противном случае этот узел занят, и мы последуем на имеющийся здесь

список занятых узлов).

C3.[Сравнение.] Если K=KEY[i], поиск завершен удачно.

C4.[Переход к следующему.] Если LINK[i]?0, установить i?LINK[i] и
вернуться на

C3.

C5.[Найти свободный узел.] (Поиск был неудачным, и мы хотим найти в

таблице свободное место.) Уменьшать R до тех пор, пока не будет
получено

такое значение, что узел TABLE[R] свободен. Если R=0, алгоритм

заканчивается по переполнению (свободных узлов больше нет); в противном

случае установить LINK[i]?R, i?R.

C6.[Вставить новый ключ.] Пометить TABLE[i] как занятый узел

С KEY[i]?K и LINK[i]?0.

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

вставки в таблицу записи перемещать не нужно.

C1.Хеширование

Нет

Да

K=KEY[i] R=0

УДАЧА ПЕРЕПОЛНЕНИЕ

Рис. Поиск с вставкой по рассеянной таблице с цепочками.

TABLE[1]: [ TO ][ ]

TABLE[2]: [ SYV ][ ? ]

TABLE[3]: [ EN ][ ? ]

TABLE[4]: [ TRE ][ ? ]

TABLE[5]: [ FEM ][ ? ]

TABLE[6]: [_ ? _]

TABLE[7]: [_ ? _]

TABLE[8]: [ SEKS ][ ? ]

TABLE[9]: [ FIRE ][ ]

рис. Сросшиеся списки.

На первый взгляд шаг C5 может показаться неэффективным, так как в нем

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

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

шаге C5 не превышает количества элементов в таблице; значит, в среднем
на

каждую вставку тратится не более одной такой пробы!

Разрешение коллизий “открытой адресацией”. Другой способ решения

проблемы коллизий состоит в том, чтобы полностью отказаться от ссылок и

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

будут найдены ключ K или свободная позиция. Не плохо было бы иметь

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

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

просматривать всякий раз при вставке или поиске K. Если мы, используя

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

то можно сделать вывод, что K нет в таблице, так как та же

последовательность проб выполняется каждый раз при обработке данного
ключа.

Этот общий класс методов У. Петерсон назвал открытой

адресацией.

Простейшая схема открытой адресации, известная как линейное

опробование, использует циклическую последовательность

h(K), h(K)-1,…, 0, M-1, M-2,…, h(K)+1 (*)

и описывается следующим образом.

alg L.(Поиск с вставкой по открытой рассеянной таблице.)

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

Если K нет в таблице и она не полна, ключ K вставляется.

Узлы таблицы обозначаются через TABLE[i], 0?i0$.\cr

}

\eqno(25)

$$

Этот метод быстрее повторного деления, но он все же приводит к

\emph{вторичному окучиванию,} требуя несколько больше проб из-за

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

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

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

%% 621

Алгоритмы~L и~D очень похожи, но имеют и достаточно различий, поэтому

полезно сравнить времена работы соответствующих программ для~\MIX.

\prog D.(Открытая адресация с двойным хешированием.)

Так как эта программа весьма напоминает программу~L, она приводится без

комментариев. Здесь~$|rI2|\equiv c-1$.

\code

START&LDX &K &1

&ENTA&0 &1

&DIV &=M= &1

&STX &*+1(0:2) &1

&ENT1&* &1

&LDX &TABLE,1 &1

&СМРХ&K &1

&JE &SUCCESS &1

&JXZ &4F &1-S1

&SRAX&5 &A-S1

&DIV &=M-2= &A-S1

&STX &*+1(0:2) &A-S1

&ENT2&* &A-S1

&LDA &K &A-S1

3H &DEC1&1,2 &C-1

&J1NN&*+2 &C-1

&INC1&M &B

&CMPA&TABLE,1 &C-1

&JE &SUCCESS &C-1

&LDX &TABLE,1 &C-1-S2

&JXNZ&3B &C-1-S2

4H &LDX &VACANCIES&1-S

&JXZ &OVERFLOW &1-S

&DECX&1 &1-S

&STX &VACANCIES&1-S

&LDA &K &1-S

&ST?????†???????????

Счетчики частот~$A$, $C$, $S1$, $S2$ имеют тот же смысл, что и

в программе~C. Среднее значение переменной~$B$ примерно равно~$(C-1)/2$.

(Если сузить диапазон~$h_2(K)$, скажем,

до~$1\le h_2(K)\le {1\over2} M$,

значение~$B$ составило бы лишь~$(C-1)/4$, вероятно, увеличение числа
проб

не сведет на нет это увеличение скорости.) Если в таблице $N=\alpha
M$~ключей,

среднее значение~$A$, разумеется, равно~$\alpha$ для неудачного

поиска и~1 для удачного. Как и в алгоритме~C, среднее значение~$S1$ для

неудачного поиска составляет~$1-{1\over2}((N-1)/M)\approx

1-{1\over2}\alpha$. Трудно точно определить среднее число проб, однако

эмпирические проверки показывают хорошее согласие с выведенными ниже

формулами для “равномерного опробования”:

$$

\eqalignno{

C’_N&={M+1\over M+1-N}\approx(1-\alpha)^{-1} \rem{(неудачный
поиск)};&(26)\cr

C_N&={M+1\over N}(H_{M+1}-H_{M+1-N}) \approx-\alpha^{-1}\ln (1-\alpha)

\rem{(удачный поиск)},&(27)\cr

}

$$

если~$h_1(K)$ и~$h_2(K)$ независимы. Когда же $h_2(K)$~зависит
от~$h_1(K)$,

как в~(25), вторичное окучивание вызывает увеличение средних

%%622

значений до

$$

\eqalignno{

C’_N &={M+1\over M+1-N}-{N\over
M+1}+H_{M+1}-H_{M+1-N}+O(M)^{-1}\approx\cr

&\approx(1-\alpha)^{-1}-\alpha-\ln(1-\alpha);&(28)\cr

C_N&=1+H_{M+1}-H_{M+1-N}-{N\over 2(M+1)}

-(H_{M+1}-H_{M+1-N})/N+O(N^{-1})\approx\cr

&\approx 1-\ln(1-\alpha)-{1\over2}\alpha. &(29) \cr

}

$$

(См.~упр.~44.) Заметим, что, когда таблица заполняется, т.~е.~когда $N

$~стремится к~$M$, значение~$C_N$ приближается к~$H_{M+1}-1$,

а~$C’_N$—к~$H_{M+1}-{1\over2}$; это много лучше, чем в случае
алгоритма~L,

но не столь хорошо, как в методах цепочек.

Поскольку в алгоритме~L пробы занимают несколько меньше времени, двойное

хеширование предпочтительно лишь при заполненной таблице. На рис.~42

сравниваются средние времена работы программ~L, D и модифицированной

программы~D (причем эта модификация влечет за собой вторичное
скучивание):

мы заменяем довольно медленное вычисление~$h_2(K)$ в строках~10–13 на
три

команды

$$

\mixcode

ENN2 & -M-1, 1 & $c\asg M-i$.

J1NZ & *+2

ENT2 & 0 & Если $i=0$, $c\asg 1$.

\endmixcode

\eqno(30)

$$

\picture{Рис. 42. Время удачного поиска для трех схем открытой
адресации.}

%%623

В данном случае вторичное скучивание лучше независимого повторного
хеширования.

На двоичной ЭВМ мы могли бы иным способом ускорить вычисление~$h_2(K)$,

заменив строки~10–13, скажем, на

$$

\mixcode

AND & =511= & $|rA|\asg |rA| \bmod 512$.

STA & *+1(0:2)

ENT2 & * & $c\asg |rA|+1$.

\endmixcode

\eqno(31)

$$

если $M$—простое число, большее~512. Эта идея, предложенная Беллом и

Кам\’а [{\sl CACM,\/} {\bf 13} (1970), 675–677], независимо
придумавшими

алгоритм~D, позволяет избежать вторичного скучивания без затрат на

повторное деление.

Было предложено много других последовательностей проб в качестве
улучшений

алгоритма~L, но, по-видимому, ни одна из них не лучше алгоритма~D. (Быть

может, исключение составляет метод, описанный в упр.~20.)

\picture{ Рис. 43. Сколько раз компилятор ищет имена переменных в
типичном

случае. Имена выписаны слева направо в порядке их первого появления.}

\section Изменение, предложенное Брентом. Ричард Брент нашел такой
способ

изменения алгоритма~D, чтобы среднее время удачного поиска оставалось

ограниченным по мере заполнения таблицы. Его метод основан на том факте,

что во многих приложениях

%%624

удачный поиск производится гораздо чаще вставок; поэтому он предлагает

делать больше работы при вставке элемента, nepeмещая записи, чтобы

уменьшить ожидаемое время выборки.

[{\sl CACM,\/} {\bf 16} (1973), 105–109.]

Например, на рис.~43 показано, сколько раз тот или иной идентификатор

встречался в типичной процедуре на~PL/1. Судя по этим данным, компилятор

с~PL/1, использующий рассеянную таблицу для хранения имен переменных,

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

Аналогично Белл и~Кам\’а обнаружили, что компилятор с~Кобола
использовал

свой алгоритм таблиц символов $10988$~раз во время компиляции программы
и

совершил лишь $735$~вставок, т.~е.~на один неудачный поиск приходилось

примерно 14~удачных.

Иногда таблица создается только один раз (например, таблица
символических

кодов операций в автокоде) и используется после этого исключительно для

выборки.

Брент предложил следующим образом изменить процесс вставки в
алгоритме~D.

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

$$

p_0, p_1,~\ldots, p_{t-1}, p_t,

$$

где~$p_j=(h_1(K)-jh_2(K))\bmod M$ и узел~$|TABLE|[p_t]$ пуст. Если~$t\le

1$, мы, как обычно, вставляем~$K$ в позицию~$p_t$, но если~$t\ge2$,

вычисляем~$c_0=h_2(K_0)$, где~$K_0=|KEY|[p_0]$, и смотрим, свободно ли

в~$|TABLE| [(p_0-c_0)\bmod M$]. Если условие выполнено, помещаем в
данный

узел содержимое ячейки~$|TABLE|[p_0]$ и вставляем~$K$ в позицию~$p_0$.
Это

увеличивает время выборки $K_0$ на один шаг, но уменьшает время

выборки~$K$ на $t\ge2$~шагов. Выигрыш налицо. Аналогично, если

в~$|TABLE|[(p_0-c_0)\bmod M]$ занято и~$t\ge3$, мы пробуем
ячейку~$|TABLE|

[(p_0-2c_0)\bmod M]$;

если и там занято, вычисляем~$c_1=h_2(|KEY|[p_1])$ и пробуем

$|TABLE|[(p_1-c_1)\bmod M]$ и~т.~д. Вообще,

пусть~$c_j=h_2(|KEY|[p_j])$ и~$p_{j,k}=(p_j-kc_j)\bmod M$; если

позиции~$|TABLE|[p_{j,k}]$ оказались занятыми при всех~$j, k$, таких,

что~$j+k (M+1)/(M+1-n)$;

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

В действительности в качестве меры лучше подходит не~$C’_N$, а число
проб

при \emph{удачном} поиске~$C_N$. Перестановки~(52) не дают
улучшения~$C_N$

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

приписывание перестановкам вероятностей не может сделать~$C_N$ меньше

“равномерного” значения~$((M+1)/N) (H_{M+1}-H_{M+1-N})$.

Как оказывается, это утверждение очень трудно доказать главным образом

потому, что получить эффект равномерного хеширования можно многими

способами; мы не обязаны приписывать каждой перестановке
вероятность~$1/M!$.

Например, следующее распределение при~$M=4$ эквивалентно равномерному
хешированию:

$$

\matrix{

\hbox{Перестановка} & \hbox{Вероятность} & \hbox{Перестановка} &
\hbox{Вероятность}\cr

0\ 1\ 2\ 3 & 1/6 &0\ 2\ 1\ 3 & 1/12\cr

1\ 2\ 3\ 0 & 1/6 &1\ 3\ 2\ 0 & 1/12\cr

2\ 3\ 0\ 1 & 1/6 &2\ 0\ 3\ 1 & 1/12\cr

}

\eqno(53)

$$

(остальным 16~перестановкам приписывается нулевая вероятность).

Следующая теорема характеризует \emph{все} распределения вероятностей,

которые дают поведение равномерного хеширования:

\proclaim Теорема~U. Приписывание перестановкам вероятностей сделает все

$\perm{M}{N}$~конфигураций занятых и свободных ячеек после N~вставок

равновероятными для~$0

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020