Hash-функции

Что делает hash-функцию хорошей? Скорость

Более быстрый чем бинарный поиск

Взаимосвязанность

Если у нас есть ключ K, тогда hash(K) всегда будет Возвращать одинаковый результат

Равномерное распределение

hash –функция должна равномерно распределять ключи Через все возможные индексы в массиве

Сделать хорошую хеш-функцию тяжело

С точки зрения практического применения, хорошей является такая хэш-функция,

которая удовлетворяет следующим условиям:

функция должна быть простой с

вычислительной точки зрения;

функция не должна отображать какую-

либо связь между значениями ключей в связь между значениями адресов;

функция должна минимизировать число

коллизий,то есть ситуаций, когда

разным ключам соответствует одно значение хэш-функции (ключи в этом

случае называются синонимами).

Хеширование данных

•Идеальной хеш-функцией является такая hash-функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса.

Hash Functions

•A collision occurs when h(x) maps two keys to the same location.

Оценка качества хеш-функции

Hash Tables

Проблемы хеширования

Хэш-таблицы не выдерживают порядка их внутренних элементов

Создать идеальную хэш-функцию практически невозможно

Collisions

Когда два различных ключа генерируют одинаковое значение хэш- это называется коллизия

hash(K1) == hash(K2)

Хеширование данных

Обработка коллизий

Метод Открытой Адресации

Если мы попытаемся вставить новый элемент и есть коллизия, будем перебирать хэш-таблицу,

пока не найдем свободное место

Реализация:

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

Все данные хранятся непосредственно в хэш-таблице. Дополнительные структуры данных не нужны.

Open Addressing (Linear Probing)

Start with an empty Hash Table

Data

0

1

2

3

4