Преимущества и недостатки связывания

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

Из хеш‑таблицы, которая использует связывание, также просто удалять элементы, при этом элемент просто удаляется из соответствующего связного списка. В некоторых других схемах хеширования удалить элемент непросто или невозможно.

Один из недостатков связывания состоит в том, что если число связных списков недостаточно велико, то размер списков может стать большим, при этом для вставки или поиска элемента необходимо будет проверить большое число элементов списка. Если хеш‑таблица содержит 10 связных списков и к ней добавляется 1000 элементов, то средняя длина связного списка будет равна 100. Чтобы найти элемент в таблице, придется проверить порядка 100 ячеек.

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

 

Private Function LocateItemSorted(Value As Long) As Integer

Dim cell As ChainCell

 

' Получить вершину связного списка.

Set cell = m_ListTops(Value Mod NumLists).NextCell

Do While Not (cell Is Nothing)

   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

[RV18]

======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

 

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

С другой стороны, если блоки достаточно велики, то они могут содержать большое число пустых ячеек. Если данные неравномерно распределены по блокам, то одни блоки могут быть переполнены, а другие — практически пусты. Использование другого варианта размещения с большим числом блоков меньшего размера может уменьшить эту проблему. Даже если некоторые блоки все еще будут переполнены, а некоторые пусты, то почти пустые блоки будут иметь меньший размер, потому они не будут содержать так много пустых ячеек.

На рис. 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

 

Быстрее и легче вместо удаления элемента просто помечать его как удаленный, но, в конце концов, таблица может оказаться заполненной неиспользуемыми ячейками. Если добавить в хеш‑таблицу ряд элементов и затем удалить большинство из них в порядке первый вошел — первый вышел, то расположение элементов в блоках может оказаться «перевернутым». Большая часть настоящих данных будет находиться в конце блоков и в дополнительных блоках. Добавлять новые элементы в таблицу будет просто, но при поиске элемента довольно много времени будет тратиться на пропуск удаленных элементов.

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