Хеширование

Суть методов хеширования состоит в том, что мы берем значения ключа (или некоторые его характеристики) и используем его для начала поиска, то есть мы вычисляем некоторую хеш-функцию h(k) и полученное значение берем в качестве адреса начала поиска. То есть мы не требуем полного взаимно-однозначного соответствия, но, с другой стороны, для повышения скорости мы ограничиваем время этого поиска (количество дополнительных шагов) для окончательного получения адреса. Таким образом, мы допускаем, что нескольким разным ключам может соответствовать одно значение хеш-функции (один адрес). Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хеш-функции, называются синонимами. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Поэтому при использовании хеширования как метода доступа необходимо принять два независимых решения:

· Выбрать хэш-функцию;

· Выбрать метод разрешения коллизий.

Для ускорения доступа к данным в таблицах можно использовать предварительное упорядочивание таблицы в соответствии со значениями ключей.

Например, для ускорения доступа к данным в таблицах можно использовать предварительное упорядочивание таблицы в соответствии со значениями ключей. Для сокращения времени доступа к данным в таблицах используется случайное упорядочивание или хеширование. При этом данные организуются в виде таблицы при помощи хеш-функции h, используемой для вычисления адреса по значению ключа.

Идеальной хеш-функцией является такая hash-функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса. k1<>k2 => h(k1) <> h(k2). Подобрать такую функцию можно в случае, если все возможные значения ключей заранее известны. Такая организация данных носит название совершенное хеширование. В случае заранее неопределенного множества значений ключей и ограниченной длины таблицы подбор совершенной функции затруднителен. Поэтому часто используют хеш-функции, которые не гарантируют выполнение условия.