Эффективные хэш-функции

[vak]

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

Собрал я в кучу несколько вариантов и потестировал. Один из вариантов - самопальный, придуманный в далеком студенчестве. Оказывается, неплохо работает.

Comments

[vak]

Похоже, я изобрел гениальный алгоритм для хэш-функции: http://vak.ru/doku.php/proj/hash/sources#shift_hash_function
Всего один сдвиг и сложение, а по конфликтам в два раза лучшее остальных. Или я чего-то не дотумкиваю?

[spamsink]

Сырое значение хэша обычно не используется. Для индексации в хэш-таблице используется какое-то подмножество битов хэша (или остаток от деления хэша на размер таблицы). Попробуй собрать статистику по распределению, скажем, младших 10 и младших 16 бит - интересно, у кого окажется наиболее равномерное.

[spamsink]

Или, скажем, остатки от деления на 10007 или 65521.

[vak]

Попробовал - чистый Пуассон получается. Для всех хэш-функций примерно одинаково, график совершенно неинтересный: http://vak.ru/lib/exe/detail.php/proj/hash/coll-dens.png

Все-таки распределение у всех достаточно равномерое.