Файл: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией.pdf

4.7. БGдеревья (BGtrees)
До сих пор наше обсуждение ограничивалось двоичными деревьями, то есть таки%
ми, где каждый узел имеет не более двух потомков. Этого вполне достаточно,
если, например, мы хотим представить семейные связи, подчеркивая происхож%
дение, то есть указывая для каждого человека его двух родителей. Ведь ни у кого не бывает больше двух родителей. Но что, если возникнет необходимость указы%
вать потомков каждого человека? Тогда придется учесть, что у некоторых людей больше двух детей, и тогда деревья будут содержать узлы со многими ветвями.
Будем называть такие деревья сильно ветвящимися.
Разумеется, в подобных структурах нет ничего особенного, и мы уже знакомы со всеми средствами программирования и определения данных, чтобы справиться с такими ситуациями. Например, если задан абсолютный верхний предел на число детей (такое предположение, конечно, немного футуристично), то можно представ%
лять детей полем%массивом в записи, представляющей человека. Но если число де%
тей сильно зависит от конкретного индивида, то это может привести к плохому ис%
пользованию имеющейся памяти. В этом случае гораздо разумнее организовать потомство с помощью линейного списка, причем указатель на младшего (или стар%
шего) потомка хранится в записи родителя. Возможное определение типа для этого случая приводится ниже, а возможная структура данных показана на рис. 4.40.
TYPE Person = POINTER TO RECORD
name: alfa;
sibling, offspring: Person
END
Б<деревья (B

Динамические структуры данных
228
При наклоне картинки на 45 градусов она будет выглядеть как обычное дво%
ичное дерево. Но такой вид вводит в заблуждение, так как функциональный смысл двух структур совершенно разный. Обычно нельзя безнаказанно обра%
щаться с братом как с сыном и не следует так поступать даже при определении структур данных. Структуру данных в этом примере можно усложнить еще больше, вводя в запись для каждого индивида дополнительные компоненты,
представляющие другие семейные связи, например супружеские отношения между мужем и женой или даже информацию о родителях, ведь подобную ин%
формацию не всегда можно получить из ссылок от родителей к детям и к брать%
ям%сестрам. Подобная структура быстро вырастает в сложную реляционную базу данных, на которую можно отобразить несколько деревьев. Алгоритмы, ра%
ботающие с такими структурами, тесно связаны с соответствующими определе%
ниями данных, так что не имеет смысла указывать ни какие%либо общие прави%
ла, ни общеприменимые приемы.
Однако есть очень полезная область применения сильно ветвящихся деревьев,
представляющая общий интерес. Это построение и поддержка больших деревьев поиска, в которых нужно выполнять вставки и удаления элементов, но опера%
тивная память компьютера либо недостаточна по размеру, либо слишком дорога,
чтобы использовать ее для длительного хранения данных.
Итак, предположим, что узлы дерева должны храниться на внешних устрой%
ствах хранения данных, таких как диски. Динамические структуры данных,
введенные в этой главе, особенно удобны для того, чтобы использовать внешние носители. Главная новация будет просто в том, что роль указателей теперь будут играть дисковые адреса, а не адреса в оперативной памяти. При использовании двоичного дерева для набора данных из, скажем, миллиона элементов потребу%
ется в среднем примерно ln 10 6
(то есть около 20) шагов поиска. Поскольку здесь каждый шаг требует обращения к диску (с неизбежной задержкой), то крайне желательно организовать хранение так, чтобы уменьшить число таких обраще%
ний. Сильно ветвящееся дерево – идеальное решение проблемы. Если имеет мес%
то обращение к элементу на внешнем носителе, то без особых усилий становится доступной целая группа элементов. Отсюда идея разделить дерево на поддеревья таким образом, чтобы эти поддеревья представлялись блоками, которые доступ%
Рис. 4.40. Сильно ветвящееся дерево, представленное как двоичное дерево

229
ны сразу целиком. Назовем такие поддеревья страницами. На рис. 4.41 показано двоичное дерево, разделенное на страницы по 7 узлов на каждой.
Рис. 4.41. Двоичное дерево, разделенное на страницы
Экономия на числе обращений к диску – теперь обращение к диску соответ%
ствует обращению к странице – может быть значительной. Предположим, что на каждой странице решено размещать по 100 узлов (это разумное число); тогда де%
рево поиска из миллиона элементов потребует в среднем только log
100
(10 6
)
(то есть около 3) обращений к страницам вместо 20. Правда, при случайном росте де%
рева это число все равно может достигать
10 4
в наихудшем случае. Ясно, что рос%
том сильно ветвящихся деревьев почти обязательно нужно как%то управлять.
4.7.1. Сильно ветвящиеся Б=деревья
Если искать способ управления ростом дерева, то следует сразу исключить требо%
вание идеальной сбалансированности, так как здесь понадобятся слишком боль%
шие накладные расходы на балансировку. Ясно, что нужно несколько ослабить требования. Весьма разумный критерий был предложен Бэйером и Маккрейтом в 1970 г. [4.2]: каждая страница (кроме одной) содержит от n
до
2n узлов, где n
–
некоторая заданная константа. Поэтому для дерева из
N
элементов и с максималь%
ным размером страницы в
2n узлов потребуется в худшем случае log n
N
обраще%
ний к страницам; а именно на обращения к страницам приходятся основные уси%
лия в подобном поиске. Более того, важный коэффициент использования памяти будет не меньше 50%, так как страницы всегда будут заполнены по крайней мере наполовину. Причем при всех этих достоинствах описываемая схема требует сравнительно простых алгоритмов для поиска, вставки и удаления элементов.
В дальнейшем мы подробно изучим их.
Такую структуру данных называют Бдеревом (также B%дерево; B%tree), число n
– его порядком, и при этом предполагаются следующие свойства:
1. Каждая страница содержит не более
2n элементов (ключей).
2. Каждая страница, кроме корневой, содержит не менее n
элементов.
Б<деревья (B

Динамические структуры данных
230 3. Каждая страница либо является концевой, то есть не имеет потомков, либо имеет m+1
потомков, где m
– число ключей на этой странице.
4. Все концевые страницы находятся на одном уровне.
Рисунок 4.42 показывает Б%дерево порядка 2, имеющее 3 уровня. На всех стра%
ницах – 2, 3 или 4 элемента; исключением является корень, где разрешено иметь только один элемент. Все концевые страницы – на уровне 3. Ключи будут стоять в порядке возрастания слева направо, если Б%дерево «сплющить» в один слой так,
чтобы потомки вставали между ключами соответствующих страниц%предков. Та%
кая организация является естественным развитием идеи двоичных деревьев поис%
ка и предопределяет способ поиска элемента с заданным ключом. Рассмотрим страницу, показанную на рис. 4.43, и пусть задан аргумент поиска x
. Предполагая,
что страница уже считана в оперативную память, можно использовать обычные методы поиска среди ключей k
0
... k m–1
. Если m
велико, то можно применить по%
иск делением пополам; если оно мало, то будет достаточно обычного последова%
тельного поиска. (Заметим, что время поиска в оперативной памяти будет, веро%
ятно, пренебрежимо мало по сравнению со временем считывания страницы в оперативную память из внешней.) Если поиск завершился неудачей, то возника%
ет одна из следующих ситуаций:
1.
k i
< x < k i+1
для
0 < i < m–1
Поиск продолжается на странице p
i
^
2.
k m–1
< x
Поиск продолжается на странице p
m–1
^
3.
x < k
0
Поиск продолжается на странице p
–1
^
Рис. 4.42. Б:дерево порядка 2
Рис. 4.43. Б:дерево с m ключами

231
Если в каком%то случае указатель оказался равен
NIL
, то есть страница%пото%
мок отсутствует, то это значит, что элемента с ключом x
во всем дереве нет, и по%
иск заканчивается.
Удивительно, но вставка в Б%дерево тоже сравнительно проста. Если элемент нужно вставить на странице с m < 2n элементами, то вставка затрагивает только содержимое этой страницы. И только вставка в уже заполненную страницу затро%
нет структуру дерева и может привести к размещению новых страниц. Чтобы по%
нять, что случится в этом случае, рассмотрим рис. 4.44, который показывает вставку ключа 22 в Б%дерево порядка 2. Здесь выполняются следующие шаги:
1. Обнаруживается, что ключа 22 в дереве нет; вставка на странице
C
невоз%
можна, так как
C
уже полна.
2. Страница
C
разбивается на две (то есть размещается новая страница
D
).
3.
2n+1
ключей поровну распределяются между страницами
C
и
D
, а средний ключ перемещается на один уровень вверх на страницу%предок
A
Рис. 4.44. Вставка ключа 22 в Б:дерево
Эта очень изящная схема сохраняет все характеристические свойства Б%дере%
вьев. В частности, разбиваемые страницы содержат в точности n
элементов. Разу%
меется, вставка элемента на странице%предке тоже может вызвать переполнение,
так что снова нужно выполнять разбиение, и т. д. В крайнем случае, процесс раз%
биений достигнет корня. И это единственный способ увеличить высоту Б%дерева.
Странная манера расти у Б%деревьев: вверх от листьев к корню.
Разработаем теперь подробную программу на основе этих набросков. Уже ясно, что самой удобной будет рекурсивная формулировка, так как процесс раз%
биения может распространяться в обратном направлении по пути поиска. Поэто%
му по общей структуре программа получится похожей на вставку в сбалансиро%
ванное дерево, хотя в деталях будут отличия. Прежде всего нужно определить структуру страниц. Выберем представление элементов с помощью массива:
TYPE Page = POINTER TO PageDescriptor;
Item = RECORD key: INTEGER;
p: Page;
count: INTEGER (* *)
END;
PageDescriptor = RECORD m: INTEGER; (* 0 .. 2n *)
p0: Page;
e: ARRAY 2*n OF Item
END
Б<деревья (B

Динамические структуры данных
232
Поле count представляет любую информацию, которая может быть связана с элементом, но оно никак не участвует собственно в поиске. Заметим, что каждая страница предоставляет место для
2n элементов. Поле m
указывает реальное чис%
ло элементов на данной странице. Так как m
≥
n
(кроме корневой страницы), то гарантируется, что память будет использована по меньшей мере на 50%.
Алгоритм поиска и вставки в Б%дерево сформулирован ниже в виде процедуры search
. Его основная структура бесхитростна и подобна поиску в сбалансирован%
ном двоичном дереве, за исключением того факта, что выбор ветви не ограничен двумя вариантами. Вместо этого поиск внутри страницы реализован как поиск делением пополам в массиве e.
Алгоритм вставки для ясности сформулирован как отдельная процедура. Она вызывается, когда поиск показал, что нужно передать элемент вверх по дереву
(в направлении корня). Это обстоятельство указывается булевским параметром%
переменной h
; его использование аналогично случаю алгоритма вставки в сбалан%
сированное дерево, где h
сообщал, что поддерево выросло. Если h
истинно, то вто%
рой параметр%переменная u
содержит элемент, передаваемый наверх. Заметим,
что вставки начинаются в виртуальных страницах, а именно в так называемых дополнительных узлах (см. рис. 4.19); при этом новый элемент сразу передается через параметр u
вверх на концевую страницу для реальной вставки. Вот набро%
сок этой схемы:
PROCEDURE search (x: INTEGER; a: Page; VAR h: BOOLEAN; VAR u: Item);
BEGIN
IF a = NIL THEN (*x , *)
x u, h TRUE, ,
u
ELSE
x a.e;
IF
THEN

ELSE
search(x, descendant, h, u);
IF h THEN (* *)
IF
a^ < 2n THEN
u a^ h FALSE
ELSE

END
END
END
END
END search
Если h
равен
TRUE
после вызова процедуры search в главной программе, зна%
чит, требуется разбить корневую страницу. Так как корневая страница играет осо%
бую роль, то это действие следует запрограммировать отдельно. Оно состоит про%
сто в размещении новой корневой страницы и вставке единственного элемента,

233
задаваемого параметром u
. В результате новая корневая страница содержит единственный элемент. Полный текст программы приведен ниже, а рис. 4.45 по%
казывает, как она строит Б%дерево при вставке ключей из следующей последова%
тельности:
20; 40 10 30 15; 35 7 26 18 22; 5; 42 13 46 27 8 32; 38 24 45 25;
Точки с запятой отмечают моменты, когда сделаны «снимки», – после каждого размещения страниц. Вставка последнего ключа вызывает два разбиения и разме%
щение трех новых страниц.
Рис. 4.45. Рост Б:дерева порядка 2
Поскольку каждый вызов процедуры поиска подразумевает одно копирование страницы в оперативную память, то понадобится не более k = log n
(N)
рекурсив%
ных вызовов для дерева из
N
элементов. Поэтому нужно иметь возможность раз%
местить k
страниц в оперативной памяти. Это первое ограничение на размер стра%
ницы
2n
. На самом деле нужно размещать больше, чем k
страниц, так как вставка может вызвать разбиение. Отсюда следует, что корневую страницу лучше посто%
Б<деревья (B

Динамические структуры данных
234
янно держать в оперативной памяти, так как каждый запрос обязательно прохо%
дит через корневую страницу.
Другое достоинство организации данных с помощью Б%деревьев – удобство и экономичность чисто последовательного обновления всей базы данных. Каждая страница загружается в оперативную память в точности один раз.
Операция удаления элементов из Б%дерева по идее довольно проста, но в дета%
лях возникают усложнения. Следует различать две разные ситуации:
1. Удаляемый элемент находится на концевой странице; здесь алгоритм уда%
ления прост и понятен.
2. Элемент находится на странице, не являющейся концевой; его нужно заме%
нить одним из двух соседних в лексикографическом смысле элементов, ко%
торые оказываются на концевых страницах и могут быть легко удалены.
В случае 2 нахождение соседнего ключа аналогично соответствующему алго%
ритму при удалении из двоичного дерева. Мы спускаемся по крайним правым указателям вниз до концевой страницы
P
, заменяем удаляемый элемент крайним правым элементом на
P
и затем уменьшаем размер страницы
P
на
1
. В любом слу%
чае за уменьшением размера должна следовать проверка числа элементов m
на уменьшившейся странице, так как m
< n
нарушает характеристическое свойство
Б%деревьев. Здесь нужно предпринять дополнительные действия; это условие не
достаточной заполненности (underflow) указывается булевским параметром h
Единственный выход – позаимствовать элемент с одной из соседних страниц,
скажем
Q
. Поскольку это требует считывания страницы
Q
в оперативную память, –
что относительно дорого, – есть соблазн извлечь максимальную пользу из этой нежелательной ситуации и позаимствовать за один раз больше одного элемента.
Обычная стратегия – распределить элементы на страницах
P
и
Q
поровну на обеих страницах. Это называется балансировкой страниц (page balancing).
Разумеется, может случиться, что элементов для заимствования не осталось,
поскольку страница
Q
достигла минимального размера n
. В этом случае общее число элементов на страницах
P
и
Q
равно
2n–1
, и можно объединить обе страни%
цы в одну, добавив средний элемент со страницы%предка для
P
и
Q
, а затем пол%
ностью избавиться от страницы
Q
. Эта операция является в точности обраще%
нием разбиения страницы. Целиком процесс проиллюстрирован удалением ключа 22 на рис. 4.44. И здесь снова удаление среднего ключа со страницы%пред%
ка может уменьшить размер последней ниже разрешенного предела n
, тем са%
мым требуя выполнения специальных действий (балансировки или слияния) на следующем уровне. В крайнем случае, слияние страниц может распространять%
ся вверх до самого корня. Если корень уменьшается до размера 0, следует уда%
лить сам корень, что вызывает уменьшение высоты Б%дерева. На самом деле это единственная ситуация, когда может уменьшиться высота Б%дерева. Рисунок
4.46 показывает постепенное уменьшение Б%дерева с рис. 4.45 при последова%
тельном удалении ключей
25 45 24; 38 32; 8 27 46 13 42; 5 22 18 26; 7 35 15;

235
Здесь, как и раньше, точки с запятой отмечают места, где делаются «снимки»,
то есть там, где удаляются страницы. Следует особо подчеркнуть сходство струк%
туры алгоритма удаления с соответствующей процедурой для сбалансированного дерева.
Рис. 4.46. Удаление элементов из Б:дерева порядка 2
TYPE Page = POINTER TO PageRec;
(* ADruS471_Btrees *)
Entry = RECORD
key: INTEGER; p: Page
END;
PageRec = RECORD
m: INTEGER; (* *)
p0: Page;
e: ARRAY 2*N OF Entry
END;
VAR root: Page; W: Texts.Writer;
Б<деревья (B

Динамические структуры данных
236
PROCEDURE search (x: INTEGER; VAR p: Page; VAR k: INTEGER);
VAR i, L, R: INTEGER; found: BOOLEAN; a: Page;
BEGIN
a := root; found := FALSE;
WHILE (a # NIL) & found DO
L := 0; R := a.m; (* *)
WHILE L < R DO
i := (L+R) DIV 2;
IF x <= a.e[i].key THEN R := i ELSE L := i+1 END
END;
IF (R < a.m) & (a.e[R].key = x) THEN found := TRUE
ELSIF R = 0 THEN a := a.p0
ELSE a := a.e[R–1].p
END
END;
p := a; k := R
END search;
PROCEDURE insert (x: INTEGER; a: Page; VAR h: BOOLEAN; VAR v: Entry);
(*a # NIL. ’ x ‡– a;
(*
x.
(*
 € , # v.
(*
h := " "*)
VAR i, L, R: INTEGER;
b: Page; u: Entry;
BEGIN
(* h *)
IF a = NIL THEN
v.key := x; v.p := NIL; h := TRUE
ELSE
L := 0; R := a.m; (* *)
WHILE L < R DO
i := (L+R) DIV 2;
IF x <= a.e[i].key THEN R := i ELSE L := i+1 END
END;
IF (R < a.m) & (a.e[R].key = x) THEN (* v, #*)
ELSE (* *)
IF R = 0 THEN b := a.p0 ELSE b := a.e[R–1].p END;
insert(x, b, h, u);
IF h THEN (* u a.e[R]*)
IF a.m < 2*N THEN
h := FALSE;
FOR i := a.m TO R+1 BY –1 DO a.e[i] := a.e[i–1] END;
a.e[R] := u; INC(a.m)
ELSE (* ; a a, b
v*)
NEW(b);
IF R < N THEN (* a*)

237
v := a.e[N–1];
FOR i := N–1 TO R+1 BY –1 DO a.e[i] := a.e[i–1] END;
a.e[R] := u;
FOR i := 0 TO N–1 DO b.e[i] := a.e[i+N] END
ELSE (* b*)
DEC(R, N);
IF R = 0 THEN
v := u
ELSE
v := a.e[N];
FOR i := 0 TO R–2 DO b.e[i] := a.e[i+N+1] END;
b.e[R–1] := u
END;
FOR i := R TO N–1 DO b.e[i] := a.e[i+N] END
END;
a.m := N; b.m := N; b.p0 := v.p; v.p := b
END
END
END
END
END insert;
PROCEDURE underflow (c, a: Page; s: INTEGER; VAR h: BOOLEAN);
(*a = , # v (underflow),
(*
c = – ,
(*
s = # c*)
VAR b: Page; i, k: INTEGER;
BEGIN
(*h & (a.m = N–1) & (c.e[s–1].p = a) *)
IF s < c.m THEN (*b := a*)
b := c.e[s].p;
k := (b.m–N+1) DIV 2; (*k = b*)
a.e[N–1] := c.e[s]; a.e[N–1].p := b.p0;
IF k > 0 THEN (* k–1 b a*)
FOR i := 0 TO k–2 DO a.e[i+N] := b.e[i] END;
c.e[s] := b.e[k–1]; b.p0 := c.e[s].p;
c.e[s].p := b; DEC(b.m, k);
FOR i := 0 TO b.m–1 DO b.e[i] := b.e[i+k] END;
a.m := N–1+k; h := FALSE
ELSE (* a b, b v € *)
FOR i := 0 TO N–1 DO a.e[i+N] := b.e[i] END;
DEC(c.m);
FOR i := s TO c.m–1 DO c.e[i] := c.e[i+1] END;
a.m := 2*N; h := c.m < N
END
ELSE (*b := a*)
DEC(s);
IF s = 0 THEN b := c.p0 ELSE b := c.e[s–1].p END;
k := (b.m–N+1) DIV 2; (*k = b*)
Б<деревья (B

Динамические структуры данных
238
IF k > 0 THEN
FOR i := N–2 TO 0 BY –1 DO a.e[i+k] := a.e[i] END;
a.e[k–1] := c.e[s]; a.e[k–1].p := a.p0;
(* k–1 b a, c*) DEC(b.m, k);
FOR i := k–2 TO 0 BY –1 DO a.e[i] := b.e[i+b.m+1] END;
c.e[s] := b.e[b.m]; a.p0 := c.e[s].p;
c.e[s].p := a; a.m := N–1+k; h := FALSE
ELSE (* a b, a v € *)
c.e[s].p := a.p0; b.e[N] := c.e[s];
FOR i := 0 TO N–2 DO b.e[i+N+1] := a.e[i] END;
b.m := 2*N; DEC(c.m); h := c.m < N
END
END
END underflow;
PROCEDURE delete (x: INTEGER; a: Page; VAR h: BOOLEAN);
(* x ‡– a;
(*
v ,
(*
;
(*
h := " v "*)
VAR i, L, R: INTEGER; q: Page;
PROCEDURE del (p: Page; VAR h: BOOLEAN);
VAR k: INTEGER; q: Page; (*# a, R*)
BEGIN k := p.m–1; q := p.e[k].p;
IF q # NIL THEN del(q, h);
IF h THEN underflow(p, q, p.m, h) END
ELSE p.e[k].p := a.e[R].p; a.e[R] := p.e[k];
DEC(p.m); h := p.m < N
END
END del;
BEGIN
IF a # NIL THEN
L := 0; R := a.m; (* *)
WHILE L < R DO
i := (L+R) DIV 2;
IF x <= a.e[i].key THEN R := i ELSE L := i+1 END
END;
IF R = 0 THEN q := a.p0 ELSE q := a.e[R–1].p END;
IF (R < a.m) & (a.e[R].key = x) THEN (* v*)
IF q = NIL THEN (*a — *)
DEC(a.m); h := a.m < N;
FOR i := R TO a.m–1 DO a.e[i] := a.e[i+1] END
ELSE
del(q, h);
IF h THEN underflow(a, q, R, h) END
END
ELSE

239
delete(x, q, h);
IF h THEN underflow(a, q, R, h) END
END
END
END delete;
PROCEDURE ShowTree (VAR W: Texts.Writer; p: Page; level: INTEGER);
VAR i: INTEGER;
BEGIN
IF p # NIL THEN
FOR i := 1 TO level DO Texts.Write(W, 9X) END;
FOR i := 0 TO p.m–1 DO Texts.WriteInt(W, p.e[i].key, 4) END;
Texts.WriteLn(W);
IF p.m > 0 THEN ShowTree(W, p.p0, level+1) END;
FOR i := 0 TO p.m–1 DO ShowTree(W, p.e[i].p, level+1) END
END
END ShowTree;
Эффективность Б%деревьев изучалась весьма подробно, результаты можно найти в упомянутой статье Бэйера и Маккрейта. В частности, там обсуждается вопрос оптимального размера страницы, который сильно зависит от характерис%
тик используемой вычислительной системы и памяти.
Вариации на тему Б%деревьев обсуждаются у Кнута ([2.7], с. 521–525 перево%
да). Заслуживает внимания наблюдение, что разбиение страницы следует откла%
дывать, как следует откладывать и слияние страниц, и сначала пытаться сбалан%
сировать соседние страницы. В остальном похоже, что выгода от предлагавшихся улучшений незначительна. Весьма полный обзор Б%деревьев можно найти в [4.8].

1   ...   14   15   16   17   18   19   20   21   22

Глава 5
Хэширование
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
но не только вставлять и искать, но и удалять. Удаление элементов в хэш%табли%
це – чрезвычайно громоздкая операция, если только не использовать прямое свя%
зывание в отдельной области переполнения. Поэтому разумно заключить, что древесные способы организации по%прежнему привлекательны и даже предпоч%
тительны, если объем данных плохо предсказуем, сильно меняется и даже может уменьшаться.

1   ...   14   15   16   17   18   19   20   21   22