Вообше то это больше магия чем математика. Хеш функции и числа которые используются в них подбираются в зависимости от приложения где вы его используете. Если количество входных значений ограничено и заранее известно какое значение нужно выявить , то лучше , не использовать хеш а что то вроде perfect hashing как здесь
http://www.gnu.org/software/gperf/gperf.html.
Он анализирует входные значения и генерирует минимального размера код (на С ) для опознания входного значения из множества заданных значений.
Prime numbers, если не ошибаюсь это простые числа деляшиеся только на себя и на единицу. Они выбирайтуся на основе тестов результата хеш функции . Задаете тестовое множество вхопдных значений, рассчитываете ключи и вычисляете количество коллизий. При этом вычисления производите итерационно для каждого значения prime number. Впоследствии из этой статистики можно найти для какого prime числа количество коллизий наименьшее . Но это все магия )).
Допустим для одного приложения я использовал функцию Пирсона (из DHCP load balancing hash function). Сделал тест написанный выше и получилось что число используемое там не оптимально для моего множества входных данных. Собрав статистику изменяя prime number в алгоритме (если не ошибаюсь там было 31) нашел другое более оптимальное число .
Но кроме хеша есть еше и сортируюшие алгоритмы . Домустим на сонове дерева (balanced and unbalanced trees). Или же простейший алгоритм на основе алфавитного упорядочения или же его вариации .
Хеш функция должна выбираться на основе входных данных - их количества , возможного разброса значений. Ну а чтобы выбрать , надо их всех сколлекционировать, почитать их достоинства и недостатки и смоделировать тестом для случая вашего множества входных значений .
Knuth как отметили до меня содержит эту информацию . Буду дома, посмотрю что еше там есть .
hash-функции
Dec 29 2005, 14:19
я бы
