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

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

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

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

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, _

Страницы: 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