Главная  Терминология Хоора 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 [ 100 ] 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

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

Основная трудность преобразования ключей заключаете в том, что множество возможных значений ключей намног обширнее, чем множество имеющихся адресов памяти (нндек^ сов массива). Типичный пример - использование слов длиной скажем, до 10 букв алфавита в качестве ключей для идентц! фикации индивидуумов в множестве, например, до тысячи человек. Следовательно, имеются 26 возможных ключей которые нужно отобразить в 10 возможных индексов. Поэтому очевидно, что Н - это функция, отображающая много в один . Р.гли дан некоторый ключ fc, то первый этап в операции поиска - это вычисление соответствующего индекса h = H{k), а второй - очевидно, необходимый этап -провер-ка, действительно ли элемент с ключом k находится в массиве (таблице) Т по адресу h, т. е. проверка T[H(k)]-key = k. Сразу возникают два вопроса:

1. Какую функцию Я следует использовать?

2. Как поступать в ситуации, когда Н не дает местонахождения нужного элемента?

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

4.6.1. Выбор функции преобразования

Основное требование к хорошей функции преобразования состоит в том, чтобы она распределяла ключи как можно более равномерно по шкале значений индексов. Кроме выполнения этого требования, распределение не связано никакой схемой, и даже желательно, чтобы оно производило впечатление совершенно случайного. Такая особенность дала этомУ методу несколько ненаучное название расстановки (хеШИ рования), а Я называется функцией расстановки*). РазУ меется, она должна эффективно вычисляться, т. е. состоят

*) Следует отметить, что в советской литературе впервые этот был описан А. П. Ершовым и назван им функциями расстановки -Прим. ред.



1та функция обладает тем свойством, что значения ключей равномерно распределяются на всем интервале индексов, поэтому она служит основой большинства преобразований ключей. Кроме того, она очень эффективно вычисляется при N, равном степени двойки. Но как раз этого случая следует избегать, если ключи являются последовательностями букв. Предположение, что все ключи равновероятны, в этом случае совершенно ошибочно. В результате слова, различающиеся лишь несколькими символами, будут с большой вероятностью отображаться в одинаковые индексы, что приведет к чрезвычайно неравномерному распределению. Поэтому рекомендуется, чтобы в (4.88) было простым числом [4.7]. Отсюда следует, что придется выполнять операцию целого деления, которую нельзя заменить простым маскированием двоичных разрядов. Но это не является препятствием для большинства

f-овременных вычислительных машин, которые имеют встроеи-ую команду деления. Часто употребляется свертка, состоящая из выполнения логических операций, таких, как исключающее или на не-

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

4.6.2. Разрешение конфликтов

Если строка в таблице, соответствующая заданному ключу. Не содержит нужный элемент, то имеет место конфликт, т. е. Два элемента имеют ключи.отображающиеся в один и тот же Индекс. Нужна вторая проба с использованием другого ин-Лекса, который однозначно получается на основе данного (ключа. Существует несколько методов получения таких вторичных индексов. Очевидный и эффективный метод*) - свя-

*) Это, конечно, метод разрешения конф.чиктов, а не метод получения Вторичных индексов.- Ярыл(. рей.

очень небольшого числа основных арифметических действий-

Предположим, что имеется функция ord{k), которая определяет порядковый номер ключа k во множестве всех воз-. jjoSCHbix значений ключей. Предположим далее, что индексы массива занимают интервал целых чисел О ... - I, где - размер массива. Тогда очевидным решением является

~~ H{k) = ord{k) той N (4.88)



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

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

. /г:=Я(/г); /:=0; repeat

if T{h\.key=k then элемент найден else

if ТЩ.кеу = свободно then элемента нет в

таблице else (4.89)

begin {конфликт}

i:=i+\, h:=H{k) + G{i) end

until найден или нет в таблице [или таблица полна)

Для разрещения конфликтов в литературе предлагались различные функции. Обзор этой темы Моррисом в 1968 г. [4.8] стимулировал активную деятельность в этой области. Простейщий метод - это, считая, что таблица круговая, исследовать следующее место и так до тех пор, пока не будет найден элемент с заданным ключом или не встретится свободное место. Следовательно, G (i) = i; индексы Ы, используемые для поиска, в этом случае имеют вид:

. о=Я(/е). ,

hi = (h(,-\-i)modN, i=l...N-l.

Этот метод называется линейным опробированием, он имеет тот недостаток, что элементы обычно скапливаются вокруг первичных ключей (ключей, при которых мы не столкнулись с конфликтом при включении). В идеале, конечно, следует выбирать такую функцию G, которая вновь равномерно ра сеивает ключи на оставщемся пространстве. Но на практике это требует слишком больших затрат, и предпочтение of-




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 [ 100 ] 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133