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

[romez777]

Приветствую

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

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

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

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

Спасибо!

[mkalexey]

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

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

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

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