2.2 Функции хеширования
2.2.1 Как уже отмечалось, основная идея хеширования заключается в том, что элемент данных заносится в память по адресу, который легко вычислить, зная содержимое ключевого слова (КлСл), присвоенного этому элементу. На выбор КлСл не накладывается практически никаких ограничений: могут использоваться обычные имена или произвольные числовые коды (ЧК), причем к ним не требуется добавлять какие-нибудь контрольные метки или символы. Длина КлСл также выбирается произвольно, хотя в вычислениях участвуют обычно только несколько первых символов. В результате набор или область допустимых слов (т.е. пространство имен) оказывается весьма обширным. Например, количество слов, которые можно составить из шести букв английского алфавита = 256 млн. (? 300 млн.!) 
.
Первая мысль, которая приходит в голову при рассмотрении возможных вариантов преобразования пространства имен в пространство адресов (ПрИм > ПрАдр) – это желание осуществить тем или иным способом сжатие пространства имен (ПрИм). Коэффициент заполнения ПрИм в реальных условиях оказывается крайне малым. Поэтому хотелось бы подобрать такую функцию, у которой в области значений (совпадающей с адресным пространством) адреса распределялись бы более равномерно и с большей плотностью.
Если бы ключевым словам были поставлены в соответствие некоторые числовые значения v, случайно распределенные по закону, близкому к равномерному, то задача решалась бы достаточно просто.
Обозначим F(v) интегральную функцию распределения случайной переменной v. Если в качестве хеш-адреса, соответствующего данному v, взять величину 
, где
H – общее количество допустимых адресов;
B – первый адрес,
то на отрезке [B, B+H] хеш-адреса будут распределены равномерно.
К сожалению, такой подход связан с определенными сложностями:
Во-первых, ключевые слова – это, как правило, коды, элементам которых при переводе в числовую форму придают различные веса. Очень сомнительно, что бы получавшиеся в результате такого преобразования числа имели распределение, близкое к равномерному.
Во-вторых, таким способом нельзя устранить проблему коллизий, т.к. при сжатии в результате ошибок дискретизации могут появиться совпадающие адреса.
Позже мы посмотрим, что преобразование адресов может осуществляться проще и независимо от распределения ключевых слов. Поэтому методы сжатия рассматривать не будем.
Преобразование ключевых слов в допустимые адреса памяти в общем случае выполняется с помощью некоторой функции хеширования.
Содержимое ключа обозначим через k, а число h(k) назовем вычисленным адресом, или хеш-адресом.
Если двум разным ключам k1 и k2 соответствуют одинаковые адреса h(k1) = h(k2), то говорят, что возникла коллизия. При этом, для одного из конфликтующих элементов (обычно – второго) необходимо отыскать незанятый адрес, который нетрудно определить, зная вычисленный h(k1) – это может быть следующий за h(k1) или другой.
Если резервные ячейки помещаются в области памяти, адреса которой входят в область значений хеш-функции, то коллизии могут происходить и с резервными ячейками.
В принципе коллизии всегда устраняются одним способом независимо от того, где они возникли – по вычисленному или резервному адресу.
Если на ключевые слова не накладывается никаких ограничений, то можно сравнивать различные функции хеширования, исходя из способности минимизировать количество коллизий. В общем случае, хорошей функцией хеширования может считаться любая, обеспечивающая равномерное распределение вычисленных адресов внутри выделенной области памяти.
Процесс формирования хеш-функции включает обычно два этапа:
- выбор способа перевода ключевых слов в числовую форму;
- выбор алгоритма преобразования числовых значений в набор хеш-адресов.
2.2.2 Перевод ключевых слов в числовую форму
Всякая информация, вводимая в ЭВМ, должна быть тем или иным способом закодирована. Установлены стандартные форматы для кодирования чисел, букв, других символов на любых носителях (и в памяти). Данные между устройствами тоже передаются в форме специальных кодов.
Например, ASCII (Американский стандартный код обмена информацией), КОИ-8, ДКОИ и др.
В этих кодах все числа, буквы, символы представлены 8-ми разрядными цифрами (байт).
Для выполнения арифметических операций числа обычно преобразуются либо в двоичную, либо в двоично-десятичную форму. Учитывая, что все машинные переменные так или иначе представлены в числовой форме, то дополнительных преобразований проводить уже не надо.
Однако в некоторых алгоритмах, предназначенных для вычисления адресов, требуется, чтобы все исходные числовые величины располагались в пределах допустимого диапазона целых чисел в ЭВМ.
Как правило, ключевое слово представляет собой строку, состоящую из цифр, букв, или алфавитно-цифровых символов. В алфавит могут входить разные символы. Наиболее удобны алфавиты, включающие простое число символов. При проведении арифметических преобразований это число выступает в качестве основания системы счисления.
Предположим, что имеется алфавит, в котором каждому символу i согласно некоторому правилу поставлен в соответствии номер
di ? {0, 1, 2,…, W-1}.
Тогда строку, образованную из этих символов, и записанную в форме
k = dN ? dN-1 …d1?d0,
можно рассматривать как представление некоторого числа в системе с основанием W. Его значение определяется по формуле:
(1)
Возьмем, например, английский алфавит и следующим образом присвоим номера его буквам:
di = {A=0, B=1, …, Z=25}.
Тогда слову “ABE” соответствует числовое значение 0 ? 262 + 1 ? 261 + 4 ? 260 = 30.
Описанный метод дает хорошие результаты при переводе в числовую форму английских имен и слов.
Рассмотрим, каким способом в числовую форму, пригодную для хеширования, можно преобразовать индексные переменные. Такая проблема, в частности, возникает при разработке методов хранения и выборки разреженных матриц.
Разреженными называют такие матрицы, у которых только небольшая часть элементов отлична от нуля, причем эти ЭД ? 0 распределены внутри матрицы произвольным образом. Для того чтобы не расходовать машинную память на запись нулей, ненулевые элементы (ЭД ? 0) можно занести в хеш-таблицу, причем в этом случае пара индексов (i, j), указывающих позицию элемента в матрице, выступает в качестве ключевого слова.
Полагая, что i ? {1, 2,…, p} и j ? {1, 2,…, q}, мы можем получить числовое значение «ключевого слова» (i, j) при помощи одной из следующих двух формул:
v = i + q?(j – 1) – 1 или v = j + p?(i – 1) – 1 (2)
Адрес в хеш-таблице, по которому будет храниться ЭД (элемент матрицы), вычисляется в виде некоторой функции v точно также, как определяется хеш-функция символьной строки, если известно ее числовое значение v.
В рассмотренных методах перехода к числовой форме стремились получить распределение величин v, достаточно близкое к равномерному.
Однако в процедуре хеширования имеется и второй этап, связанный с преобразованием числовых значений v в пространстве хеш-адресов. В ходе этой операции осуществляется окончательная рандомизация адресов.
Рандомизация – метод преобразования ключа записи в адрес ее размещения во внутренней памяти, основанный на использовании генератора псевдослучайных чисел.
Качество результатов данного этапа в основном определяется свойствами функции хеширования.
Краткая «справка» по методам рандомизации
Основные методы:
- линейный;
- квадратичный;
- случайный.
Прежде, чем углубляться в дальнейшее обсуждение алгоритмов хеширования, целесообразно рассмотреть некоторые методы генерации псевдослучайных чисел.
Псевдослучайные числа имеют отношение к методам хеширования по двум причинам:
- хеш-адреса, получаемые как функции ключевых слов, сами по себе являются псевдослучайными числами;
- зависящие или не зависящие от значения ключа случайные числа используются в алгоритмах пробинга.
Наиболее важной характеристикой псевдослучайных чисел является степень корреляции между соседними элементами, величина которой должна быть, по возможности, минимальной.
Что касается метода хеширования, то он относится, по существу, к методу проб и ошибок. Поэтому качество псевдослучайных чисел для него особой роли не играет и влияет лишь на суммарное число проб. Определяющим здесь является быстродействие самого алгоритма хеширования, который должен выполняться с помощью минимального количества коротких (l) команд.
Последовательности псевдослучайных чисел, применяемые, например, в алгоритмах пробинга, обладают одним важнейшим свойством:
Если задано некоторое исходное число, то всякая последовательность, формируемая алгоритмом-генератором псевдослучайных чисел, полностью детерминирована. Это объясняется тем, что вычисление псевдослучайных чисел всегда производится по рекуррентной схеме, т.е. результаты, полученные на предыдущих шагах, используются в качестве параметров на последующих.
Известны несколько алгоритмов генерации псевдослучайных чисел.
Наиболее распространены основанные на так называемом мультипликативном сравнении.
Для выполнения операций хеширования могут применяться и специальные аппаратные средства. Наиболее известные способы аппаратной реализации генераторов псевдослучайных чисел:
- сдвиговый регистр со специальными обратными связями (по операции “исключающее ИЛИ” над двумя разрядами).
Другие методы хеширования
- метод деления
; - метод умножения;
- метод извлечения битов.
Один из старейших способов формирования хеш-функции:
- двоичное число, соответствующее хеш-адресу, образуется просто путем сцепления нужного количества битов, извлекаемых из определенных позиций внутри указанной битовой строки;
- метод квадрата (числовое значение ключевого слова v возводится в квадрат);
- метод сегментации (строка делится на сегменты, равные по длине хеш-адресу, и далее, различные сочетания и операции с сегментами);
- переход к новому основанию (системы счисления);
- алгебраическое деление (группирование ключевых слов, применение полиномов);
- оптимальные функции хеширования (попытки обобщить методы алгебраического кодирования);
- специальные методы хеширования (для решения задач классификации, сокращенные хеш-таблицы).