Хеш-функции
Хеш-функция должна отображать ключ в целое число из диапазона 0…n-1. При этом количество коллизий должно быть ограниченным, а вычисление самой хеш-функции – очень быстрым. Некоторые методы удовлетворяют этим требованиям.
Наиболее часто используется метод деления (division method), требующий двух шагов. Сначала ключ должен быть преобразован в целое число, а затем полученное значение вписывается в диапазон 0…n-1 с помощью оператора получения остатка. На практике метод деления используется в большинстве приложений, работающих с хешированием.
Предположим, что ключ – пятизначное число. Хэш-функция извлекает две младшие цифры. Например, если это число равно 56389, то HF(56389) = 89. Две младшие цифры являются остатком от деления на 100.
Эффективность хеш-функции зависит от того, обеспечивает ли она равномерное распределение ключей в диапазоне 0…n-1. Если две последние цифры соответствуют году рождения, то будет слишком много коллизий при идентификации подростков, играющих в юношеской бейсбольной лиге.
Другой пример – ключ-символьная строка С++. Хеш-функция отображает эту строку в целое число посредством суммирования первого и последнего символов и последующего вычисления остатка от деления на 101(размер таблицы).
Другой пример реализации хеш-функции, суммирование всех символов строки.
Лучшие результаты дает хеш-функция, производящая перемешивание битов в символах.
В общем случае при больших n индексы имеют больший разброс. Кроме того, математическая теория утверждает, что распределение будет более равномерным, если n – простое число.
Другие методы хеширования
Метод середины квадрата (midsquare technique) предусматривает преобразование ключа в целое число, возведение его в квадрат и возвращение в качестве значения функции последовательности битов, извлеченных из середины полученного числа. Предположим, что ключ есть целое 32-битное число. Тогда следующая хеш-функция извлекает средние 10 бит возведенного в квадрат ключа.
При мультипликативном методе (multiplicative method) используется случайное действительное число f в диапазоне от 0<f<1. Дробная часть произведения f * key лежит в диапазоне от 0 до 1. Если это произведение умножить на n (размер хеш-таблицы), то целая часть полученного произведения даст значение хеш-функции в диапазоне 0…n-1.
Выполнение работы:
1. Реализовать хэш-функцию методом деления (на 10 и 100).
2. Реализовать хэш-функцию суммированием первого и последнего символов и последующего вычисления остатка от деления на 101. Определить недостатки.
3. Реализовать хеш-функцию, суммированием всех символов строки. Определить недостатки.
4. Реализовать хэш-функцию методом середины квадрата.
5. Реализовать хэш-функцию мультипликативным методом.
