Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
На рис. 11.8 показана хеш‑таблица, содержащая большой кластер элементов. На нем также показаны тестовые последовательности, которые возникают при попытке вставить два различных элемента в позиции, занимаемые кластером. Обе эти тестовые последовательности заканчиваются в точке, которая не прилегает к кластеру, поэтому после вставки этих элементов размер кластера не увеличивается.
Следующий код демонстрирует поиск элемента с использованием квадратичной проверки (quadratic probing):
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 = (Value + probes * probes) Mod NumEntries
probes = probes + 1
Loop
End Function
Программа Quad демонстрирует открытую адресацию с использованием квадратичной проверки. Она аналогична программе Linear, но использует квадратичную, а не линейную проверку.
В табл. 11.3 приведена средняя длина тестовых последовательностей, полученных в программах Linear и Quad для хеш‑таблицы со 100 ячейками, значения элементов в которой находятся в диапазоне от 1 до 999. Квадратичная проверка обычно дает лучшие результаты.
@Рис. 11.8. Квадратичная проверка
======303
@Таблица 11.3. Длина поиска при использовании линейной и квадратичной проверки
Квадратичная проверка также имеет некоторые недостатки. Из‑за способа формирования тестовой последовательности, нельзя гарантировать, что она обойдет все ячейки в таблице, что означает, что иногда в таблицу нельзя будет вставить элемент, даже если она не заполнена до конца.
Например, рассмотрим небольшую хеш‑таблицу, состоящую всего из шести ячеек. Тестовая последовательность для числа 3 будет следующей:
3
3 + 12 = 4 = 4 (Mod 6)
3 + 22 = 7 = 1 (Mod 6)
3 + 32 = 12 = 0 (Mod 6)
3 + 42 = 19 = 1 (Mod 6)
3 + 52 = 28 = 4 (Mod 6)
3 + 62 = 39 = 3 (Mod 6)
3 + 72 = 52 = 4 (Mod 6)
3 + 82 = 67 = 1 (Mod 6)
3 + 92 = 84 = 0 (Mod 6)
3 + 102 = 103 = 1 (Mod 6)
и так далее.
Эта тестовая последовательность обращается к позициям 1 и 4 дважды перед тем, как обратиться к позиции 3, и никогда не попадает в позиции 2 и 5. Чтобы пронаблюдать этот эффект, создайте в программе Quad хеш‑таблицу с шестью ячейками, а затем вставьте элементы 1, 3, 4, 6 и 9. Программа определит, что таблица заполнена целиком, хотя две ячейки и остались неиспользованными. Тестовая последовательность для элемента 9 не обращается к элементам 2 и 5, поэтому программа не может вставить в таблицу новый элемент.
=======304
Можно показать, что квадратичная тестовая последовательность будет обращаться, по меньшей мере, к N/2 ячеек таблицы, если размер таблицы N — простое число. Хотя при этом гарантируется некоторый уровень производительности, все равно могут возникнуть проблемы, если таблица почти заполнена. Так как производительность для почти заполненной таблицы в любом случае сильно падает, то возможно лучше будет просто увеличить размер хеш-таблицы, а не беспокоиться о том, сможет ли тестовая последовательность найти свободную ячейку.
Не столь очевидная проблема, которая возникает при применении квадратичной проверки, заключается в том, что хотя она устраняет первичную кластеризацию, во время нее может возникать похожая проблема, которая называется вторичной кластеризацией (secondary clustering). Если два элемента отображаются в одну ячейку, для них будет выполняться одна и так же тестовая последовательность. Если множество элементов отображаются на одну из ячеек таблицы, они образуют вторичный кластер, который распределен по хеш‑таблице. Если появляется новый элемент с тем же самым начальным значением, для него приходится выполнять длительную тестовую последовательность, прежде чем он обойдет элементы во вторичном кластере.
На рис. 11.9 показана хеш‑таблица, которая может содержать 10 ячеек. В таблице находятся элементы 2, 12, 22 и 32, которые все изначально отображаются в позицию 2. Если попытаться вставить в таблицу элемент 42, то нужно будет выполнить длительную тестовую последовательность, которая обойдет все эти элементы, прежде чем найдет свободную ячейку.
Псевдослучайная проверка
Степень кластеризации растет, если в кластер добавляются элементы, которые отображаются на уже занятые кластером ячейки. Вторичная кластеризация возникает, когда для элементов, которые первоначально должны занимать одну и ту же ячейку, выполняется одна и та же тестовая последовательность, и образуется вторичный кластер, распределенный по хеш‑таблице. Можно устранить оба эти эффекта, если сделать так, чтобы для разных элементов выполнялись различные тестовые последовательности, даже если элементы первоначально и должны были занимать одну и ту же ячейку.
Один из способов сделать это заключается в использовании в тестовой последовательности генератора псевдослучайных чисел. Для вычисления тестовой последовательности для элемента, его значение используется для инициализации генератора случайных чисел. Затем для построения тестовой последовательности используются последовательные случайные числа, получаемые на выходе генератора. Это называется псевдослучайной проверкой (pseudo‑random probing).
Когда позднее требуется найти элемент в хеш‑таблице, генератор случайных чисел снова инициализируется значением элемента, при этом на выходе генератора мы получим ту же самую последовательность чисел, которая использовалась для вставки элемента в таблицу. Используя эти числа, можно воссоздать исходную тестовую последовательность и найти элемент.
@Рис. 11.9. Вторичная кластеризация
==========305
Если используется качественный генератор случайных чисел, то разные значения элементов будут давать различные случайные числа и соответственно разные тестовые последовательности. Даже если два значения изначально отображаются на одну и ту же ячейку, то следующие позиции в тестовой последовательности будут уже различными. В этом случае в хеш‑таблице не будет возникать первичная или вторичная кластеризация.
Можно проинициализировать генератор случайных чисел Visual Basic, используя начальное число, при помощи двух строчек кода:
Rnd -1
Randomize seed_value
Оператор Rnd дает одну и ту же последовательность чисел после инициализации одним и тем же начальным числом. Следующий кода показывает, как можно выполнять поиск элемента с использованием псевдослучайной проверки:
Public Function LocateItem(Value As Long, pos As Integer, _
probes As Integer) As Integer
Dim new_value As Long
' Проинициализировать генератор случайных чисел.
Rnd -1
Randomize Value
probes = 1
pos = Int(Rnd * 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 = Int(Rnd * m_NumEntries)
probes = probes + 1
Loop
End Function
=======306
Программа Rand демонстрирует открытую адресацию с псевдослучайной проверкой. Она аналогична программам Linear и Quad, но использует псевдослучайную, а не линейную или квадратичную проверку.
В табл. 11.4 приведена примерная средняя длина тестовой последовательности, полученной в программах Quad или Rand для хеш‑таблицы со 100 ячейками и элементами, значения которых находятся в диапазоне от 1 до 999. Обычно псевдослучайная проверка дает наилучшие результаты, хотя разница между псевдослучайной и квадратичной проверками не так велика, как между линейной и квадратичной.
Псевдослучайная проверка также имеет свои недостатки. Так как тестовая последовательность выбирается псевдослучайно, нельзя точно предсказать, насколько быстро алгоритм обойдет все элементы в таблице. Если таблица меньше, чем число возможных псевдослучайных значений, то существует вероятность того, что тестовая последовательность обратится к одному значению несколько раз до того, как она выберет другие значения в таблице. Возможно также, что тестовая последовательность будет пропускать какую‑либо ячейку в таблице и не сможет вставить новый элемент, даже если таблица не заполнена до конца.
Так же, как и в случае квадратичной проверки, эти эффекты могут вызвать затруднения, только если таблица почти заполнена. В этом случае увеличение таблицы дает гораздо больший прирост производительности, чем поиск неиспользуемых ячеек таблицы.
@Рис. 11.4. Длина поиска при использовании квадратичной и псевдослучайной проверки
=======307
Удаление элементов
Удаление элементов из хеш‑таблицы, в которой используется открытая адресация, выполняется не так просто, как удаление их из таблицы, использующей связные списки или блоки. Просто удалить элемент из таблицы нельзя, так как он может находиться в тестовой последовательности другого элемента.
Предположим, что элемент A находится в тестовой последовательности элемента B. Если удалить из таблицы элемент A, найти элемент B будет невозможно. Во время поиска элемента B встретится пустая ячейка, которая осталась после удаления элемента A, поэтому будет сделан неправильный вывод о том, что элемент B отсутствует в таблице.
Вместо удаления элемента из хеш‑таблицы можно просто пометить его как удаленный. Можно использовать эту ячейку позднее, если она встретится во время выполнения вставки нового элемента в таблицу. Если помеченный элемент встречается во время поиска другого элемента, он просто игнорируется и тестовая последовательность продолжится.
После того, как большое число элементов будет помечено как удаленные, в хеш‑таблице может оказаться множество неиспользуемых ячеек, и при поиске элементов достаточно много времени будет уходить на пропуск удаленных элементов. В конце концов, может потребоваться рехеширование таблицы для освобождения неиспользуемой памяти.
Рехеширование
Чтобы освободить удаленные элементы из хеш‑таблицы, можно выполнить ее рехеширование (rehashing) на месте. Чтобы этот алгоритм мог работать, нужно иметь какой‑то способ для определения, было ли выполнено рехеширование элемента. Простейший способ сделать это — определить элементы в виде структур данных, содержащих поле Rehashed.
Type ItemType
Value As Long
Rehashed As Boolean
End Type
Вначале присвоим полю Rehashed значение false. Затем выполним проход по таблице в поиске ячеек, которые не помечены как удаленные, и для которых еще не было выполнено рехеширование.
Если такой элемент встретится, то выполняется его удаление из таблицы и повторное хеширование, при этом выполняется обычная тестовая последовательность для элемента. Если встречается свободная или помеченная как удаленная ячейка, элемент размещается в ней, помечается как рехешированный, и продолжается проверка остальных элементов, для которых еще не было выполнено рехеширование.
Если при выполнении рехеширования найдется элемент, который уже был помечен как рехешированный, то тестовая последовательность продолжается. Если затем встретится элемент, для которого еще не было выполнено рехеширование, то элементы меняются местами, текущая ячейка помечается как рехешированная и процесс начинается снова.
======308
Изменение размера хеш‑таблиц
Если хеш‑таблица становится почти заполненной, производительность значительно падает. В этом случае может понадобиться увеличение размера таблицы, чтобы в ней было больше места для элементов. И наоборот, если в таблице слишком мало ячеек, может потребоваться уменьшить ее, чтобы освободить занимаемую память. Используя методы, похожие на те, которые использовались при рехешировании таблицы на месте, можно увеличивать и уменьшать размер хеш‑таблицы.
Чтобы увеличить хеш‑таблицу, вначале размер массива, в котором она находится, увеличивается при помощи оператора Dim Preserve. Затем выполняется рехеширование таблицы, при этом элементы могут занимать ячейки в созданной свободной области в конце таблицы. После завершения рехеширования таблица будет готова к использованию.
Чтобы уменьшить размер таблицы, вначале определим, сколько элементов должно содержаться в массиве таблицы после уменьшения. Затем выполняем рехеширование таблицы, причем элементы помещаются только в уменьшенную часть таблицы. После завершения рехеширования всех элементов, размер массива уменьшается при помощи оператора ReDim Preserve.
Следующий код демонстрирует рехеширование таблицы с использованием линейной проверки. Код для рехеширования таблицы с использованием квадратичной или псевдослучайной проверки выглядит почти так же:
Public Sub Rehash()
Dim i As Integer
Dim pos As Integer
Dim probes As Integer
Dim Value As Long
Dim new_value As Long
' Пометить все элементы как нерехешированные.
For i = 0 To NumEntries - 1
m_HashTable(i).Rehashed = False
Next i
' Поиск нерехешированных элементов.
For i = 0 To NumEntries - 1
If Not m_HashTable(i).Rehashed Then
Value = m_HashTable(i).Value
m_HashTable(i).Value = UNUSED
If Value <> DELETED And Value <> UNUSED Then
' Выполнить тестовую последовательность
' для этого элемента, пока не найдется свободная,
' удаленная или нерехешированная ячейка.
probes = 0
Do
pos = (Value + probes) Mod NumEntries
new_value = m_HashTable(pos).Value
' Если ячейка свободна или помечена как
' удаленная, поместить элемент в нее.
If new_value = UNUSED Or _
new_value = DELETED _
Then
m_HashTable(pos).Value = Value
m_HashTable(pos).Rehashed = True
Exit Do
End If
' Если ячейка не помечена как рехешированная,
' поменять их местами и продолжить.
If Not m_HashTable(pos).Rehashed Then
m_HashTable(pos).Value = Value
m_HashTable(pos).Rehashed = True
Value = new_value
probes = 0
Else
probes = probes + 1
End If
Loop
End If
End If
Next i
End Sub
Программа Rehash использует открытую адресацию с линейной проверкой. Она аналогична программе Linear, но позволяет также помечать объекты как удаленные и выполнять рехеширование таблицы.
Резюме
Различные типы хеш‑таблиц, описанные в этой главе, имеют свои преимущества и недостатки.
Для хеш‑таблиц, которые используют связные списки или блоки можно легко изменять размер таблицы и удалять из нее элементы. Использование блоков также позволяет легко работать с таблицами на диске, позволяя считать за одно обращение к диску сразу множество элементов данных. Тем не менее, оба эти метода являются более медленными, чем открытая адресация.
Линейная проверка проста и позволяет достаточно быстро вставлять и удалять элементы из таблицы. Применение упорядоченной линейной проверки позволяет быстрее, чем в случае неупорядоченной линейной проверки, установить, что элемент отсутствует в таблице. С другой стороны, вставку элементов в таблицу при этом выполнить сложнее.
Страницы: 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
