Пусть имеется n элементов а1, а2, а3,..., а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 именно в ней.
Получим следующую хеш-таблицу:
| индекс | ||||||||||
| ключ | 28 (h=9) | 15 (h=6) | 35 (h=6) | 17 (h=8) | 05 (h=6) | 19 (h=10) |
Для поиска любого из шести ключей в этой таблице потребуется в среднем (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) + i2) 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. Ну и, наконец – ложка дегтя в бочке меда: метод совершенно непригоден для обработки упорядоченных наборов.
Практические задания
Задание 1. Построить бесконфликтную хеш-таблицу для заданного набора текстовых ключей. Число ключей (и размер таблицы) равен 10. В качестве ключей взять 10 любых служебных слов языка Паскаль. Для преобразования текстовых ключей в числовые значения использовать суммирование кодов символов текстового ключа: код (End) = код (E) + код (n) + код (d). Преобразование числового кода ключа в значение индекса выполнить с помощью простейшей хеш-функции, которая берет остаток от целочисленного деления кода на размер хеш-таблицы (в задании – 10).
Для подсчета индексов ключей написать вспомогательную программу, которая в диалоге многократно запрашивает исходный текстовый ключ (служебное слово языка Паскаль) и подсчитывает значение хеш-функции. Программа должна вычислять длину очередного текстового ключа с помощью функции Length, в цикле вычислять сумму кодов всех символов ключа и брать остаток от деления этой суммы на 10.
Если некоторые исходные ключи будут конфликтовать друг с другом, можно изменить исходное слово, например – сменить регистр начальной буквы или всех букв в слове, полностью заменить слово на близкое по значению (End на Stop и.т.д.), ввести какие-либо спецсимволы или придумать другие способы
После подбора неконфликтующих ключей написать основную программу, которая должна:
· ввести подобранные ключи и расположить их в ячейках хеш-таблицы в соответствии со значением хеш-функции
· вывести хеш-таблицу на экран
· организовать циклический поиск разных ключей, как имеющихся в таблице (с выводом местоположения), так и отсутствующих: вычислить для ключа значение хеш-функции и сравнить содержимое соответствующей ячейки таблицы с исходным ключом
Задание 2. Реализовать метод внутреннего хеширования. Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа, для него ищется первое свободное по порядку место по формуле
j = ((h (ключ) + i) mod m) + 1, где i = 0, 1, 2,..., m-2
Программа должна выполнять следующие действия:
· добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений
· поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений
· вывод текущего состояния таблицы на экран
После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 10 ключей и разместить их поочередно в таблице размерности 11, 13 и 17. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии количества пустых мест в таблице на эффективность поиска.
Задание 3. Реализовать метод открытого хеширования. Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа этот ключ добавляется в конец вспомогательного списка. Это требует включения в каждую ячейку хеш-таблицы двух указателей на начало и конец вспомогательного списка.
Программа должна выполнять следующие действия:
· добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений
· поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений
· вывод текущего состояния таблицы на экран
· удаление заданного ключа из таблицы
Алгоритм удаления:
· вычислить хеш-функцию и организовать поиск удаляемого элемента в таблице
· если удаляемый элемент найден в ячейке таблицы, то эта ячейка либо становится пустой (если связанный с ней список пуст), либо в нее записывается значение из первого элемента списка с соответствующим изменением указателей
· если удаляемый элемент найден в списке, то производится его удаление с изменением указателей
После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 20 ключей и разместить их поочередно в таблице размерности 9, 17 и 23. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии размерности таблицы на эффективность поиска.
4.5. Контрольные вопросы по теме
1. В чем заключается метод хеш-поиска?
2. Для чего используется хеш-функция и какие к ней предъявляются требования?
3. Что такое хеш-таблица и как она используется?
4. Как по трудоемкости соотносятся между собой основные методы поиска (полный перебор, двоичный поиск, хеш-поиск)?
5. Как с помощью простейшей хеш-функции находится расположение в таблице строковых ключей?
6. Какие проблемы могут возникать при построении хеш-таблиц с произвольными наборами ключей?
7. В каких ситуациях можно построить бесконфликтную хеш-таблицу?
8. Где на практике и почему можно использовать бесконфликтные хеш-таблицы?
9. Что такое открытое хеширование и для чего оно применяется?
10. Какие структуры данных используются для реализации открытого хеширования?
11. Какие шаги выполняет алгоритм построения хеш-таблицы при открытом хешировании?
12. Какие шаги выполняет алгоритм поиска в хеш-таблице при открытом хешировании?
13. Какие проблемы могут возникать при использовании открытого хеширования?
14. Как влияет размер хеш-таблицы на эффективность открытого хеширования?
15. Что такое внутреннее хеширование и для чего оно применяется?
16. Какие правила можно использовать для поиска свободных ячеек при внутреннем хешировании?
17. Какие шаги выполняет алгоритм построения хеш-таблицы при внутреннем хешировании?
18. Какие шаги выполняет алгоритм поиска в хеш-таблице при внутреннем хешировании?
19. Как влияет размер хеш-таблицы на эффективность внутреннего хеширования?
20. В каких задачах НЕ следует применять метод хеш-поиска?