3.5. Хеширование

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

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

Рассмотрим технологию хеширования на примере данных, приводимых в табл. 3.1. Используем для вычисления адресов страниц значения данных в поле первичного ключа таблицы Номер накладной: 18, 28, 37, 54, 60, 74, 80. Предположим, что на каждой странице внешней памяти можно разместить только одну запись.

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

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

Таблица 3.6

Сведения о поставках товаров в магазин

Номер накладной	Название товара	Артикул	Количество	Дата поставки	Адрес (номер страницы)
37	Костюм	500	50	10.12.05	4
54	Сапоги	200	75	10.12.05	10
18	Туфли	100	120	11.12.05	7
60	Костюм	500	35	11.12.05	5
28	Костюм	300	20	12.12.05	6
74	Костюм	400	50	12.12.05	8
80	Туфли	100	100	12.12.05	3

С помощью выполненного хеширования записи размещаются на семи страницах внешней памяти с адресами от 00 до 10.

Рассмотренный пример иллюстрирует и недостатки хеширования:

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

2. Возможно совпадение рассчитанных адресов страниц для двух или нескольких записей (например адреса, вычисленные для номеров накладных 18, 29, 40, будут равны одному числу – семи).

Совпадение вычисленных адресов называется коллизией, значения данных, для которых получены одинаковые адреса – синонимами.

Существует много стратегий разрешения коллизий, но основные из них две:

а) с областью переполнения;

б) свободного замещения.

Стратегия разрешения коллизий с помощью области переполнения

Область хранения разбивается на две части: основную область и область переполнения (рис. 6).

При вводе в базу данных новой записи вычисляется значение хеш-функции, которое используется для определения места расположения страницы в основной области памяти. Например, если номер накладной равен 12, запись будет размещена на странице с адресом 1 (см. обозначения курсивом на рис. 6).

Когда страница с полученным адресом занята и возникает коллизия, новая запись заносится на первое свободное место в области переполнения. Например, запись с номером накладной 29, следовательно, значением хеш-функции, равным 7, будет размещена по адресу 500. В записи-синониме, которая находится в основной области, делается ссылка на адрес записи, размещаемой в области переполнения. В ситуациях повторения коллизий (номер накладной равен 40, значение хеш-функции – 7) вновь вводимая запись помещается на свободное место в области переполнения (например, если страница с номером 501 занята, по адресу 502). Она становится второй в цепочке синонимов (этим обеспечивается сокращение времени на размещение новых записей) с помощью изменения ссылок на адреса синонимов (см. рис. 6).

При поиске нужной записи вычисляется значение ее хеш-функции, указывающее на адрес страницы в основной памяти. Если эта запись не является искомой, последовательно просматривается цепочка синонимов до получения необходимого результата. Очевидно, что скорость поиска существенно зависит от длины цепочки синонимов. Считается, что в цепочке не должно быть более 10 синонимов [ 4 ].

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

Основная область

Адрес (номер страницы)	Номер накладной	Название товара	Арти- кул	Коли-чество	Дата поставки	Ссылка на синонимы
0
1	12	Сапоги	150	150	13.12.05
2
3	80	Туфли	100	100	12.12.05
4	37	Костюм	500	50	10.12.05
5	60	Костюм	500	35	11.12.05
6	28	Костюм	300	20	12.12.05
7	18	Туфли	100	120	11.12.05	5 02
8	74	Костюм	400	50	12.12.05	5 01
9
10	54	Сапоги	200	75	10.12.05