Приветствую

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

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

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

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

Спасибо!

Доброго времени суток!


У нас есть ключ, по которому мы легко можем найти данные.
Адресс = функция_от(ключа).
Как выбирать функцию - почитайте в Кнуте, там не много, но хорошо. Суть в том, что функция должна для разных клечей давать разные значения на ограниченом адресном пространстве. Но ничего идеального не бывает, поэтому случаются колизии: два разных ключа (аргумента) дают один адресс (значение функции). Тогда этот адрес на двоих указывает на список из елементов и время поиска уже не бедет О(1). В худшем варианте О(н). Да что я , том все написано. И Кнута, обязательно.

Если что, пишите - разберемся.

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

Приветствую.

Спасибо за ответы, Кнута обязательно скачаю. Какая книга, глава посвящена теории хеш-функций?

посмотрите вот здесь есть обширная подборка хеш функций с исходниками.
http://burtleburtle.net/bob/hash/

Knuth Vol 3 Sortig and seraching 6.4 Hashing