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

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

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

номером 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.

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

Нет

Да

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≤i<M, и принадлежат

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

содержит ключ KEY[i] и, возможно, другие поля. Значение вспомогательной переменной N равно числу занятых узлов; эта переменная рассматривается как часть таблицы, и при вставке нового ключа ее значение увеличивается на 1.

Данный алгоритм использует хеш-функцию h(K) и линейную

последовательность проб ( * ) для адресации. Модификации этой

последовательности обсуждаются ниже.

L1.[Хеширование.] Установить i←h(K). (Теперь 0≤i< M.)

L2.[Сравнить.] Если узел TABLE[i] свободен, то перейти на L4. В

противном случае, если KEY[i]=K, алгоритм заканчивается удачно.

L3.[Перейти к следующему.] Установить i←(i-1); если теперь i<0,

Установить i←i+M. Вернуться на L 2.

L4.[Вставить.] (Поиск был неудачным.) Если N=M-1, алгоритм

заканчивается по переполнению. В противном

случае установить N←N+1, отметить, что узел TABLE[i] занят и

установить KEY[i]←K.

На рис.( см. ниже) показано, что происходит при вставке с помощью алгоритма~L семи "норвежских" ключей , имеющих коды хеширования 2, 7, 1, 8, 2, 8, 1

соответственно. Последние три ключа- FEM, SEKS и SYV-смещены по

сравнению со своими начальными адресами h(K).

0 [ FEM ]

1 [ TRE ]

2 [ EN ]

3 []

4 []

5 [ SYV ]

6 [_SEKS ]

7 [_ TO ]

8 [ FIRE ]

Рис. Линейная открытая адресация.

Эксперименты с линейным опробованием показывают, что этот метод работает прекрасно, пока таблица не слишком заполнена, но в конце концов процесс замедляется, длинные серии проб становятся все более частыми. Причину такого поведения можно понять, рассмотрев следующую гипотетическую рассеянную таблицу (M=19, N= 9):

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Заштрихованные квадраты обозначают занятые позиции. Ключ K, который должен быть вставлен в таблицу следующим, попадет в одну из десяти свободных позиций, но не с равными вероятностями. В самом деле, K будет вставлен в позицию 11, если 11≤h(K)≤15, а в позицию 8 он попадет лишь при h(K)=8. Следовательно, вероятность попасть в

позицию 11 в пять раз больше, чем в позицию 8; длинные списки стремятся стать еще длиннее.

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

Этот алгоритм почти совпадает с алгоритмом L, но использует несколько иную последовательность проб, вычисляя две хеш-функции h₁(K) и h₂(K). Как обычно, h₁(K) порождает величины от 0 до M-1 включительно; но значения h₂(K) должны лежать от 1 до M-1 и быть взаимно просты с M. (Например, если M - простое число, то h₂(K) может быть любой величиной от 1 до M-1 включительно, или, если M=2^m, то h₂(K) может быть любым нечетным числом между 1 и 2^m-1.)

D1.[Первое хеширование.] Установить i ←h₂(K).

D2.[Первая проба.] Если узел TABLE[i] свободен, то перейти

на D6. В противном случае, если KEY[i]=K, алгоритм

заканчивается удачно.

D3.[Второе хеширование.] Установить c←h₂(K).

D4.[Перейти к следующему.] Установить i←i-c; если теперь i<0,

Установить i←i+M.

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

на D6. В противном случае, если KEY[i]=K, алгоритм заканчивается

удачно; в противном случае вернуться на D4.

D6.[Вставка.] Если N=M-1, алгоритм заканчивается по переполнению. В

противном случае установить N←N+1, пометить узел TABLE[i]как занятый

и установить KEY[i]← K.

Для вычисления h₂(K) было предложено несколько способов.

Если M - простое число и h₁(K)=K mod M, можно положить h₂(K)=1+(K mod (M-1)); но так как M-1 четно, было бы лучше положить h₂(K)=1+(K mod (M-2)).

Это наводит на мысль о таком выборе M, чтобы M и M-2были простыми числами-близнецами, например 1021 и 1019. Можно взять h₂(K)=1+([K/M] mod (M-2)), ибо частное [K/M] можно получить в регистре как побочный продукт вычисления h₁(K).

Сравнение методов. Итак, мы знаем много методов поиска;

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

для конкретного приложения? Трудно в нескольких словах описать все, что нам хотелось бы учесть при выборе метода поиска, однако следующие соображения, пожалуй, наиболее важны, если мы заинтересованы в сокращении времени поиска и объема занимаемой памяти.

Различные способы разрешения коллизий приводят к различному числу проб. Но это еще не все, так как с изменением метода меняется время пробы, что заметно отражается на времени работы. При линейном опробовании чаще, чем в других методах, происходит обращение к таблице, зато этот метод прост.

Методы цепочек весьма экономны с точки зрения числа проб, но потребность в дополнительном пространстве памяти для полей ссылок иногда (при небольшом размере записей) делает более привлекательной открытую адресацию. Например, если нужно сделать выбор между таблицей с цепочками на 500 элементов и таблицей с открытой адресацией на 1000 элементов, то последняя, очевидно, предпочтительнее, ибо она обеспечивает эффективный поиск среди 500 записей и способна вместить в два раза больше данных. С другой стороны, порой в силу размера записей или их формата пространство под поля ссылок достается фактически бесплатно.

Как соотносятся методы хеширования с другими стратегиями поиска? Сравнивая их по скорости, можно утверждать, что методы хеширования лучше, если число записей велико, поскольку среднее время поиска для методов хеширования остается ограниченным при N →∞ в случае, когда таблица не становится слишком заполненной. Более того, бинарный поиск годится лишь для фиксированных таблиц, в то время как рассеянные таблицы допускают эффективные процедуры вставки.

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

a) После неудачного поиска в рассеянной таблице мы знаем лишь то, что нужного ключа там нет. Методы поиска, основанные на сравнениях, всегда дают больше информации; они позволяют найти наибольший ключ ≤ K или наименьший ключ ≥ K , что важно во многих приложениях

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

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

b) Часто довольно трудно распределить память для рассеянных таблиц; под хеш-таблицу нужно отвести определенную область памяти, а размер ее не всегда ясен. Если отвести слишком много памяти, то такая расточительность отразится на других списках или на других пользователях ЭВМ, но если отвести мало места, таблица переполнится! При переполнении рассеянной таблицы, вероятно, лучше всего "рехешировать" ее, т.е. отвести больше пространства и изменить хеш-функцию, а затем вставить записи в большую таблицу. Ф.~Хопгуд предложил рехешировать таблицу, если коэффициент заполнения достигнет α₀ , заменяя M на d₀M.

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

c) Наконец, при использовании методов хеширования нужно свято верить в теорию вероятностей, ибо они эффективны лишь в среднем, а наихудший случай просто ужасен! Как и в ситуации с датчиками случайных чисел, мы не можем быть полностью уверенными в том, что при применении к новому множеству данных хеш-функция будет работать удовлетворительно. Поэтому рассеянная память не всегда подходит для работы в реальном масштабе времени, например для управления движением транспорта, поскольку на карту поставлены человеческие жизни. Алгоритмы сбалансированного дерева гораздо безопаснее, ведь они имеют гарантированную верхнюю границу времени поиска.

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

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

Дата добавления: 2021-04-24; просмотров: 56; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!