Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Лекции - Структуры и алгоритмы компьютерной обработки данных / 9.Хеширование. Методы устранения коллизий. Хеширование с открытой адресацией

.doc
Скачиваний:
77
Добавлен:
06.02.2015
Размер:
207.87 Кб
Скачать

Хэширование (расстановка ключей)

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

В худшем случае добавление и поиск в хэш-таблице требуют столько же времени, что и в обычном списке Ө(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.

Этот способ дает наилучшие результаты.