Хеширование (hashing) — использование хэш-функций, которые вычисляют вес строки таблицы по значению ее ключевых атрибу­тов. Результат вычисления хэш-функции — целое число в диапазоне физических номеров строк таблицы.

 

Идеальная хэш-функция должна давать разные значения весов для разных ключевых атрибутов. Но это не всегда возможно. На практике обычно используют простые хэш-функции, например, f(k) = kmodp, где k — целое число, первичный ключ отношения; р — простое целое число; mod — операция, вычисляющая остаток при целочисленном делении. Если ключевой атрибут — строка символов, то для вычисления f(k) выбирается один из методов пре­образования строки в число, например вычисление контрольной суммы.
 

Для организации доступа к данным при хешировании создается таблица с пустыми строками, которая заполняется следующим об­разом:

• по первичному ключу новой строки вычисляется значение хэш-функции f(k) и результат трактуется, как номер строки в созданной таблице;

• если строка уже занята, производится проверка следующих строк по специальному алгоритму до тех пор, пока не будет обнаружено свободное место.

Аналогично производится поиск нужной строки:

• если после вычисления/(/с) на месте в таблице, которое соот­ветствует вычисленному значению, оказывается пустая строка, значит, искомой строки просто нет;

• иначе (строка занята);

• если значение ключа совпало с искомым, поиск заканчива­ется;

• иначе (значение не совпало) — проверяются следующие стро­ки до строки с нужным ключом — строка найдена или до пус­той строки — строка отсутствует.

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