VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

будет обращаться к диску при чтении каждого элемента. С другой стороны,

можно использовать оператор Visual Basic Get для чтения всего блока сразу.

При этом потребуется всего одно обращение к диску, и программа будет

выполняться намного быстрее.

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

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

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

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

возможности изменения размеров блоков ограничены по сравнению с предыдущим

вариантом алгоритма.

Global Const ITEMS_PER_BUCKET = 10 ' Число элементов в блоке.

Global Const MAX_ITEM = 9 ' ITEMS_PER_BUCKET - 1.

Type ItemType

Value As Long

End Type

Global Const ITEM_SIZE = 4 ' Размер данных этого типа.

Type BucketType

Item(0 To MAX_ITEM) As ItemType

End Type

Global Const BUCKET_SIZE = ITEMS_PER_BUCKET * ITEM_SIZE

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

произвольного доступа:

Open filename For Random As #DataFile Len = BUCKET_SIZE

=========288

@Рис. 11.4. Программа Bucket

Для удобства работы можно написать функции для чтения и записи блоков. Эти

функции читают и пишут данные в глобальную переменную TheBucket, которая

содержит данные одного блока. После того, как данные загружены в эту

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

Так как при произвольном обращении к файлу записи нумеруются с единицы, а

не с нуля, то эти функции должны добавлять к номеру блока в хеш-таблице

единицу перед считыванием данных из файла. Например, нулевому блоку в хеш-

таблице будет соответствовать запись с номером 1.

Private Sub GetBucket(num As Integer)

Get #DataFile, num + 1, TheBucket

End Sub

Private Sub PutBucket(num As Integer)

Put #DataFile, num + 1, TheBucket

End Sub

Используя функции GetBucket и PutBucket, можно переписать процедуру поиск в

хеш-таблице для чтения записей из файла:

Public Function LocateItem(Value As Long, _

bucket_probes As Integer, item_probes As Integer) As Integer

Dim bucket As Integer

Dim pos As Integer

item_probes = 0

' Определить, к какому блоку принадлежит элемент.

GetBucket Value Mod NumBuckets

bucket_probes = 1

' Поиск элемента или пустой ячейки.

For pos = 0 To MAX_ITEM

item_probes = item_probes + 1

If TheBucket.Item(pos).Value = UNUSED Then

LocateItem = HASH_NOT_FOUND ' Элемента нет в таблице.

Exit Function

End If

If TheBucket.Item(pos).Value = Value Then

LocateItem = HASH_FOUND ' Элемент найден.

Exit Function

End If

Next pos

' Проверить дополнительные блоки

For bucket = NumBuckets To MaxOverflow

' Проверить следующий дополнительный блок.

GetBucket bucket

bucket_probes = bucket_probes + 1

For pos = 0 To MAX_ITEM

item_probes = item_probes + 1

If TheBucket.Item(pos).Value = UNUSED Then

LocateItem = HASH_NOT_FOUND ' Элемента нет.

Exit Function

End If

If TheBucket.Item(pos).Value = Value Then

LocateItem = HASH_FOUND ' Элемент найден.

Exit Function

End If

Next pos

Next bucket

' Если элемент все еще не найден, его нет в таблице.

LocateItem = HASH_NOT_FOUND

End Function

Программа Bucket2 аналогична программе Bucket, но она хранит блоки на

диске. Она также не вычисляет и не выводит на экран среднюю длину тестовой

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

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

============290

Так как при обращении к блокам происходит чтение с диска, а обращение к

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

сильнее влияет на время выполнения программы, чем полное число проверенных

элементов. Для сравнения среднего числа проверенных блоков и элементов при

поиске элементов можно использовать программу Bucket.

Каждый блок в программе Bucket2 может содержать до 10 элементов. Это

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

переполнятся. В реальной программе следует попытаться поместить в блок

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

этом равным целому числу кластеров диска.

Например, можно читать данные блоками по 1024 байта. Если элемент данных

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

и при этом размер блока будет меньше 1024 байт.

Global Const ITEMS_PER_BUCKET = 23 ' Число элементов в блоке.

Global Const MAX_ITEM = 22 ' ITEMS_PER_BUCKET - 1.

Type ItemType

LastName As String * 20 ' 20 байт.

FirstName As String * 20 ' 20 байт.

EmloyeeId As Long ' 4 байта (это ключ).

End Type

Global Const ITEM_SIZE = 44 Размер данных этого типа.

Type BucketType

Item(0 To MAX_ITEM) As ItemType

End Type

Global Const BUCKET_SIZE = ITEMS_PER_BUCKET * ITEM_SIZE

Размещение в каждом блоке большего числа элементов позволяет считывать

больше данных при каждом обращении к диску. При этом в таблице также может

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

дополнительные блоки. Доступ к дополнительным блокам требует дополнительных

обращений к диску, поэтому следует по возможности избегать его.

С другой стороны, если блоки достаточно велики, то они могут содержать

большое число пустых ячеек. Если данные неравномерно распределены по

блокам, то одни блоки могут быть переполнены, а другие — практически пусты.

Использование другого варианта размещения с большим числом блоков меньшего

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

будут переполнены, а некоторые пусты, то почти пустые блоки будут иметь

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

На рис. 11.5 показаны два варианта расположения одних и тех же данных в

блоках. В расположении наверху используются 5 блоков, каждый из которых

содержит по 5 элементов. При этом дополнительные блоки не используются, и

всего имеется 12 пустых ячеек. Расположение внизу использует 10 блоков,

каждый из которых содержит по 2 элемента. В нем имеется 9 пустых ячеек и

один дополнительный блок.

========291

@Рис. 11.5. Два варианта расположения элементов в блоках

Это пример пространственно-временного компромисса. При первом расположении

все элементы расположены в обычных (не дополнительных) блоках, поэтому

можно быстро найти любой из них. Второе расположение занимает меньше места,

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

ним занимает больше времени.

Связывание блоков

Можно использовать другой подход, если при переполнении блоков создавать

цепочки из блоков. Для каждого заполненного блока создается своя цепочка

блоков, вместо того, чтобы хранить все лишние элементы в одних и тех же

дополнительных блоках. При поиске элемента в заполненном блоке нет

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

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

блоков переполнено, то это может сэкономить довольно много времени.

На рис. 11.6 показано применение двух разных схем хеширования для одних и

тех же данных. Вверху лишние элементы помещаются в общие дополнительные

блоки. Чтобы найти элементы 32 и 30, нужно проверить три блока. Во-первых,

проверяется блок, в котором элемент должен находится. Элемента в этом блоке

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

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

котором, наконец, находится искомый элемент.

В нижнем расположении заполненные блоки связаны со своими собственными

дополнительными блоками. При таком расположении любой элемент можно найти

после обращения не более чем к двум блокам. Как и раньше, вначале

проверяется блок, в котором элемент должен находиться. Если его там нет, то

проверяется связный список дополнительных блоков. В этом примере чтобы

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

=========292

@Рис. 11.6. Связные дополнительные блоки

Если дополнительные блоки хеш-таблицы содержит большое число элементов, то

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

много времени. Предположим, что имеется относительно большая хеш-таблица,

содержащая 1000 блоков, в каждом из которых находится 10 элементов.

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

для которых понадобится 100 дополнительных блоков. Чтобы найти один из

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

блок.

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

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

В этом случае пришлось бы проверить все 100 дополнительных блоков, прежде

чем выяснилось бы, что элемент отсутствует в таблице. Если программа часто

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

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

Если дополнительные блоки связаны между собой и ключевые значения

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

Если максимальное число дополнительных элементов для одного блока равно 10,

то каждый блок может иметь не больше одного дополнительного. В этом случае

можно найти элемент или определить, что его нет в таблице, проверив не

более двух блоков.

С другой стороны, если хеш-таблица только слегка переполнена, то многие

блоки будут иметь дополнительные блоки, содержащие всего один или два

элемента. Допустим, что в каждом блоке должно находиться 11 элементов. Так

как каждый блок может вместить только 10 элементов, для каждого обычного

блока нужно будет создать один дополнительный. В этом случае потребуется

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

элемент, и всего в дополнительных блоках будет 900 пустых ячеек.

Это еще один пример пространственно-временного компромисса. Связывание

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

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

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

разместив в ней все элементы таблицы.

=====293

Удаление элементов

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

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

таблицы. Если блок не заполнен, то на место удаленного элемента помещается

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

находиться в его начале. Тогда, если при поиске элемента в блоке позднее

найдется пустая ячейка, то можно будет заключить, что элемента в таблице

нет.

Если блок, содержащий искомый элемент, заполнен, то нужно провести поиск

заменяющего его элемента в дополнительных блоках. Если ни один из элементов

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

заменяется последним элементом в блоке, и последняя ячейка блока становится

пустой.

Иначе, если в дополнительном блоке существует элемент, который принадлежит

к данному блоку, то найденный элемент из дополнительного блока помещается

на место удаленного элемента. При этом в дополнительном блоке образуется

пустое пространство, но это легко исправить — в образовавшуюся пустую

ячейку помещается последний элемент из последнего дополнительного блока.

На рис. 11.7 показан процесс удаления элемента из заполненного блока. Во-

первых, из блока 0 удаляется элемент 24. Так как блок 0 был заполнен, то

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

бы вставить на его место в блок 0. В данном случае блок 0 содержит все

четные элементы, поэтому любой четный элемент из дополнительных блоков

подойдет. Первый четным элементом в дополнительных блоках будет элемент 14,

поэтому можно заменить элементы 24 в блоке 0 элементом 14.

При этом в третьей позиции первого дополнительного блока образуется пустая

ячейка. Заполним ее последним элементом из последнего дополнительного

блока, в данном случае элементом 79. В этот момент хеш-таблица снова готова

к работе.

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

удаленный. Для поиска элементов в таком блоке нужно игнорировать удаленные

элементы. Если позднее в блок будут добавляться новые элементы, можно будет

помещать их на место элементов, помеченных как удаленные.

@Рис. 11.7. Удаление элемента из блока

=========294

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

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

ячейками. Если добавить в хеш-таблицу ряд элементов и затем удалить

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

элементов в блоках может оказаться «перевернутым». Большая часть настоящих

данных будет находиться в конце блоков и в дополнительных блоках. Добавлять

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

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

В качестве компромисса при удалении элемента из блока можно перемещать

последний элемент блока на освободившееся место и затем помечать последний

элемент блока как удаленный. Тогда при поиске в блоке можно прекратить

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

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

они существуют.

Преимущества и недостатки применения блоков

Вставка и удаление элемента в хеш-таблицу с блоками выполняется достаточно

быстро, даже если таблица почти заполнена. Фактически, хеш-таблица,

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

(связыванием из предыдущей главы, а не связыванием блоков). Если хеш-

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

обращение к диску весь блок. При использовании связных списков, следующий

элемент может находиться на диске не обязательно рядом с предыдущим. При

этом для каждой проверки элемента потребуется обращение к диску.

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

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

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

элемента, который нужно поместить на его место.

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

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

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

создать в его конце новый дополнительный блок.

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

часть данных может находиться в дополнительных блоках. Тогда для того,

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

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

хеш-таблицу с большим числом основных блоков и поместить элементы в нее.

Открытая адресация

Иногда элементы данных слишком велики, чтобы их было удобно размещать в

блоках. Если требуется список из 1000 элементов, каждый из которых занимает

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

бы более одного или двух элементов. Если каждый из блоков будет содержать

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

проверить множество блоков.

При использовании открытой адресации (open addressing) хеш-функция

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

массиве. Например, можно использовать в качестве хеш-таблицы массив с

нижним индексом 0 и верхним 99. Тогда хеш-функция может сопоставлять ключу

со значением K индекс массива, равный K Mod 100. При этом элемент со

значением 1723 окажется в таблице на 23 позиции. Затем, когда понадобится

найти элемент 1723, проверяется 23 позиция в массиве.

==========295

Различные схемы открытой адресации используют разные методы для

формирования тестовых последовательностей. В следующих разделах

рассматриваются три наиболее важных метода: линейная, квадратичная и

псевдослучайная проверка.

Линейная проверка

Если позиция, на которую отображается новый элемент в массиве, уже занята,

то можно просто просмотреть массив с этой точки до тех пор, пока не

найдется незанятая позиция. Этот метод разрешения конфликтов называется

линейной проверкой (linear probing), так как при этом таблица

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

Рассмотрим снова пример, в котором имеется массив с нижней границей 0 и

верхней границей 99, и хеш-функция отображает элемент K в позицию K Mod

100. Чтобы вставить элемент 1723, вначале проверяется позиция 23. Если эта

ячейка заполнена, то проверяется позиция 24. Если она также занята, то

проверяются позиции 25, 26, 27 и так далее до тех пор, пока не найдется

свободная ячейка.

Чтобы вставить новый элемент в хеш-таблицу, применяется выбранная тестовая

последовательность до тех пор, пока не будет найдена пустая ячейка. Чтобы

найти элемент в таблице, применяется выбранная тестовая последовательность

до тех пор, пока не будет найден элемент или пустая ячейка. Если пустая

ячейка встретится раньше, значит элемент в хеш-таблице отсутствует.

Можно записать комбинированную функцию проверки и хеширования:

Hash(K, P) = (K + P) Mod 100 где P = 0, 1, 2, ...

Здесь P — число элементов в тестовой последовательности для K. Другими

словами, для хеширования элемента K проверяются элементы Hash(K, 0),

Hash(K, 1), Hash(K, 2), … до тех пор, пока не найдется пустая ячейка.

Можно обобщить эту идею для создания таблицы размера N на основе массива с

индексами от 0 до N - 1. Хеш-функция будет иметь вид:

Hash(K, P) = (K + P) Mod N где P = 0, 1, 2, ...

Следующий код показывает, как выполняется поиск элемента при помощи

линейной проверки:

Public Function LocateItem(Value As Long, pos As Integer, _

probes As Integer) As Integer

Dim new_value As Long

probes = 1

pos = (Value Mod m_NumEntries)

Do

new_value = m_HashTable(pos)

' Элемент найден.

If new_value = Value Then

LocateItem = HASH_FOUND

Exit Function

End If

' Элемента в таблице нет.

If new_value = UNUSED Or probes >= NumEntries Then

LocateItem = HASH_NOT_FOUND

pos = -1

Exit Function

End If

pos = (pos + 1) Mod NumEntries

probes = probes + 1

Loop

End Function

Программа Linear демонстрирует открытую адресацию с линейной проверкой.

Заполнив поле Table Size (Размер таблицы) и нажав на кнопку Create table

(Создать таблицу), можно создавать хеш-таблицы различных размеров. Затем

можно ввести значение элемента и нажать на кнопку Add (Добавить) или Find

(Найти), чтобы вставить или найти элемент в таблице.

Чтобы добавить в таблицу сразу несколько случайных значений, введите число

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

могут иметь в области Random Items (Случайные элементы), и затем нажмите на

кнопку Create Items (Создать элементы).

После завершения программой какой-либо операции она выводит статус операции

(успешное или безуспешное завершение) и длину тестовой последовательности.

Она также выводит среднюю длину успешной и безуспешной тестовой

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

последовательности, выполняя поиск всех значений от 1 до максимального

значения в таблице.

В табл. 11.1 приведена средняя длина успешных и безуспешных тестовых

последовательностей, полученных в программе Linear для таблицы со 100

ячейками, элементы в которых находятся в диапазоне от 1 до 999. Из таблицы

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

Является ли производительность приемлемой, зависит от того, как

используется таблица. Если программа тратит большую часть времени на поиск

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

неплохой, даже если таблица практически заполнена. Если же программа часто

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

очень низкой, если таблица переполнена.

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

расходуя при этом слишком много памяти, если заполнено от 50 до 75

процентов таблицы. Если таблица заполнена больше, чем на 75 процентов, то

производительность падает. Если таблица заполнена меньше, чем на 50

процентов, то она занимает больше памяти, чем это необходимо. Это делает

открытую адресацию хорошим примером пространственно-временного компромисса.

Увеличивая хеш-таблицу, можно уменьшить время, необходимое для вставки или

поиска элементов.

=======297

@Таблица 11.1. Длина успешной и безуспешной тестовых последовательностей

Первичная кластеризация

Линейная проверка имеет одно неприятное свойство, которое называется

первичной кластеризацией (primary clustering). После добавления большого

числа элементов в таблицу, возникает конфликт между новыми элементами и уже

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

кластер, чтобы найти пустую ячейку.

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

пустая хеш-таблица, которая может содержать N элементов. Если выбрать

случайное число и вставить его в таблицу, то вероятность того, что элемент

займет любую заданную позицию P в таблице, равна 1/N.

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

ту же позицию с вероятностью 1/N. Из-за конфликта в этом случае он

помещается в позицию P + 1. Также существует вероятность 1/N, что элемент и

должен располагаться в позиции P + 1, и вероятность 1/N, что он должен

находиться в позиции P - 1. Во всех этих трех случаях новый элемент

располагается рядом с предыдущим. Таким образом, в целом существует

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

друга, образуя небольшой кластер.

По мере роста кластера вероятность того, что следующие элементы будут

располагаться вблизи кластера, возрастает. Если в кластере находится два

элемента, то вероятность того, что очередной элемент присоединится к

кластеру, равна 4/N, если в кластере четыре элемента, то эта вероятность

равна 6/N, и так далее.

Что еще хуже, если кластер начинает расти, то его рост продолжается до тех

пор, пока он не столкнется с соседним кластером. Два кластера сливаются,

образуя кластер еще большего размера, который растет еще быстрее, сливается

с другими кластерами и образует еще большие кластеры.

======298

В идеальном случае хеш-таблица должна быть наполовину пуста, и элементы в

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

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

элемента. Также существует 50-процентная вероятность того, что он найдет

пустую ячейку после проверки всего лишь двух позиций в таблице. Средняя

длина тестовой последовательности равна 0,5 * 1 + 0,5 * 2 = 1,5.

В наихудшем случае все элементы в таблице будут сгруппированы в один

гигантский кластер. При этом все еще есть 50-процентная вероятность того,

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

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

шаге, то поиск свободной ячейки потребует гораздо больше времени. Если

элемент должен находиться на первой позиции кластера, то алгоритму придется

проверить все элементы в кластере, чтобы найти свободную ячейку. В среднем

для вставки элемента при таком распределении потребуется гораздо больше

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

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

крайними случаями. Вы можете использовать программу Linear для исследования

эффекта кластеризации. Запустите программу и создайте хеш-таблицу со 100

ячейками, а затем добавьте 50 случайных элементов со значениями до 999. Вы

обнаружите, что образовалось несколько кластеров. В одном из тестов 38 из

50 элементов стали частью кластеров. Если добавить еще 25 элементов к

таблице, то большинство элементов будут входить в кластеры. В другом тесте

70 из 75 элементов были сгруппированы в кластеры.

Упорядоченная линейная проверка

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

можно остановить поиск, если найдется элемент со значением большим, чем

искомое. Так как при этом возможное положение искомого элемента уже позади,

значит искомый элемент отсутствует в списке.

Можно использовать похожую идею при поиске в хеш-таблице. Предположим, что

можно организовать элементы в хеш-таблице таким образом, что значения в

каждой тестовой последовательности находятся в порядке возрастания. Тогда

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

прекратить поиск, если встретится элемент со значением, большим искомого. В

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

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

Public Function LocateItem(Value As Long, pos As Integer, _

probes As Integer) As Integer

Dim new_value As Long

probes = 1

pos = (Value Mod m_NumEntries)

Do

new_value = m_HashTable(pos)

' Элемента в таблице нет.

If new_value = UNUSED Or probes > NumEntries Then

LocateItem = HASH_NOT_FOUND

pos = -1

Exit Function

End If

' Элемент найден или его нет в таблице.

If new_value >= Value Then Exit Do

pos = (pos + 1) Mod NumEntries

probes = probes + 1

Loop

If Value = new_value Then

LocateItem = HASH_FOUND

Else

LocateItem = HASH_NOT_FOUND

End If

End Function

Для того, чтобы этот метод работал, необходимо организовать элементы в хеш-

таблице так, чтобы при выполнении тестовой последовательности они

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

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

Когда в таблицу вставляется новый элемент, для него выполняется тестовая

последовательность. Если найдется свободная ячейка, то элемент вставляется

в эту позицию и процедура завершена. Если встречается элемент, значение

которого больше значения нового элемента, то они меняются местами и

продолжается выполнение тестовой последовательности для большего элемента.

При этом может встретиться элемент с еще большим значением. Тогда элементы

снова меняются местами, и выполняется поиск нового местоположения для этого

элемента. Этот процесс продолжается до тех пор, пока, в конце концов, не

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

местами.

========299-300

Public Function InsertItem(ByVal Value As Long, pos As Integer,_ probes

As Integer) As Integer

Dim new_value As Long

Dim status As Integer

' Проверить, заполнена ли таблица.

If m_NumUnused < 1 Then

' Поиск элемента.

status = LocateItem(Value, pos, probes)

If status = HASH_FOUND Then

InsertItem = HASH_FOUND

Else

InsertItem = HASH_TABLE_FULL

pos = -1

End If

Exit Function

End If

probes = 1

pos = (Value Mod m_NumEntries)

Do

new_value = m_HashTable(pos)

' Если значение найдено, поиск завершен.

If new_value = Value Then

InsertItem = HASH_FOUND

Exit Function

End If

' Если ячейка свободна, элемент должен находиться в ней.

If new_value = UNUSED Then

m_HashTable(pos) = Value

HashForm.TableControl(pos).Caption = Format$(Value)

InsertItem = HASH_INSERTED

m_NumUnused = m_NumUnused - 1

Exit Function

End If

' Если значение в ячейке таблицы больше значения

' элемента, поменять их местами и продолжить.

If new_value > Value Then

m_HashTable(pos) = Value

Value = new_value

End If

pos = (pos + 1) Mod NumEntries

probes = probes + 1

Loop

End Function

Программа Ordered демонстрирует открытую адресацию с упорядоченной линейной

проверкой. Она идентична программе Linear, но использует упорядоченную хеш-

таблицу.

В табл. 11.2 приведена средняя длина успешной и безуспешной тестовых

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

проверок. Средняя длина успешной проверки для обоих методов почти

одинакова, но в случае неуспеха упорядоченная линейная проверка выполняется

намного быстрее. Разница в особенности заметна, если хеш-таблица заполнена

более, чем на 70 процентов.

=========301

@Таблица 11.2. Длина поиска при использовании линейной и упорядоченной

линейной проверки

В обоих методах для вставки нового элемента требуется примерно одинаковое

число шагов. Чтобы вставить элемент K в таблицу, каждый из методов начинает

с позиции (K Mod NumEntries) и перемещается по таблице до тех пор, пока не

найдет свободную ячейку. Во время упорядоченного хеширования может

потребоваться поменять вставляемый элемент на другие в его тестовой

последовательности. Если элементы представляют собой записи большого

размера, то на это может потребоваться больше времени, особенно если записи

находятся на диске или каком-либо другом медленном запоминающем устройстве.

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

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

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

которых нет в таблице, или элементы таблицы имеют большой размер и

перемещать их достаточно сложно, то можно получить лучшую

производительность при использовании неупорядоченной линейной проверки.

Квадратичная проверка

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

использовать хеш-функцию следующего вида:

Hash(K, P) = (K + P2) Mod N где P = 0, 1, 2, ...

Предположим, что при вставке элемента в хеш-таблицу он отображается в

кластер, образованный другими элементами. Если элемент отображается в

позицию возле начала кластера, то возникнет еще несколько конфликтов

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

P в тестовой функции, значение этой функции быстро меняется. Это означает,

что позиция, в которую попадет элемент в конечном итоге, возможно, окажется

далеко от кластера.

=======302

На рис. 11.8 показана хеш-таблица, содержащая большой кластер элементов. На

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

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

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

прилегает к кластеру, поэтому после вставки этих элементов размер кластера

не увеличивается.

Следующий код демонстрирует поиск элемента с использованием квадратичной

проверки (quadratic probing):

Public Function LocateItem(Value As Long, pos As Integer, probes As

Integer) As Integer

Dim new_value As Long

probes = 1

pos = (Value Mod m_NumEntries)

Do

new_value = m_HashTable(pos)

' Элемент найден.

If new_value = Value Then

LocateItem = HASH_FOUND

Exit Function

End If

' Элемента нет в таблице.

If new_value = UNUSED Or probes > NumEntries Then

LocateItem = HASH_NOT_FOUND

pos = -1

Exit Function

End If

pos = (Value + probes * probes) Mod NumEntries

probes = probes + 1

Loop

End Function

Программа Quad демонстрирует открытую адресацию с использованием

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

квадратичную, а не линейную проверку.

В табл. 11.3 приведена средняя длина тестовых последовательностей,

полученных в программах Linear и Quad для хеш-таблицы со 100 ячейками,

значения элементов в которой находятся в диапазоне от 1 до 999.

Квадратичная проверка обычно дает лучшие результаты.

@Рис. 11.8. Квадратичная проверка

======303

@Таблица 11.3. Длина поиска при использовании линейной и квадратичной

проверки

Квадратичная проверка также имеет некоторые недостатки. Из-за способа

формирования тестовой последовательности, нельзя гарантировать, что она

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

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

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

Тестовая последовательность для числа 3 будет следующей:

3

3 + 12 = 4 = 4 (Mod 6)

3 + 22 = 7 = 1 (Mod 6)

3 + 32 = 12 = 0 (Mod 6)

3 + 42 = 19 = 1 (Mod 6)

3 + 52 = 28 = 4 (Mod 6)

3 + 62 = 39 = 3 (Mod 6)

3 + 72 = 52 = 4 (Mod 6)

3 + 82 = 67 = 1 (Mod 6)

3 + 92 = 84 = 0 (Mod 6)

3 + 102 = 103 = 1 (Mod 6)

и так далее.

Эта тестовая последовательность обращается к позициям 1 и 4 дважды перед

тем, как обратиться к позиции 3, и никогда не попадает в позиции 2 и 5.

Чтобы пронаблюдать этот эффект, создайте в программе Quad хеш-таблицу с

шестью ячейками, а затем вставьте элементы 1, 3, 4, 6 и 9. Программа

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

неиспользованными. Тестовая последовательность для элемента 9 не обращается

к элементам 2 и 5, поэтому программа не может вставить в таблицу новый

элемент.

=======304

Можно показать, что квадратичная тестовая последовательность будет

обращаться, по меньшей мере, к N/2 ячеек таблицы, если размер таблицы N —

простое число. Хотя при этом гарантируется некоторый уровень

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

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

случае сильно падает, то возможно лучше будет просто увеличить размер хеш-

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

найти свободную ячейку.

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

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

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

называется вторичной кластеризацией (secondary clustering). Если два

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

же тестовая последовательность. Если множество элементов отображаются на

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

по хеш-таблице. Если появляется новый элемент с тем же самым начальным

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15