Table of Contents
Эффективность хэш-функций
(Есть вариант этой статьи на английском языке)
В статье Arash Partow "General Purpose Hash Function Algorithms" приведены восемь вариантов 32-битных хэш-функций:
- rs — простая хэш-функция из книги Роберта Седжвика 'Фундаментальные алгоритмы на C'
- js — побитовая хэш-функция от Justin Sobel
- pjw — алгоритм, основанный на работе Peter J. Weinberger
- bkdr — хэш-функция из книги Брайана Кернигана и Денниса Ритчи 'Язык программирования C'
- sdbm — специальный алгоритм, используемый в проекте SDBM
- djb — алгоритм, разработанный профессором Daniel J. Bernstein
- dek — алгоритм, предложенный Дональдом Кнутом в книге 'Искусство программирования'
- ap — алгоритм, разработанный Arash Partow
Еще пять вариантов:
- faq6 — номер 6 из FAQ Боба Дженкинса
- lookup3 — автор Боб Дженкинс
- ly — предложен Леонидом Юрьевым (конгруэнтный генератор)
- rot13 — простой алгоритм с циклическим сдвигом, от Сергея Вакуленко
- crc32 — стандартная контрольная сумма с полиномом x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
Тексты на языке Си можно посмотреть здесь.
Тест номер 1
Для проверки эффективности хэш-функций были выбраны следующие тестовые данные:
- Американский словарь из проекта Ispell, 62075 слов.
- Русский словарь из проекта Ispell, 128900 слов.
- Список имен, извлеченный из всех библиотек на моем linux-компьютере (libc.a и прочие), 136073 слов.
Общее количество после слияния — 326797 уникальных слов. При идеально равномерном распределении 32-битного хэша для достижения 50%-ной вероятности коллизии требуется 77163 слова. Так что коллизии должны иметь место.
Для каждого из слов тестового наборы было вычислено 32-битное значение хэш-функции и подсчитано количество коллизий.
Алгоритм | Коллизии |
---|---|
rs | 9 |
js | 98 |
pjw | 1315 |
bkdr | 11 |
sdbm | 14 |
djb | 83 |
dek | 308 |
ap | 16 |
ly | 9 |
rot13 | 7 |
faq6 | 14 |
lookup3 | 9 |
crc32 | 13 |
Список коллизий для rs, bkdr, sdbm, ap, ly, rot13, faq6, lookup3 и crc32 можно посмотреть здесь.
Наиболее эффективные функции:
- rot13 — один циклический сдвиг и сложение
- lookup3 — один сдвиг и сложение (или больше)
- ly — одно умножение и сложение
- rs — два умножения
Результаты представлены на графике. Два явных аутсайдера — pjw и dek — выходят за пределы графика.
Тест номер 2
В предыдущем тесте данные имели общее свойство - неизменный старший бит каждого байта. Это могло повлиять на результат. Поэтому был проведен повторный тест, для которого были выбраны другие наборы данных:
- Немецкий словарь из проекта Ispell, 39612 слов.
- Венгерский словарь из проекта Ispell, 211880 слов.
- Итальянский словарь из проекта Ispell, 37268 слов.
- Шведский словарь из проекта Ispell, 24019 слов.
Общее количество после слияния — 310595 уникальных слов.
В тесте не участвовали алгоритмы js, pjw, djb и dek.
Алгоритм | Коллизии |
---|---|
rs | 5 |
bkdr | 14 |
sdbm | 14 |
ap | 32 |
ly | 8 |
rot13 | 10 |
faq6 | 13 |
lookup3 | 14 |
crc32 | 15 |
Наиболее эффективные функции:
Результаты представлены на графике.