После завершения операции поиска или вставки, программа выводит статус операции в нижней части формы — была ли операция успешной и число проверенных во время ее выполнения элементов.
В строке статуса также выводится средняя длина успешной (если элемент есть в таблице) и безуспешной (если элемента в таблице нет) тестовых последовательностей. Программа вычисляет эти значения, выполняя поиск для всех чисел между единицей и наибольшим числом в хеш‑таблице, и затем подсчитывая среднее значение длины тестовой последовательности.
На рис. 11.2 показано окно программы Chain после успешного поиска элемента 414.[RV17]
Другой способ разрешения конфликтов заключается в том, чтобы выделить ряд блоков, каждый из которых может содержать несколько элементов. Для вставки элемента в таблицу, он отображается на один из блоков и затем помещается в этот блок. Если блок уже заполнен, то используется обработка переполнения.
@Рис. 11.2. Программа Chain
======285
Возможно, самый простой метод обработки переполнения состоит в том, чтобы поместить все лишние элементы в специальные блоки в конце массива «нормальных» блоков. Это позволяет при необходимости легко увеличивать размер хеш‑таблицы. Если требуется больше дополнительных блоков, то размер массива блоков просто увеличивается, и в конце массива создаются новые дополнительные блоки.
Например, чтобы добавить новый элемент K в хеш‑таблицу, которая содержит пять блоков, вначале мы пытаемся поместить его в блок с номером K Mod 5. Если этот блок заполнен, элемент помещается в дополнительный блок.
Чтобы найти элемент в таблице, вычислим K Mod 5, чтобы найти его положение, и затем выполним поиск в этом блоке. Если элемента в этом блоке нет, и блок не заполнен, значит элемента в хеш‑таблице нет. Если элемента в блоке нет и блок заполнен, необходимо проверить дополнительные блоки.
На рис. 11.3 показаны пять блоков с номерами от 0 до 4 и один дополнительный блок. Каждый блок может содержать по 5 элементов. В этом примере в хеш‑таблицу были вставлены следующие элементы: 50, 13, 10 ,72, 25, 46, 68, 30, 99, 85, 93, 65, 70. При вставке элементов 65 и 70 блоки уже были заполнены, поэтому эти элементы были помещены в первый дополнительный блок.
Чтобы реализовать метод блочного хеширования в Visual Basic, можно использовать для хранения блоков двумерный массив. Если требуется NumBuckets блоков, каждый из которых может содержать BucketSize ячеек, выделим память под блоки при помощи оператора ReDim TheBuckets(0 To BucketSize -1, 0 To NumBuckets - 1). Второе измерение соответствует номеру блока. Оператор Visual Basic ReDim позволяет изменить только размер массива, поэтому номер блока должен быть вторым измерением массива.
Чтобы найти элемент K, вычислим номер блока K Mod NumBuckets. Затем проведем поиск в блоке до тех пор, пока не найдется искомый элемент, или пустая ячейка блока, или блок не закончится. Если элемент найден, поиск завершен. Если встретится пустая ячейка, значит элемента в хеш‑таблице нет, и процесс также завершен. Если проверен весь блок, и не найден искомый элемент или пустая ячейка, требуется проверить дополнительные блоки.
@Рис. 11.3. Хеширование с использованием блоков
======286
Public Function LocateItem(Value As Long, _
bucket_probes As Integer, item_probes As Integer) As Integer
Dim bucket As Integer
Dim pos As Integer
bucket_probes = 1
item_probes = 0
' Определить, к какому блоку он относится.
bucket = (Value Mod NumBuckets)
' Поиск элемента или пустой ячейки.
For pos = 0 To BucketSize - 1
item_probes = item_probes + 1
If Buckets(pos, bucket).Value = UNUSED Then
LocateItem = HASH_NOT_FOUND ' Элемент отсутствует.
Exit Function
End If
If Buckets(pos, bucket).Value = Value Then
LocateItem = HASH_FOUND ' Элемент найден.
Exit Function
End If
Next pos
' Проверить дополнительные блоки.
For bucket = NumBuckets To MaxOverflow
bucket_probes = bucket_probes + 1
For pos = 0 To BucketSize - 1
item_probes = item_probes + 1
If Buckets(pos, bucket).Value = UNUSED Then
LocateItem = HASH_NOT_FOUND ' Not here.
Exit Function
End If
If Buckets(pos, bucket).Value = Value Then
LocateItem = HASH_FOUND ' Элемент найден.
Exit Function
End If
Next pos
Next bucket
' Если элемент до сих пор не найден, то его нет в таблице.
LocateItem = HASH_NOT_FOUND
End Function
======287
Программа Bucket демонстрирует этот метод. Эта программа очень похожа на программу Chain, но она использует блоки, а не связные списки. Когда эта программа выводит длину тестовой последовательности, она показывает число проверенных блоков и число проверенных элементов в блоках. На рис. 11.4 показано окно программы после успешного поиска элемента 661 в первом дополнительном блоке. В этом примере программа проверила 9 элементов в двух блоках.
Многие запоминающие устройства, такие как стримеры, дисководы и жесткие диски, могут считывать большие куски данных за одно обращение к устройству. Обычно эти блоки имеют размер 512 или 1024 байта. Чтение всего блока данных занимает столько же времени, сколько и чтение одного байта.
Если имеется большая хеш‑таблица, записанная на диске, то этот факт можно использовать для улучшения производительности. Доступ к данным на диске занимает намного больше времени, чем доступ к данным в памяти. Если сразу загружать все элементы блока, то можно будет прочитать их все во время одного обращения к диску. После того, как все элементы окажутся в памяти, их проверка может выполняться намного быстрее, чем если бы пришлось их считывать с диска по одному.
Если для чтения элементов с диска используется цикл For, то Visual Basic будет обращаться к диску при чтении каждого элемента. С другой стороны, можно использовать оператор 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
Размещение в каждом блоке большего числа элементов позволяет считывать больше данных при каждом обращении к диску. При этом в таблице также может быть больше элементов, прежде чем будет необходимо использовать дополнительные блоки. Доступ к дополнительным блокам требует дополнительных обращений к диску, поэтому следует по возможности избегать его.