Разрешение коллизий и структуры хеш-таблиц

Проблема, свойственная хеш-таблицам, заключается в том, что индексы (хеш-значения) нескольких разных ключей могут совпадать. Эта ситуация неизбежна, поскольку количество возможных значений ключей U значительно превышает размер хеш-таблицы. Такой случай называется коллизией или столкновением.

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

Хеш-таблица с цепочками коллизий (рис. 24) представляет собой массив списков коллизий. В позиции i массива хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно i. Если таких элементов в таблице нет, то позиция i содержит nil. Такой способ разрешения коллизий снимает ограничения на количество элементов, включённых в таблицу.

Рис. 24. Хеш-таблица с цепочками коллизий.

Хеш-таблица с открытой адресацией представляет собой массив Т, в который помещаются элементы таблицы по индексу, равному хеш-значению ключа. При возникновении коллизии выполняется поиск другой ячейки массива (зондирование), в которой может разместиться элемент. Эта ячейка должна быть свободной (открытой). Для пометки состояния в ячейки таблицы вводится специальный признак состояния ячейки state. Ячейка хеш-таблицы может быть в одном из трех состояний: свободна (free), занята (busy), свободна после удаления из неё элемента (deleted). Открытой считается ячейка, находящаяся в состоянии free или deleted.

При поиске свободной ячейки вычисляется и просматривается последовательность индексов ячеек массива. Последовательность зависит от ключа. k и номера попытки поиска i. Для вычисления последовательности к хеш-функции добавляется второй аргумент - номер попытки (нумерация начинается с 0). Последовательность ячеек для некоторого ключа k имеет вид <h (k, 0), h (k, 1), …, h (k, m-1)>.

Обычно используются три способа поиска свободных ячеек, называемых линейное зондирование, квадратичное зондирование и зондирование с двойным хешированием.

При линейном зондировании хеш-функция при каждой попытке поиска вычисляет новую ячейку по формуле

h (k, i) = (h(k) + i) mod m.

, где h(k)- обычная хеш-функция, i – номер попытки поиска свободной ячейки.

При работе с ключом k первой выбирается ячейка T [ h(k) ], а затем перебираются ячейки таблицы подряд: T [ h(k)+1 ], T [ h(k)+2 ], …. После ячейки T [ m-1 ] следует ячейка T [ 0 ]. У метода очевидный недостаток: он может привести к образованию кластеров – длинных последовательностей занятых ячеек, идущих подряд. Это удлиняет поиск.

При квадратичном зондировании хеш-функция, задаёт квадратичную последовательность ячеек по формуле:

h (k, i) = (h (k) + c₁ i + c₂ i ² ) mod m,

, где c ₁ ≠ 0 и c ₂ ≠ 0 – некоторые константы. Пробы начинаются с ячейки T [ h(k) ], но дальше ячейки просматриваются не подряд. Номер пробуемой ячейки квадратично зависит от номера попытки. Для того, чтобы использовались все ячейки таблицы, c ₁ и c ₂ нужно тщательно подбирать. Хорошую квадратичную последовательность проб даёт алгоритм, явно не использующий константы c ₁ и c ₂. Алгоритм продемонстрирован на примере вставки элемента в хеш-таблицу.

Hash_Insert (T, k)

j← h(k)

i← 0

while i ≠ m

do if T [j] = free or deleted

then T [j] = k

return j

i← (i + 1)

j← (j + i) mod m

error “Переполнение хеш-функции”

При квадратичном зондировании тенденция к образованию кластеров частично устраняется. Хотя и остается эффект кластеризации в более мягкой форме – образование вторичных кластеров.

Двойное хеширование – один из лучших методов открытой адресации. Последовательности индексов, возникающие при зондировании с двойным хешированием, близки к равномерному хешированию. При двойном хешировании функция h имеет вид:

h (k, i) = (h(k) + i h ₁ (k)) mod m

, где h(k) и h ₁ (k) – обычные хеш-функции. То есть, последовательность проб при зондировании является арифметической прогрессией по модулю m с первым членом h(k) и шагом h ₁ (k).

Чтобы последовательность зондируемых ячеек охватывала всю таблицу, значение h ₁ (k) должно быть взаимно простым с размером хеш-таблицы m. Простой способ добиться этого условия – выбрать в качестве m степень двойки, а функцию h ₁ (k) взять такую, чтобы она принимала только нечетные значения. В другом варианте, если m – простое число, значения h ₁ (k) - целые положительные числа, меньшие m. Например, если используется модульное хеширование, в котором размер хеш-таблицы выбирается, как простое число, то можно положить:

h (k) = k mod m

h ₁ (k) = 1 + (k mod m ₁ ),

, где m ₁ чуть меньше, чем m ( m ₁ = m-1 или m-2).

6.3. Трудоёмкость операций

Алгоритмы чтения или модификации, вставки и удаления элементов зависят от структуры хеш-таблицы. Если используется хеш-таблица с цепочками коллизий, то алгоритмы поиска, вставки и удаления элемента действуют по однотипной схеме:

· хеширование ключа элемента и вычисление индекса заголовка списка в массиве цепочек коллизий,

· поиск в списке элемента с заданным ключом,

· выполнение операции над элементом.

Трудоёмкость операций зависит от средней длины списков, которую можно вычислить как α = n/m, где n – число занесенных в таблицу элементов, m – размер хеш-таблицы. С учётом первоначального хеширования ключа перед просмотром списка оценку трудоёмкости можно записать, как O(1+α/2) [3]. Величина α учитывает фактор заполнения таблицы и называется коэффициентом заполнения таблицы. Трудоёмкость операций в хеш-таблице зависит не от числа элементов n, содержащихся в ней, а от коэффициента заполнения α. Для хеш-таблиц с цепочками коллизий величина α может быть меньше и больше единицы.

Зависимость трудоёмкости операций от заполнения справедлива и для хеш-таблиц с открытой адресацией. Чем более заполнена хеш-таблица, тем больше возникает коллизий и проб при зондировании. Приведённые в приложении 5 алгоритмы трёх основных операций для хеш-таблицы с открытой адресацией демонстрируют этот процесс.

Так же, как при анализе хеширования с цепочками коллизий, трудоёмкость операций с открытой адресацией оценивается в терминах коэффициента заполнения α. Для открытой адресации α ≤ 1. Анализ трудоёмкости операций для хеш-таблиц с открытой адресацией более сложен, чем для хеш-таблиц с цепочками коллизий [3, 4, 6]. Помимо коэффициента α трудоёмкость операции зависит от её алгоритма, метода зондирования, вероятности промахов операций. Поскольку в основе всех операций лежит определение наличия или отсутствия ключа в таблице, то трудоёмкость операций оценивается в количестве проб зондирования, выполненных при поиске ключа. Ниже приведены оценки трудоёмкости успешного или не успешного поиска ключа в зависимости от метода зондирования [4]:

Таблица 3

Метод зондирования	Успешный поиск ключа	Не успешный поиск ключа
Линейное зондирование	1/2 (1+ 1/(1- α))	(1/2 (1+ 1/(1- α))^2
Квадратичное зондирование	-ln(1- α)/ α	1/(1- α)
Зондирование с двойным хешированием	-ln(1- α)/ α	1/(1- α)

Обход хеш-таблицы заключается в просмотре элементов, хранящихся в хеш-таблице для выполнения над ними некоторой операции. Для хеш-таблиц с цепочками коллизий обход сводится к просмотру всех непустых списков. Поэтому трудоёмкость обхода можно оценить, как сумму длин просмотренных списков, которая равна числу элементов в таблице. То есть, трудоёмкость обхода имеет оценку O(n). В хеш-таблице с открытой адресацией ведётся поиск всех занятых ячеек, хранящих данные. Трудоёмкость просмотра соответствует размеру хеш-таблицы и выражается оценкой O(m).

---

Дата добавления: 2015-11-04