6.2. Выбор функции расстановки
 

При выборе функции расстановки f, отображающей множество ключей k в адреса а_i, i = 0, 1, ..., N - 1, где N — размер таблицы, желательно, чтобы она не только сокращала число коллизий, но не допускала скучивания ключей в отдельных частях таблицы. Поэтому ее подбирают из условия случайного и возможно более равномерного отображения ключей в адреса хранения. Таблицы, построенные по такому принципу, называют таблицами со случайным перемешиванием (хеш-таблицами), а вычисление адресов — хешированием.

Функция расстановки f(k) должна иметь значения между О и N -1. По этой причине ее часто определяют в виде f(k) = q(k) mod N, где q(k) — функция, принимающая целочисленные значения. Тогда существуют два вида коллизий:

а) непосредственные коллизии, соответствующие ключам к_i и k_j, таким, что q(k_i) = q(k_j), i! = j;
б) коллизии но модулю, порождаемые ключами к_i и k_j, такими, что q(k_i)! = q(k_j), но q(k_i)modN = q(k_j)modN, i! = j.

Существует правило Люма : доля коллизий по модулю уменьшается, если размером таблицы выбрать целое N, не имеющее делителей, меньших 20. N можно взять, например, простым, но это не обязательно.

Функция q(k) должна обеспечивать хорошее начальное распределение адресов по всей таблице. Для выбора такой функции нет готовых рецептов. Во многом это определяется решаемой задачей. Полезно построить несколько таких функций и моделировать их поведение при решении задачи.

Метод деления. В методе деления в качестве значения хеш-функции используется остаток от деления ключа на некоторое целое число М: А = kmodM или а = q(k)modM. Эффективность рассеивания по таблице во многом зависит от значения М. Плохо, если М является степенью основания системы счисления ключа или 2, при М = 2⁸ — это значение последнего символа при символьном ключе. Лучше, если М является простым числом. Очевидно, что в этом случае число возможных адресов равно М (0, 1, ..., М - 1), все ключи, равные (к + i*M), i = 0, 1, ..., будут конфликтными.

Рассмотрим таблицу, в которой в качестве ключей записей используются фами-лии студентов учебной группы. Используем для вычисления адреса входа в таблицу только первую букву фамилии (заглавная буква русского алфавита). В русском алфавите 32 буквы, коды прописных букв имеют значения С, = 128, 129, ..., 159. Если в качестве адреса взять а = C_i-128, то а = 0, 1, ..., 31. Если список учебной группы содержит всего 17 фамилий, то по методу деления адреса могут быть вычислены как a_i = (С_i-128)modl7. Фамилии, начинающиеся с А и С, Б и Т, ... будут конфликтными по модулю.

Очевидно, что для больших таблиц вычисление адреса по одной букве, когда число возможных адресов всего 32, мало подходит. Можно предложить такой подход. Рассматривая коды символов символьного ключа как целые без знака, находим сумму значений всех символов ключа и полученную сумму делим на число символов в ключе, затем целую часть частного делим на M и в качестве значения хеш-функции используем остаток от такого деления.

Метод умножения. Представим ключ в виде двоичною числа. Возьмем некоторую дробь р, умножим дробь р на k и возьмем дробную часть этого произведения (р*к). Затем умножим ее на М и возьмем целую часть. Хорошие результаты получаются, если в качестве р взять «золотое сечение», равное 0, 6180339887.

Рассмотренные два метода — метод деления и метод умножения, являются во многих случаях наилучшими.

Метод середины квадратов. Значение ключа представляется целым двоичным числом и возводится в квадрат. За адрес записи А принимается m бит средней части результата к². Этот метод очень близок методу умножения, однако по многим параметрам уступает ему.

Преобразование системы счисления. Пусть ключ выражен в некоторой р-ичной системе счисления: к = а₀ + а₁р + а₂р² + … . Функция t(k), используя те же коэффициенты а_i, в q-ичной системе счисления вычисляет значение полинома t(k) = a_o + а₁q+a₂q²+…+a_s-1q^s-1 для 5 младших цифр ключа, р и q — положительные числа, р < q, либо вычисляет t(k) с использованием всех коэффициентов, затем оставляют s младших цифр:
27130410 ≥ 2*13⁵ + 7*13⁴ +1*13³+3*13²+0*13+4*13⁰=945221, взяв, младшие 4 цифры, получим адрес 5221.

Метод слияния (метод свертки). Ключ разбивается на не¬сколько отрезков (частей) постоянной длины, затем эти части арифметически или логически склады-ваются. Символьные ключи перед разбивкой могут преобразоваться в двоичный код. Пример: ключ 271304 = > 271 + 304 = 575. Естественно, могут быть предложены другие способы разбивки на части.

Метод деления многочленов. Пусть к выражено в двоичной системе счисления к =b_n2ⁿ + b_n-1 2^n-1+…+b₀2⁰.

Используя те же коэффициенты, представим k в виде многочлена r(t) = b_ntⁿ+b_n-1t^n-1+…+b₀t⁰. Найдем остаток от деления r(t) на постоянный для всех ключей многочлен c(t): c(t) =c_mt^m+c_m-1t^m-1+…+c₁t+c₀.

Этот остаток, опять рассматриваемый в двоичной системе счисления, и используем в качестве значения A =f(k). Этот метод трудоёмок, поэтому находит реализацию аппаратным или микропрограммным способом.

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