Выбор хеш-функции

Обратимся к вопросу, как выбрать хорошую хеш-функцию. Ясно, что она должна создавать как можно меньше коллизий при хешировании, т.е. она должна равномерно распределять ключи на имеющиеся индексы в массиве. Наиболее известная хеш-функция (которую мы использовали в вышеизложенных примерах) использует метод деления, при котором некоторый целый ключ делится на размер таблицы и остаток от деления берется в качестве значения хеш-функции. Она обозначается h(key)=mod(key, m). Предположим, что m равно 1000 и что все ключи оканчиваются на 3 одинаковые цифры (например, последние три цифры номера изделия означают номер завода-изготовителя). Тогда остаток от деления на 1000 для всех ключей будет одинаков, т.е. возникнут коллизии при хешировании для всех записей, кроме первой. Ясно, что при таком наборе ключей допуска должна использоваться другая хеш-функция [3].

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

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

Например, предположим, что внутреннее представление некоторого ключа в виде последовательности разрядов имеет вид 010111001010110 и для индекса отводится 5 разрядов. Над тремя последовательностями разрядов 01011, 10010 и 10110 выполняется операция сложения, что дает 01111 или двоичное представление числа 15.

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

Если ключи не являются числами, то они должны быть преобразованы в целые числа перед применением описанных выше хеш-функций. Для этого имеется несколько способов. Например, для строки символов в качестве двоичного числа может интерпретироваться внутреннее двоичное представление кода каждого символа. Недостатком этого является то, что для большинства ЭВМ двоичное представление букв и цифр очень похоже друг на друга. Если ключи состоят только их одних букв, то индекс каждой буквы в алфавите может использоваться для создания некоторого целого числа. Так, первая буква алфавита (А) представится цифрами 01, а 14-я буква (N) представляется цифрами 14. Ключ “Hello” представляется целым числом 0805121215. Когда существует некоторое целое представление строки символов, то для сведения его к приемлемому размеру может быть использован метод свертки или середины квадрата.