![]() |
![]() |
![]() | ||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
Содержание
Эффективность хэш-функций(Есть вариант этой статьи на английском языке) В статье Arash Partow "General Purpose Hash Function Algorithms" приведены восемь вариантов 32-битных хэш-функций:
Еще пять вариантов:
Тексты на языке Си можно посмотреть здесь. Тест номер 1Для проверки эффективности хэш-функций были выбраны следующие тестовые данные:
Общее количество после слияния — 326797 уникальных слов. При идеально равномерном распределении 32-битного хэша для достижения 50%-ной вероятности коллизии требуется 77163 слова. Так что коллизии должны иметь место. Для каждого из слов тестового наборы было вычислено 32-битное значение хэш-функции и подсчитано количество коллизий.
Список коллизий для rs, bkdr, sdbm, ap, ly, rot13, faq6, lookup3 и crc32 можно посмотреть здесь. Наиболее эффективные функции:
Результаты представлены на графике. Два явных аутсайдера — pjw и dek — выходят за пределы графика. Тест номер 2В предыдущем тесте данные имели общее свойство - неизменный старший бит каждого байта. Это могло повлиять на результат. Поэтому был проведен повторный тест, для которого были выбраны другие наборы данных:
Общее количество после слияния — 310595 уникальных слов. В тесте не участвовали алгоритмы js, pjw, djb и dek.
Наиболее эффективные функции: Результаты представлены на графике. |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
![]() |