hash-функции Опции

[romez777]

Приветствую

Приступил к изучению hash-функций и сразу завяз, столько много методов и сразу
не разобраться.

Читал материалы на сайте http://algolist.manual.ru/ds/s_has.php не понял,
например такого: если хэш-функция должна минимизировать коллизии, то как
получается что элемент хэш-таблицы указывает на список элементов - ведь так
или иначе функция будет возвращать этот индекс многократно.

И еще: как вообще подбирается хэш-функция под задачу, в некоторых примерах
используются некие magic numbers, prime числа, для чего они нужны?

Если есть доступное описание без особого углубления в математику я бы
с удовольствием почитал.

Спасибо!

[_artem_]

Вообше то это больше магия чем математика. Хеш функции и числа которые используются в них подбираются в зависимости от приложения где вы его используете. Если количество входных значений ограничено и заранее известно какое значение нужно выявить , то лучше , не использовать хеш а что то вроде 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 как отметили до меня содержит эту информацию . Буду дома, посмотрю что еше там есть .