Хеширование

В прямом методе доступа рассматривается множество ключевых значений размером l байт, определённых на словаре V, и для каждого из возможных ключевых значений требуется отдельный физический адрес. Если в БД используется только N различных значений, то степень заполнения адресного пространства будет

При этом в прямом методе имеет место отображение 1:1.

В одном из альтернативных методов, именуемом «хеширование ключа», предпринимается попытка построить равномерное отображение множества значений в множество O(N) физических адресов и поэтому имеет место отображение m:1. При этом процедуру преобразования ключа в относительный или абсолютный физический адрес (хеш-адрес) называют функцией хеширования.

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

Особенности этой технологии можно сформулировать следующим образом:

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

- для сохранения записи в СУБД сначала вычисляется хеш-адрес новой записи, а затем диспетчер файлов помещает эту запись по вычисленному адресу;

- для извлечения нужной записи сначала по заданному значению хеш-поля в СУБД вычисляется хеш-адрес, а затем диспетчеру файлов посылается запрос для извлечения записи по вычисленному адресу.

Задачу хеширования ключа можно сформулировать следующим образом: пусть существует множество S элементов, характеризующихся значениями ключей K, и требуется отобразить эти ключи на заданном адресном пространстве A. Таким образом, следует подобрать такую функцию преобразования K®A, чтобы поиск элемента по адресу с заданным ключом характеризовался наименьшими затратами.

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

Наиболее популярными хеш-функциями являются функции класса «деление/остаток», так как они обладают устойчивой производительностью. Простейшая из этих функций имеет вид:

где M – размер адресного пространства, причём M должно быть простым натуральным числом, т. к. это приводит к более равномерному распределению.

Например, пусть имеются записи с данными о грузах Г100, Г200, Г300, Г400 и Г500 (вместо приведенных ранее Г1, Г2, Г3, Г4 и Г5 – см. п. 4.3.2), причём для хранения каждой из них предназначаются отдельные блоки. Если для хеширования избрать функцию

то номерами блоков соответственно будут Следовательно, данные о грузах будут размещены в блоках памяти со следующими адресами: запись с ключом Г100 будет иметь адрес блока 9, Г200 – 5 и т. д.

Поскольку в методе хеширования адрес является функцией от ключа и имеет место отображение m:1, то возможно возникновение аномальных ситуаций, именуемых также коллизиями. Коллизия – это ситуация, когда две и более различных записей имеют одинаковые адреса. Если в приведённом ранее примере таблицу грузов дополнить ещё одной записью с номером Г1400, то, вычисляя адрес её размещения, получаем что совпадает с адресом записи под номером Г100.

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