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

[vak]

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

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

Comments

[spamsink]

Все фигня. Сюда ходи: http://burtleburtle.net/bob/hash/index.html

[vak]

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

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

[spamsink]

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

[vak]

А что такое avalanche?

[spamsink]

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

[spamsink]

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

[vak]

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

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

[vak]

Потестировал, результаты хорошие - глянь у меня на страничке. Но не лучше остальных. :-/

В lookup3 нет умножения, вместо него на каждый байт приходится одно сложение и один сдвиг (в среднем). Плюс прочие навороты - на коротких строках эффективность снижается.

[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

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

[vak]

Все не так. Алгоритм со сдвигом плохо работает для данных с переменным старшим битом. Зато есть такой же алгоритм с циклическим сдвигом. Благо нынче GCC умный, сам понимает, что надо команду "rol" использовать.