[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 до максимального значения в таблице.
В табл. 11.1 приведена средняя длина успешных и безуспешных тестовых последовательностей, полученных в программе Linear для таблицы со 100 ячейками, элементы в которых находятся в диапазоне от 1 до 999. Из таблицы видно, что производительность алгоритма падает по мере заполнения таблицы. Является ли производительность приемлемой, зависит от того, как используется таблица. Если программа тратит большую часть времени на поиск значений, которые есть в таблице, то производительность может быть неплохой, даже если таблица практически заполнена. Если же программа часто ищет значения, которых нет в таблице, то производительность может быть очень низкой, если таблица переполнена.
Как правило, хеширование обеспечивает приемлемую производительность, не расходуя при этом слишком много памяти, если заполнено от 50 до 75 процентов таблицы. Если таблица заполнена больше, чем на 75 процентов, то производительность падает. Если таблица заполнена меньше, чем на 50 процентов, то она занимает больше памяти, чем это необходимо. Это делает открытую адресацию хорошим примером пространственно‑временного компромисса. Увеличивая хеш‑таблицу, можно уменьшить время, необходимое для вставки или поиска элементов.
=======297
@Таблица 11.1. Длина успешной и безуспешной тестовых последовательностей
Линейная проверка имеет одно неприятное свойство, которое называется первичной кластеризацией (primary clustering). После добавления большого числа элементов в таблицу, возникает конфликт между новыми элементами и уже имеющимися кластерами, при этом для вставки нового элемента нужно обойти кластер, чтобы найти пустую ячейку.
Чтобы увидеть, как образуются кластеры, предположим, что вначале имеется пустая хеш‑таблица, которая может содержать N элементов. Если выбрать случайное число и вставить его в таблицу, то вероятность того, что элемент займет любую заданную позицию P в таблице, равна 1/N.
При вставке второго случайно выбранного элемента, он может отобразиться на ту же позицию с вероятностью 1/N. Из‑за конфликта в этом случае он помещается в позицию P + 1. Также существует вероятность 1/N, что элемент и должен располагаться в позиции P + 1, и вероятность 1/N, что он должен находиться в позиции P - 1. Во всех этих трех случаях новый элемент располагается рядом с предыдущим. Таким образом, в целом существует вероятность 3/N того, что 2 элемента окажутся расположенными вблизи друг от друга, образуя небольшой кластер.
По мере роста кластера вероятность того, что следующие элементы будут располагаться вблизи кластера, возрастает. Если в кластере находится два элемента, то вероятность того, что очередной элемент присоединится к кластеру, равна 4/N, если в кластере четыре элемента, то эта вероятность равна 6/N, и так далее.
Что еще хуже, если кластер начинает расти, то его рост продолжается до тех пор, пока он не столкнется с соседним кластером. Два кластера сливаются, образуя кластер еще большего размера, который растет еще быстрее, сливается с другими кластерами и образует еще большие кластеры.
======298
В идеальном случае хеш‑таблица должна быть наполовину пуста, и элементы в ней должны чередоваться с пустыми ячейками. Тогда с вероятностью 50 процентов алгоритм сразу же найдет пустую ячейку для нового добавляемого элемента. Также существует 50‑процентная вероятность того, что он найдет пустую ячейку после проверки всего лишь двух позиций в таблице. Средняя длина тестовой последовательности равна 0,5 * 1 + 0,5 * 2 = 1,5.
В наихудшем случае все элементы в таблице будут сгруппированы в один гигантский кластер. При этом все еще есть 50‑процентная вероятность того, что алгоритм сразу найдет пустую ячейку, в которую можно поместить новый элемент. Тем не менее, если алгоритм не найдет пустую ячейку на первом шаге, то поиск свободной ячейки потребует гораздо больше времени. Если элемент должен находиться на первой позиции кластера, то алгоритму придется проверить все элементы в кластере, чтобы найти свободную ячейку. В среднем для вставки элемента при таком распределении потребуется гораздо больше времени, чем когда элементы равномерно распределены по таблице.
На практике, степень кластеризации будет находиться между этими двумя крайними случаями. Вы можете использовать программу Linear для исследования эффекта кластеризации. Запустите программу и создайте хеш‑таблицу со 100 ячейками, а затем добавьте 50 случайных элементов со значениями до 999. Вы обнаружите, что образовалось несколько кластеров. В одном из тестов 38 из 50 элементов стали частью кластеров. Если добавить еще 25 элементов к таблице, то большинство элементов будут входить в кластеры. В другом тесте 70 из 75 элементов были сгруппированы в кластеры.
При выполнении поиска в упорядоченном списке методом полного перебора, можно остановить поиск, если найдется элемент со значением большим, чем искомое. Так как при этом возможное положение искомого элемента уже позади, значит искомый элемент отсутствует в списке.
Можно использовать похожую идею при поиске в хеш‑таблице. Предположим, что можно организовать элементы в хеш‑таблице таким образом, что значения в каждой тестовой последовательности находятся в порядке возрастания. Тогда при выполнении тестовой последовательности во время поиска элемента можно прекратить поиск, если встретится элемент со значением, большим искомого. В этом случае позиция, в которой должен был бы находиться искомый элемент, уже осталась позади, и значит элемента нет в таблице.