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

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

В рассмотренных ранее алгоритмах поиска(по списку по дереву) число операции в лучшем случае было пропорционально (log n) Возникает желание найти такой алгоритм который мог бы найти элемент за число шагов независящих.

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

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

В большинстве задач размер пр-ва записи намного меньше размера 

Так например если в качестве ключа  используется строка состоящая из 10 символов кириллицы, размер пространства ключей = 0.33 Даже если ресурсы системы позволяют выделить такой объем памяти то значительная ее часть будет заполнена пустыми записями. Так как в каждом конкретном заполнении таблицы фактическое множество ключей не будет полностью покрывать пространство. Из соображения экономии целесообразно назначать размер пр-ва записи равным размеру фактическому кол-ву записей или значительно больше. В этом случае необходимо иметь функцию обеспечивающую точку из пространства записи, т.е. преобразование ключа в адрес записи.

A=h(k)

Идеальной хеш-памятью является такая функция, которая для любых 2 неодинаковых ключей дает неодинаковые адреса. При попытке отображения из некоторого широкого пр-ва в узкое неизбежна ситуация,  когда разные точки в исходном пр-ве отобразятся в одну точку. Ситуация в которой разные ключи отображаются в один и тот же адрес памяти называется - коллизией (переполнение), а такие ключи – синонимами. Поскольку хеш-функция преобразующая ключ матриц может порождать коллизию то Х однозначно обратной функции позволяет восстановить ключ … поэтому ключ должен входить в состав матрицы.

Хеш- функции в общем случае предъявляют след требования:

1 должна обеспечивать равномерное  обеспечение ключей .

2 должна порождать как можно меньше коллизий для данного фактического множества.

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

4 должна быть простой и быстрой  для вычисления.

Хеш функции:

- Функция середины квадрата (значение  ключа преобразуется в число это число возводится в квадрат и из этого квадрат выбирается несколько средних цифр)

- Функция свертки (цифровое представление  ключа- представляет на части каждой из которой имеет определенную длину, затем над производится матем. операция)

- Функция преобразование систем  счисления (ключ записанный как число в некоторой системе счисления с основанием P интерпретируется как число в системе счисления q где q>P это число переводится из системы q в систему p приводится к размеру пр-ва записи и интерпретируется в число)