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

[vak]

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

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

Comments

[vak]

Спасибо за ссылку, завтра попробую. Но, надо сказать, навороченный у мужика вариант. А ты его тестировал?

Кстати, хэш-функцию я изобретал для ассемблера БЭСМ-6. Для поиска имен в таблице. Воистину - программы живут дольше, чем машины. :)

[spamsink]

Он у нас работает практически со дня основания компании - точнее, с того момента, как хэш-функции в G++ extensions перестали нас устраивать. У меня CSE использует эту функцию - и ни одной коллизии на многие миллионы узлов. Проверь, кстати, все приведенные тобой функции на avalanche - интересно, что получится.

[vak]

А что такое avalanche?

[spamsink]

Там в одной из статей рассказывается. Avalanche - это когда изменение одного бита хэшируемого объекта приводит к изменению любого бита хэша со средней вероятностью 50%.

[spamsink]

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

[vak]

Ага, посмотрел. Но что-то лениво мне тестировать, своё любопытство я уже удовлетворил. :-)

Интересно, а как это будет по-русски? Есть такой термин в мат.физике - устойчивость. Это когда при малом изменении входных параметров результат тоже меняется несильно. А avalanche - это строго наоборот.