[romez777 0]

Приветствую

 

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

не разобраться.

 

Читал материалы на сайте http://algolist.manual.ru/ds/s_has.php не понял,

например такого: если хэш-функция должна минимизировать коллизии, то как

получается что элемент хэш-таблицы указывает на список элементов - ведь так

или иначе функция будет возвращать этот индекс многократно.

 

И еще: как вообще подбирается хэш-функция под задачу, в некоторых примерах

используются некие magic numbers, prime числа, для чего они нужны?

 

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

с удовольствием почитал.

 

Спасибо!

[mkalexey 0]

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

если хэш-функция должна минимизировать коллизии, то как

получается что элемент хэш-таблицы указывает на список элементов - ведь так

или иначе функция будет возвращать этот индекс многократно.

 

У нас есть ключ, по которому мы легко можем найти данные.

Адресс = функция_от(ключа).

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

 

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

[_artem_ 0]

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

[romez777 0]

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

 

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

[_artem_ 0]

посмотрите вот здесь есть обширная подборка хеш функций с исходниками.

http://burtleburtle.net/bob/hash/

 

Knuth Vol 3 Sortig and seraching 6.4 Hashing