Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
Хэширование 5.1. Введение .......................... 256 5.2. Выбор хэш<функции ......... 257 5.3. Разрешение коллизий ...... 257 5.4. Анализ хэширования ........ 261 Упражнения ............................. 263 Литература .............................. 263 Хэширование 256 5.1. Введение В главе 4 подробно обсуждалась следующая основная проблема: если задан набор элементов, характеризующихся ключом (который определяет отношение поряд% ка), то как организовать этот набор, чтобы извлечение элемента с заданным клю% чом требовало наименьших усилий? Ясно, что в конечном счете доступ к каждому элементу в памяти компьютера осуществляется указанием его адреса в памяти. Поэтому вышеуказанная проблема по сути сводится к нахождению подходящего отображения H ключей ( K ) в адреса ( A ): H: K → A В главе 4 это отображение реализовывалось с помощью различных алгоритмов поиска в списках и деревьях на основе разных способов организации данных. Здесь мы опишем еще один подход, простой по сути и во многих случаях очень эффективный. Затем мы обсудим и некоторые его недостатки. В этом методе данные организуются с помощью массива. Поэтому H является отображением, преобразующим ключи в индексы массива, откуда и происходит название преобразование ключей, нередко используемое для этого метода. Заме% тим, что здесь нам не понадобятся процедуры динамического размещения; массив является одной из фундаментальных, статических структур. Метод преобра% зования ключей часто используют в тех задачах, где с примерно равным успехом можно применить и деревья. Фундаментальная трудность при использовании преобразования ключей заключается в том, что множество возможных значений ключей гораздо больше, чем множество доступных адресов в памяти (индексов массива). К примеру, возьмем имена длиной до 16 букв в качестве ключей, идентифицирующих отдель% ных людей во множестве из тысячи человек. Здесь есть 26 16 возможных значений ключей, которые нужно отобразить на 10 3 возможных индексов. Очевидно, что функция H отображает несколько значений аргументов в одно значение индекса. Если задан ключ k , то первый шаг операции поиска состоит в вычислении соот% ветствующего индекса h = H(k) , а второй – очевидно, обязательный – шаг состоит в проверке того, действительно ли элемент с ключом k соответствует элементу массива (таблицы) T с индексом h , то есть выполняется ли равенство T[H(k)].key = k Мы сразу сталкиваемся с двумя вопросами: 1. Какую функцию H надо взять? 2. Что делать, если H не смогла вычислить адрес искомого элемента? Ответ на второй вопрос состоит в том, чтобы использовать метод, который даст альтернативную позицию, скажем индекс h' , и если там по%прежнему нет иско% мого элемента, то третий индекс h" , и т. д. (Такие попытки обозначаются ниже как пробы (probe) – прим. перев.) Ситуацию, когда в вычисленной позиции находится элемент, отличный от искомого, называют коллизией; задача порождения альтер% нативных индексов называется разрешением коллизий. Далее мы обсудим выбор функции преобразования ключей и методы разрешения коллизий. 257 5.2. Выбор хэшGфункции Хорошая функция преобразования ключей должна обеспечивать как можно бо% лее равномерное распределение ключей по всему диапазону значений индекса. Других ограничений на распределение нет, но на самом деле желательно, чтобы оно казалось совершенно случайным. Это свойство дало методу несколько нена% учное название хэширование (hashing от англ. «превращать в фарш» и «мешани% на» – прим. перев.). H называется хэш функцией. Очевидно, эта функция должна допускать эффективное вычисление, то есть состоять из очень небольшого числа основных арифметических операций. Предположим, что имеется функция преобразования ORD(k) , которая вычис% ляет порядковый номер ключа k во множестве всех возможных ключей. Кроме того, предположим, что индекс массива i принимает значения в диапазоне целых чисел 0 .. N–1 , где N – размер массива. Тогда есть очевидный вариант: H(k) = ORD(k) MOD N Такой выбор обеспечивает равномерное распределение ключей по диапазону индексов и поэтому является основой большинства хэш%функций. Это выраже% ние очень быстро вычисляется, если N есть степень 2, но именно этого случая сле% дует избегать, если ключи являются последовательностями букв. Предположе% ние, что все ключи равно вероятны, в этом случае неверно, и на самом деле слова, отличающиеся лишь немногими буквами, будут с большой вероятностью отобра% жаться на одно и то же значение индекса, так что получится весьма неоднородное распределение. Поэтому особенно рекомендуется в качестве значения N выбирать простое число [5.2]. Как следствие придется использовать полную операцию де% ления, которую нельзя заменить простым отбрасыванием двоичных цифр, но это не является проблемой на большинстве современных компьютеров, имеющих встроенную инструкцию деления. Часто используют хэш%функции, состоящие в применении логических опера% ций, таких как исключающее «или», к некоторым частям ключа, представленного как последовательность двоичных цифр. На некоторых компьютерах эти опера% ции могут выполняться быстрее, чем деление, но иногда они приводят к удиви% тельно неоднородному распределению ключей по диапазону индексов. Поэтому мы воздержимся от дальнейшего обсуждения таких методов. 5.3. Разрешение коллизий Если оказывается, что элемент таблицы, соответствующий данному ключу, не яв% ляется искомым элементом, то имеет место коллизия, то есть у двух элементов ключи отображаются на одно значение индекса. Тогда нужна вторая проба с неко% торым значением индекса, полученным из данного ключа детерминированным способом. Есть несколько способов порождения вторичных индексов. Очевидный способ – связать все элементы с одинаковым первичным индексом H(k) в связный список. Это называют прямым связыванием (direct chaining). Элементы этого списка могут находиться в первичной таблице или вне ее; во втором случае об% Разрешение коллизий Хэширование 258 ласть памяти, где они размещаются, называется областью переполнения (overflow area). Недостатки этого метода – необходимость поддерживать вторичные спис% ки, а также что каждый элемент таблицы должен содержать указатель (или ин% декс) на список конфликтующих элементов. Альтернативный способ разрешения коллизий состоит в том, чтобы вообще отказаться от списков и просто перебирать другие элементы в той же таблице, пока не будет найден искомый элемент либо пустая позиция, что означает отсут% ствие указанного ключа в таблице. Такой метод называется открытой адресацией (open addressing [5.3]). Естественно, последовательность индексов во вторичных попытках должна быть всегда одной и той же для заданного ключа. Тогда алго% ритм поиска в таблице может быть кратко описан следующим образом: h := H(k); i := 0; REPEAT IF T[h].key = k THEN ELSIF T[h].key = free THEN ELSE (* *) i := i+1; h := H(k) + G(i) END UNTIL ( ) В литературе предлагались разные функции для разрешения коллизий. Обзор темы, сделанный Моррисом в 1968 г. [4.8], вызвал значительную активность в этой области. Простейший метод – проверить соседнюю позицию (считая таблицу циклической), пока не будет найден либо элемент с указанным ключом, либо пустая позиция. Таким образом, G(i) = i ; в этом случае индексы h i , исполь% зуемые для поиска, даются выражениями h 0 = H(k) h i = (h i–1 + i) MOD N,i = 1 ... N–1 Этот способ называется методом линейных проб (linear probing). Его недоста% ток – тенденция элементов к скучиванию вблизи первичных ключей (то есть клю% чей, не испытавших коллизии при вставке). Конечно, в идеале функция G должна тоже распределять ключи равномерно по множеству свободных позиций. Однако на практике это довольно сложно обеспечить, и здесь предпочитают компромисс% ные методы, которые не требуют сложных вычислений, но все же работают лучше, чем линейная функция. Один из них состоит в использовании квадратичной фун% кции, так что индексы для последовательных проб задаются формулами h 0 = H(k) h i = (h 0 + i 2 ) MOD N, i > 0 Заметим, что при вычислении очередного индекса можно обойтись без возве% дения в квадрат, если воспользоваться следующими рекуррентными соотношени% ями для h i = i 2 и d i = 2i + 1 : h i+1 = h i + d i d i+1 = d i + 2, i > 0 причем h 0 = 0 и d 0 = 1 . Этот способ называется методом квадратичных проб (quadratic probing), и он, в общем, обходит упомянутую проблему скучивания, 259 практически не требуя дополнительных вычислений. Незначительный недоста% ток здесь в том, что при последовательных пробах проверяются не все элементы таблицы, то есть при вставке можно не обнаружить свободной позиции, хотя в таблице они еще есть. На самом деле в методе квадратичных проб проверяется по крайней мере половина таблицы, если ее размер N является простым числом. Это утверждение можно доказать следующим образом. Тот факт, что i %я и j %я про% бы попадают в один элемент таблицы, выражается уравнением i 2 MOD N = j 2 MOD N (i 2 – j 2 ) ≡ 0 (modulo N) Применяя формулу для разности квадратов, получаем (i + j)(i – j) ≡ 0 (modulo N) и так как i ≠ j , то заключаем, что хотя бы одно из чисел i или j должно быть не меньше N/2 , чтобы получить i+j = c*N с целым c . На практике этот недостаток не важен, так как необходимость выполнять N/2 вторичных проб при разрешении коллизий случается крайне редко, и только если таблица уже почти полна. В качестве применения описанной техники перепишем процедуру порожде% ния перекрестных ссылок из раздела 4.4.3. Главные отличия – в процедуре search и в замене указательного типа Node глобальной хэш%таблицей слов T . Хэш%функ% ция H вычисляется как остаток от деления на размер таблицы; для разрешения коллизий применяются квардатичные пробы. Подчеркнем, что для хорошей производительности важно, чтобы размер таблицы был простым числом. Хотя метод хэширования весьма эффективен в этом случае, – даже более эф% фективен, чем методы, использующие деревья, – у него есть и недостаток. Про% смотрев текст и собрав слова, мы, вероятно, захотим создать из них алфавитный список. Это несложно, если данные организованы в виде дерева, потому что прин% цип упорядоченности – основа этого способа организации. Однако простота теря% ется, если используется хэширование. Здесь и проявляется смысл слова «хэширо% вание». Для печати таблицы придется не только выполнить сортировку (которая здесь не показана), но оказывается даже предпочтительным отслеживать вставляе% мые ключи, явным образом связывая их в список. Поэтому высокая производитель% ность метода хэширования при поиске частично компенсируется дополнительны% ми операциями, необходимыми для завершения полной задачи порождения упорядоченного указателя перекрестных ссылок. CONST N = 997; (* , *) (*ADruS53_CrossRef*) WordLen = 32; (* *) Noc = 16; (* . *) TYPE Word = ARRAY WordLen OF CHAR; Table = POINTER TO ARRAY N OF RECORD key: Word; n: INTEGER; lno: ARRAY Noc OF INTEGER END; VAR line: INTEGER; Разрешение коллизий Хэширование 260 PROCEDURE search (T: Table; VAR a: Word); VAR i, d: INTEGER; h: LONGINT; found: BOOLEAN; (* # line*) BEGIN (* v– h a*) i := 0; h := 0; WHILE a[i] > 0X DO h := (256*h + ORD(a[i])) MOD N; INC(i) END; d := 1; found := FALSE; REPEAT IF T[h].key = a THEN (* *) found := TRUE; T[h].lno[T[h].n] := line; IF T[h].n < Noc THEN INC(T[h].n) END ELSIF T[h].key[0] = " " THEN (* *) found := TRUE; COPY(a, T[h].key); T[h].lno[0] := line; T[h].n := 1 ELSE (* *) h := h+d; d := d+2; IF h >= N THEN h := h–N END; IF d = N THEN Texts.WriteString(W," "); HALT(88) END END UNTIL found END search; PROCEDURE Tabulate (T: Table); VAR i, k: INTEGER; (* # W*) BEGIN FOR k := 0 TO N–1 DO IF T[k].key[0] # " " THEN Texts.WriteString(W, T[k].key); Texts.Write(W, TAB); FOR i := 0 TO T[k].n –1 DO Texts.WriteInt(W, T[k].lno[i], 4) END; Texts.WriteLn(W) END END END Tabulate; PROCEDURE CrossRef (VAR R: Texts.Reader); VAR i: INTEGER; ch: CHAR; w: Word; H: Table; BEGIN NEW(H); (* v– *) FOR i := 0 TO N–1 DO H[i].key[0] := " " END; line := 0; Texts.WriteInt(W, 0, 6); Texts.Write(W, TAB); Texts.Read(R, ch); WHILE R.eot DO IF ch = 0DX THEN (* *) Texts.WriteLn(W); INC(line); Texts.WriteInt(W, line, 6); Texts.Write(W, 9X); Texts.Read(R, ch) ELSIF ("A" <= ch) & (ch <= "Z") OR ("a" <= ch) & (ch <= "z") THEN i := 0; REPEAT IF i < WordLen–1 THEN w[i] := ch; INC(i) END; Texts.Write(W, ch); Texts.Read(R, ch) UNTIL (i = WordLen–1) OR (("A" <= ch) & (ch <= "Z")) & 261 (("a" <= ch) & (ch <= "z")) & (("0" <= ch) & (ch <= "9")); w[i] := 0X; (* *) search(H, w) ELSE Texts.Write(W, ch); Texts.Read(R, ch) END; Texts.WriteLn(W); Texts.WriteLn(W); Tabulate(H) END END CrossRef 5.4. Анализ хэширования Производительность вставки и поиска в методе хэширования для худшего случая, очевидно, ужасная. Ведь нельзя исключать, что аргумент поиска таков, что все пробы пройдут в точности по занятым позициям, ни разу не попав в нужные (или свободные). Нужно иметь большое доверие законам теории вероятности, чтобы применять технику хэширования. Здесь нужна уверенность в том, что в среднем число проб мало. Приводимые ниже вероятностные аргументы показывают, что это число не просто мало, а очень мало. Снова предположим, что все возможные значения ключей равновероятны и что хэш%функция H распределяет их равномерно по диапазону индексов таблицы. Еще предположим, что некоторый ключ вставляется в таблицу размера N , уже со% держащую k элементов. Тогда вероятность попадания в свободную позицию с первого раза равна (N–k)/N . Этой же величине равна вероятность p 1 того, что будет достаточно одного сравнения. Вероятность того, что понадобится в точно% сти еще одна проба, равна вероятности коллизии на первой попытке, умноженной на вероятность попасть в свободную позицию на второй. В общем случае получа% ем вероятность p i вставки, требующей в точности i проб: p 1 = (N–k)/N p 2 = (k/N) × (N–k)/(N–1) p 3 = (k/N) × (k–1)/(N–1) × (N–k)/(N–2) ……… p i = (k/N) × (k–1)/(N–1) × (k–2)/(N–2) × … × (N–k)/(N–(i–1)) Поэтому среднее число E проб, необходимых для вставки k+1 %го ключа, равно E k+1 = S S S S Si: 1 ≤ i ≤ k+1 : i × p i = 1 × (N–k)/N + 2 × (k/N) × (N–k)/(N–1) + ... + (k+1) * (k/N) × (k–1)/(N–1) × (k–2)/(N–2) × … × 1/(N–(k–1)) = (N+1) / (N–(k–1)) Поскольку число проб для вставки элемента совпадает с числом проб для его поиска, этот результат можно использовать для вычисления среднего числа E проб, необходимых для доступа к случайному ключу в таблице. Пусть снова раз% мер таблицы обозначен как N , и пусть m – число ключей уже в таблице. Тогда E = (S S S S Sk: 1 ≤ k ≤ m : E k ) / m = (N+1) × (SSSSSk: 1 ≤ k ≤ m : 1/(N–k+2))/m = (N+1) × (H N+1 – H N–m+1 ) Анализ хэширования Хэширование 262 где H – гармоническая функция. H можно аппроксимировать как H N = ln(N) + g , где g – постоянная Эйлера. Далее, если ввести обозначение a для отношения m/ (N+1) , то получаем E = (ln(N+1) – ln(N–m+1))/a = ln((N+1)/(N–m+1))/a = –ln(1–a)/a Величина a примерно равна отношению занятых и сво% бодных позиций; это отношение называется коэффициен том заполнения (load factor); a = 0 соответствует пустой таблице, a = N/(N+1) ≈ 1 – полной. Среднее число E проб для поиска или вставки случайного ключа дано в табл. 5.1 как функция коэффициента заполнения. Числа получаются удивительные, и они объясняют ис% ключительно высокую производительность метода преоб% разования ключей. Даже если таблица заполнена на 90%, в среднем нужно только 2,56 пробы, чтобы найти искомый ключ или свободную позицию. Особо подчеркнем, что это число не зависит от абсолютного числа ключей, а только от коэффициента заполнения. Приведенный анализ предполагает, что применяемый метод разрешения коллизий равномерно рассеивает ключи по оставшимся пози% циям. Методы, используемые на практике, дают несколько худшую производи% тельность. Детальный анализ метода линейных проб дает следующий результат для среднего числа проб: E = (1 – a/2) / (1 – a) Некоторые численные значения E(a) приведены в табл. 5.2 [5.4]. Результаты даже для простейшего способа разрешения коллизий настолько хороши, что есть соблазн рассматривать хэширование как панацею на все случаи жизни. Тем более что его производительность превышает даже самые изощрен% ные из обсуждавшихся методов с использованием деревьев, по крайней мере с точки зрения числа сравнений, необходимых для поиска и вставки. Но именно поэтому важно явно указать некоторые недостатки хэширования, даже если они очевидны при непредвзятом анализе. Разумеется, серьезным недостатком по сравнению с методами с динамическим размещением являются фиксированный размер таблицы и невозможность изме% нять его в соответствии с текущей необходимостью. Поэтому обязательно нужна достаточно хорошая ап% риорная оценка числа обрабатываемых элементов дан% ных, если неприемлемы плохое использование памяти или низкая производительность (или переполнение таблицы). Даже если число элементов известно точ% но, – что бывает крайне редко, – стремление к хорошей производительности заставляет выбирать таблицу не% много большего размера (скажем, на 10%). Второй серьезный недостаток методов «рассеянно% го хранения» становится очевидным, если ключи нуж% Таблица 5.1. Таблица 5.1. Таблица 5.1. Таблица 5.1. Таблица 5.1. Среднее число проб E как функция коэффици: ента заполнения a a E 0.1 1.05 0.25 1.15 0.5 1.39 0.75 1.85 0.9 2.56 0.95 3.15 0.99 4.66 Таблица 5.2. Таблица 5.2. Таблица 5.2. Таблица 5.2. Таблица 5.2. Среднее число проб для метода линейных проб a E 0.1 1.06 0.25 1.17 0.5 1.50 0.75 2.50 0.9 5.50 0.95 10.50 263 но не только вставлять и искать, но и удалять. Удаление элементов в хэш%табли% це – чрезвычайно громоздкая операция, если только не использовать прямое свя% зывание в отдельной области переполнения. Поэтому разумно заключить, что древесные способы организации по%прежнему привлекательны и даже предпоч% тительны, если объем данных плохо предсказуем, сильно меняется и даже может уменьшаться. |