Лекции - Структуры и алгоритмы компьютерной обработки данных / 9.Хеширование. Методы устранения коллизий. Хеширование с открытой адресацией
.docХэширование (расстановка ключей)
Предположим, что все ключи у записей различны. Рассмотрим часто употребляемую структуру данных, которая называется хэш-таблицей.
В худшем случае добавление и поиск в хэш-таблице требуют столько же времени, что и в обычном списке Ө(n), но на практике можно добиться, чтобы среднее время добавления и поиска было постоянным Ө(1).
Ключи – целые числа
Хэш-таблица - обобщение обычного массива.
Предположим, что возможные значения ключа - целые числа из множества U={0,1, …, m-1}. Тогда можно завести массив T[0..m-1] для хранения записей, причем в ячейке с номером k будем хранить элемент с ключом k.
function Search(const T: DataSet; k:KeyType):Data;
begin
Search:=T[k];
end;
procedure Insert(var T: DataSet; x:Data);
begin
T[x.key]:=x;
end;
procedure Delete(var T: DataSet; x:Data);
begin
T[x.key]:=nil
end;
Вычислительная сложность всех операций Ө(1).
Общий случай
Если множество U возможных ключей так велико, что невозможно завести ячейку в массиве для каждого ключа, то применяют хэширование (от английского глагола to hash – «перемалывать»). Идея метода - сохранять указатель на элемент с
ключом k в ячейке H(k) в хэш-таблице T[0..m-1]. Здесь
H: U → {0 … m -1} - хэш-функция,
H(k) - хэш-ключ
Коллизии
Если значения хэш-функции для двух различных ключей совпадают, то говорят, что случилась коллизия. Избежать коллизий невозможно, ведь количество ключей значительно больше чем m. Ниже мы рассмотрим два способа разрешения коллизий: с помощью списков и открытой адресации.
Нужно стремиться, чтобы коллизий было минимальное количество. Для этого хэш-функция должна равномерно распределять значения ключей, то есть для любого ключа все m ее значений должны быть равновероятны.
Примеры хэш-функций
Пусть ключ - действительное число из полуинтервала [0,1). Тогда удобно использовать функцию
H(k) = [km].
Пусть ключ - натуральное число. Наиболее часто в качестве хэш-функции используют деление с остатком:
H(k) = k mod m.
Для получения более равномерного распределения рекомендуют выбирать простое m, далекое от степеней двойки.
Еще одна функция для натуральных ключей
H(k) = [m {k A} ].
Доналд Кнут в книге «Искусство программирования» анализирует различные значения A и рекомендует использовать «золотое сечение»
Если ключи имеют нечисловой тип данных, то сначала необходимо построить по ключу натуральное число, а затем применить одну из хэш-функций. Например, для строкового ключа можно посчитать сумму или более сложную функцию от кодов символов.
Разрешение коллизий с помощью списков
При использовании списков элементы множества с одинаковым значением хэш-функции ключа связываются в цепочку-список. Каждая ячейка хэш-таблицы содержит указатель на список. Операции добавления, поиска и удаления сводятся к операциям со списками.
Сложность операций
Проанализируем сложность операций. Наибольшее время занимает поиск: в худшем случае, когда искомый элемент не найден, количество операций ограничено длиной списка. Анализ алгоритма показывает, что при равномерном распределении элементов множества по ячейкам длина списка в среднем ограничена небольшой константой, а значит время поиска Ө(1). Аналогичное значение имеет сложность добавления.
Открытая адресация
При открытой адресации записи хранятся не в отдельных списках, а в самой хэш-таблице. Идея добавления при открытой адресации в том, что начиная от h(k) мы просматриваем ячейки в определенном порядке, пока не найдем ранее не занятую. При поиске ячейки просматриваются в том же порядке, пока элемент не будет найден, или не попадется пустая ячейка, означающая отсутствие элемента.
Для этого мы модифицируем хэш-функцию, добавляя второй аргумент - номер попытки. Последовательность номеров просматриваемых ячеек (последовательность проб) для ключа k имеет вид:
H(k,0),H(k,1),H(k,2), …, H(k,m-1).
Функция должна быть такой, чтобы каждое из чисел 0 … m-1 в этой последовательности встречалось только однажды.
Иллюстрация открытой адресации
Добавление при открытой адресации
Рассмотрим процедуру добавления при использовании открытой адресации. Введем переменные l - номер попытки, j - номер ячейки.
Procedure Insert (var T:DataSet; x:pData);
Var l,j: longint;
begin
l := 0;
repeat
j := H( x^.key, l );
if T[j] = nil then
begin
T[j] := x; exit
end;
l := l + 1
until l = m
end;
Аналогично выглядит процедура поиска. Поиск прекращается при достижении пустой ячейки. В этом случае запись не найдена.
Удаление при открытой адресации
Удалять элемент при открытой адресации путем обнуления ячейки нельзя, потому что тогда мы не сможем найти элементы с тем же значением хэш-функции ключа, которые добавлялись позже.
Возможное решение - использовать для удаляемой ячейки специальное значение Deleted (удалено). При добавлении такая ячейка считается пустой, а при поиске - занятой.
Методы открытой адресации
Линейное вычисление проб. В этом случае
H'(k,l)=(H(k)+l) mod m
Этот способ приводит к образованию длинных последовательностей идущих подряд занятых ячеек (кластеров), что увеличивает количество проб.
Квадратичное вычисление проб.
H'(k,l)=(H(k)+al2+bl) mod m.
При этом способе возможны случаи, когда последовательность проб не будет содержать все возможные ячейки.
Двойное хэширование.
H'(k,l)=(H1(k)+a H2(l)) mod m.
Этот способ дает наилучшие результаты.