Разрешение конфликтов: внутреннее хеширование

Пусть имеется n элементов а₁, а₂, а₃, . . ., а_n , на основе которых требуется построить хеш-таблицу, причем некоторые ключи могут конфликтовать между собой, претендуя на одну и ту же ячейку таблицы. Внутреннее хеширование для размещения конфликтующих ключей использует не вспомогательные списки, а свободные ячейки хеш-таблицы. Для этого размер таблицы обязательно должен быть больше числа элементов (m>n).

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

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

Самое простое правило заключается в последовательном круговом просмотревсех ячеек, начиная с индекса j, т. е. ячеек с номерами j+1, j+2, …, m-1, m, 1, 2, …, j-1.

Пример. Пусть задано 6 целочисленных ключей 15, 17, 19, 35, 05, 28. Построим на их основе хеш-таблицу размерности 10 с помощью простейшего правила определения свободных ячеек.

h (15) = 6, размещаем ключ 15 в ячейке 6

h (17) = 8, размещаем ключ 17 в ячейке 8

h (19) = 10, размещаем ключ 19 в ячейке 10

h (35) = 6, но ячейка 6 уже занята, проверяем следующую: ячейка 7 свободна, размещаем ключ 35 в ячейке 7

h (05) = 6, ячейка 6 занята, следующая ячейка 7 тоже занята, ячейка 8 – тоже, поэтому размещаем ключ 05 в ячейке 9

h (28) = 9, ячейка 9 занята, ячейка 10 занята и является последней, проверяем ячейку 1 и размещаем ключ 28 именно в ней.

Получим следующую хеш-таблицу:

Для поиска любого из шести ключей в этой таблице потребуется в среднем (1+2+1+4+1+6 = 15)/6 = 2,5 сравнений.

Для циклического вычисления индекса ключа а_k в простейшем случае можно использовать следующую простую формулу:

j = (h(а_k) + i) mod m) + 1, где i = 0, 1, 2, …, m-2

Здесь для целочисленных ключей h(а_k) = а_k.

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

Поэтому более эффективным является правило, которое позволяет выполнять “перепрыгивание” через несколько соседних ячеек. Например, можно воспользоваться следующей функцией вычисления индексов размещения ключей:

j = ((h (а_k) + i²) mod m) + 1, где i = 0, 1, 2, …, m-2

Эта функция дает не постоянный шаг приращения индекса (+1), а переменный: +1, +4, +9, +16 и т.д.

Алгоритм построения хеш-таблицы:

· находим значение хеш-функции для очередного ключа и по этому значению как индексу входим в таблицу

· если данная клетка таблицы пустая, то записываем в нее соответствующий ключ

· если ячейка занята, то сравниваем хранящийся там ключ с заданным ключом:

o если ключи совпадают, то каким-то образом обрабатываем повторный ключ (например, просто ничего не выполняем)

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

Алгоритм поиска:

· находим значение хеш-функции для искомого ключа и по этому значению как индексу входим в таблицу

· если ячейка с найденным индексом пустая, то поиск заканчивается неудачей

· если ячейка не пустая, то выполняем сравнение ключей:

o если ключи совпадают, то поиск заканчивается за одно сравнение

o если ключи не совпадают, то с помощью выбранного правила организуем циклический просмотр ячеек, который завершается либо при обнаружении свободной ячейки (поиск неудачен), либо по совпадению ключей (поиск удачен)

Эффективность внутреннего хеширования существенно зависит от наличия в хеш-таблице пустых ячеек, поэтому на практике идут на искусственное увеличение размерности таблицы на. 10-20% для обеспечения достаточного количества свободных клеток.

Многочисленные эксперименты показывают, что для заполненной на 50% таблицы (половина ячеек пустые) для поиска любого ключа в среднем требуется лишь 1,5 сравнения, причем это число не зависит от количества элементов. Это еще раз подтверждает высочайшую эффективность хеш-поиска!

В заключение дадим общие рекомендации по применению хеш-поиска.

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

2. Если набор ключей может меняться и заранее неизвестен, то важным становится выбор хеш-функции для равномерного распределения ключей по таблице. Одной из лучших хеш-функций считается следующая: исходный целочисленный ключ возводится в квадрат, преобразуется в двоичное представление в виде набора битов и из середины этого набора извлекается необходимое число битов в соответствии с размерностью таблицы (например, для таблицы размерности 1024 необходимо извлечь 10 битов)

3. При использовании открытого хеширования рекомендуется размер таблицы выбирать равным n/2, что в среднем должно обеспечивать короткие вспомогательные списки (1-2 элемента), которые могут просматриваться только последовательно

4. При использовании внутреннего хеширования рекомендуется размер таблицы выбирать равным 1,2*n для обеспечения достаточного количества свободных ячеек.

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

6. Некоторые сложности возникают при удалении элементов из хеш-таблицы, особенно – при использовании внутреннего хеширования, т.к. при этом за счет появления “незапланированных” пустых ячеек может нарушится работа алгоритма поиска

7. Ну и, наконец – ложка дегтя в бочке меда: метод совершенно непригоден для обработки упорядоченных наборов.