Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
If cell.Value >= Value Then Exit Do
Set cell = cell.NextCell
Loop
If cell Is Nothing Then
LocateItemSorted = HASH_NOT_FOUND
ElseIf cell.Value = Value Then
LocateItemSorted = HASH_FOUND
Else
LocateItemSorted = HASH_NOT_FOUND
End If
End Function
Использование упорядоченных списков позволяет ускорить поиск, но не снимает настоящую проблему, связанную с переполнения таблицы. Лучшим, но более трудоемким решением будет создание хеш‑таблицы большего размера и повторное хеширование элементов в новой таблице так, чтобы связные списки в ней имели меньший размер. Это может занять довольно много времени, особенно если списки записаны на диске или каком‑либо другом медленном устройстве, а не в памяти.
========284
В программе Chain реализована хеш‑таблица со связыванием. Введите число списков в поле области Table Creation (Создание таблицы) на форме и установите флажок Sort Lists (Упорядоченные списки), если вы хотите, чтобы программа использовала упорядоченные списки. Затем нажмите на кнопку Create Table (Создать таблицу). Затем вы можете ввести новые значения и снова нажать на кнопку Create Table, чтобы создать новую хеш‑таблицу.
Так как интересно изучать хеш‑таблицы, содержащие большое число значений, то программа Chain позволяет заполнять таблицу случайными элементами. Введите число элементов, которые вы хотите создать и максимальное значение элементов в области Random Items (Случайные элементы), затем нажмите на кнопку Create Items (Создать элементы), и программа добавит в хеш‑таблицу случайно созданные элементы.
И, наконец, введите значение в области Search (Поиск). Если вы нажмете на кнопку Add (Добавить), то программа вставит элемент в хеш‑таблицу, если он еще не находится в ней. Если вы нажмете на кнопку Find (Найти), то программа выполнит поиск элемента в таблице.
После завершения операции поиска или вставки, программа выводит статус операции в нижней части формы — была ли операция успешной и число проверенных во время ее выполнения элементов.
В строке статуса также выводится средняя длина успешной (если элемент есть в таблице) и безуспешной (если элемента в таблице нет) тестовых последовательностей. Программа вычисляет эти значения, выполняя поиск для всех чисел между единицей и наибольшим числом в хеш‑таблице, и затем подсчитывая среднее значение длины тестовой последовательности.
На рис. 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
Страницы: 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
