6.Хеширование

Цель: найти элементы, ключи которых соответствуют заданному ключу поиска

Прямая индексация(частный случай хеш-таблицы (h(k) = k)) Предположим, что каждый элемент имеет уникальный ключ

Идея: хранить данные в массиве, индексами которого являются ключи

Поиск элемента с заданным ключом – O(1)

Вставка элемента – O(1)

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

Храним таблицу длины m .

Хеш-функция (hash function) преобразует ключи в индексы таблицы h: U ® {0,1,…,m-1} , h(k) – хеш-значение (hash value)

Проблемы:

1.подобрать функцию h таким образом, чтобы минимизировать число коллизий

2.уметь разрешать имеющиеся коллизии

1.Хеш-функция должна (хотя бы приближенно) удовлетворять предположениям равномерного хеширования: для очередного ключа все m хеш-значений должны быть

равновероятны.

2.не должна коррелировать с закономерностями, встречающимися в хешируемых данных.

Хеш-функции:

Деление с остатком (division method, модульная функция).

h(k) = k mod m Хороший результат, если в качестве m брать простое число. Желательно не брать m = 2^p, 10^p

Умножение (multiplication method).

h(k) = [m{kA}] A - некоторая константа.

Разрешение коллизий методом цепочек

Пусть a - среднее количество элементов в одной цепочке

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

Теорема. Среднее время поиска элемента при хешировании с цепочками - O(1+ a) (a - среднее количество элементов в одной цепочке)