2.4.26. Хэширование

Хэширование (hashing) – преобразование входной последовательности данных произвольной длины в выходную битовую строку фиксированной длины.

Такие преобразования также называются хэш-функциями или функциями свёртки, а их результаты называют хэшем, хэш-кодом или дайджестом сообщения (message digest).

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

Простейшими примерами хэш-функций может служить контрольная сумма.

В общем случае однозначного соответствия между исходными данными и хэш-кодом нет.

Поэтому существует множество массивов данных, дающих одинаковые хэш-коды – так называемые коллизии.

Вероятность возникновения коллизий играет немаловажную роль в оценке «качества» хэш-функций.

2.4.27. Хэш-таблицы

Хэш-таблица – это структура данных, реализующая интерфейс ассоциативного массива.

Она позволяет хранить пары (ключ, значение) и выполнять три операции:

• добавление новой пары по ключу;

• поиск пары по ключу;

• удаление пары по ключу.

Существует два варианта хэш-таблиц:

• с прямой адресацией;

• с открытой адресацией.

Хэш-таблица содержит некоторый массив H, элементы которого – это:

• пары (хэш-таблица с открытой адресацией);

• списки пар (хэш-таблица с прямой адресацией).

Выполнение операции в хэш-таблице начинается с вычисления хэш-функции от ключа.

Получающееся хэш-значение

i = hash(key)

играет роль индекса в массиве H.

Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива H[i].

Ситуация, когда для различных ключей получается одно и то же хэш-значение, называется коллизией (collision).

Число хранимых элементов делённое на размер массива H (число возможных значений хэш-функции) называется коэффициентом заполнения хэш-таблицы (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.

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

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

Существует несколько способов разрешения колизий.

Рассмотрим самые простые.

Прямая адресация

В массиве H хранятся списки пар. Коллизии просто приводят к тому, что появляются списки длиной более одного элемента. Когда количество таких списков достигает некоторого критического значения, может быть изменён некоторый параметр функции, отвечающий за диапазон генерируемых значений и плотность их распределения.

Массив H после этого должен быть реорганизован.

Открытая адресация

В массиве H хранятся сами пары. В случае возникновения коллизии, алгоритм поиска (удаления, добавления) объекта просто перемещается на ячейку вправо до момента разрешения коллизии.

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

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

2.4.28. Итог

Мы рассмотрели базовые подходы к физической организации файлов в реляционных БД.

В следующих темах мы рассмотрим более сложные «готовые решения».

2.5. Алгоритмы хэширования

2.5.1. Введение

Сейчас мы рассмотрим конкретные алгоритмы хэширования, применяемые для получения адресов записей в методах доступа реляционных СУБД.

2.5.2. Хэширование

Методы хэширования применяются для адресации данных, хранящихся на устройствах с произвольным доступом, начиная 50-х годов прошлого века.

Процесс хэширования вначале назывался рандомизацией (randomising). Это вызвано тем, что процессу преобразования ключа в адрес вначале пытались придать чисто случайный (random) характер, пока не выяснилось, что этот процесс не может и не должен быть случайным.

Методы хэширования и их применение являются довольно простыми и, кроме того, они имеют два существенных преимущества по сравнению с методами индексирования.

1. Большинство записей можно найти в результате одного обращения к внешнему запоминающему устройству.

2. Включение и удаление записей осуществляются сравнительно легко.

Однако индексирование успешно применяется в файлах, упорядоченных по тому или иному ключу, где показывает высокую эффективность.

В настоящее время известно много различных методов хэширования в применении к СУБД.

Мы же рассмотрим основные…