Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Это еще один пример пространственно‑временного компромисса. Связывание блоков друг с другом позволяет быстрее вставлять и находить элементы, но оно также может заполнять хеш‑таблицу пустыми ячейками. Конечно, можно избежать этой проблемы, создав новую хеш‑таблицу большего размера и разместив в ней все элементы таблицы.
=====293
Удаление элементов
Удаление элементов из блоков сложнее, чем из связных списков, но оно возможно. Во‑первых, найдем элемент, который требуется удалить из хеш‑таблицы. Если блок не заполнен, то на место удаленного элемента помещается последний элемент блока, при этом все непустые ячейки блока будет находиться в его начале. Тогда, если при поиске элемента в блоке позднее найдется пустая ячейка, то можно будет заключить, что элемента в таблице нет.
Если блок, содержащий искомый элемент, заполнен, то нужно провести поиск заменяющего его элемента в дополнительных блоках. Если ни один из элементов в дополнительных блоках не принадлежит к данному блоку, то искомый элемент заменяется последним элементом в блоке, и последняя ячейка блока становится пустой.
Иначе, если в дополнительном блоке существует элемент, который принадлежит к данному блоку, то найденный элемент из дополнительного блока помещается на место удаленного элемента. При этом в дополнительном блоке образуется пустое пространство, но это легко исправить — в образовавшуюся пустую ячейку помещается последний элемент из последнего дополнительного блока.
На рис. 11.7 показан процесс удаления элемента из заполненного блока. Во‑первых, из блока 0 удаляется элемент 24. Так как блок 0 был заполнен, то нужно попытаться найти элемент из дополнительных блоков, который можно было бы вставить на его место в блок 0. В данном случае блок 0 содержит все четные элементы, поэтому любой четный элемент из дополнительных блоков подойдет. Первый четным элементом в дополнительных блоках будет элемент 14, поэтому можно заменить элементы 24 в блоке 0 элементом 14.
При этом в третьей позиции первого дополнительного блока образуется пустая ячейка. Заполним ее последним элементом из последнего дополнительного блока, в данном случае элементом 79. В этот момент хеш‑таблица снова готова к работе.
Другой метод состоит в том, чтобы вместо удаления элемента помечать его как удаленный. Для поиска элементов в таком блоке нужно игнорировать удаленные элементы. Если позднее в блок будут добавляться новые элементы, можно будет помещать их на место элементов, помеченных как удаленные.
@Рис. 11.7. Удаление элемента из блока
=========294
Быстрее и легче вместо удаления элемента просто помечать его как удаленный, но, в конце концов, таблица может оказаться заполненной неиспользуемыми ячейками. Если добавить в хеш‑таблицу ряд элементов и затем удалить большинство из них в порядке первый вошел — первый вышел, то расположение элементов в блоках может оказаться «перевернутым». Большая часть настоящих данных будет находиться в конце блоков и в дополнительных блоках. Добавлять новые элементы в таблицу будет просто, но при поиске элемента довольно много времени будет тратиться на пропуск удаленных элементов.
В качестве компромисса при удалении элемента из блока можно перемещать последний элемент блока на освободившееся место и затем помечать последний элемент блока как удаленный. Тогда при поиске в блоке можно прекратить дальнейший поиск в блоке, если при этом встретится элемент, помеченный, как удаленный. После этого можно провести поиск в дополнительных блоках, если они существуют.
Преимущества и недостатки применения блоков
Вставка и удаление элемента в хеш‑таблицу с блоками выполняется достаточно быстро, даже если таблица почти заполнена. Фактически, хеш‑таблица, использующая блоки, обычно будет быстрее, чем таблица со связыванием (связыванием из предыдущей главы, а не связыванием блоков). Если хеш‑таблица находится на диске, блочный алгоритм может считывать за одно обращение к диску весь блок. При использовании связных списков, следующий элемент может находиться на диске не обязательно рядом с предыдущим. При этом для каждой проверки элемента потребуется обращение к диску.
Удаление элемента из таблицы сложнее выполнить с использованием блоков, чем при применении связных списков. Чтобы удалить элемент из заполненного блока, может понадобиться проверить все дополнительные блоки в поиске элемента, который нужно поместить на его место.
И еще одно преимущество хеш‑таблицы, использующей блоки, состоит в том, что если таблица переполняется, то можно легко увеличить ее размер. Когда все дополнительные блоки заполнятся, можно просто изменить размер массива и создать в его конце новый дополнительный блок.
Если многократно увеличивать размер таблицы подобным образом, то большая часть данных может находиться в дополнительных блоках. Тогда для того, чтобы найти или вставить элемент, потребуется проверить множество блоков, и производительность упадет. В этом случае, может быть лучше создать новую хеш‑таблицу с большим числом основных блоков и поместить элементы в нее.
Открытая адресация
[RV19] Иногда элементы данных слишком велики, чтобы их было удобно размещать в блоках. Если требуется список из 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, 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
