Эффективность хэш-функций

(Есть вариант этой статьи на английском языке)

В статье 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 — стандартная контрольная сумма с полиномом x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1

Тексты на языке Си можно посмотреть здесь.

Для проверки эффективности хэш-функций были выбраны следующие тестовые данные:

• Американский словарь из проекта Ispell, 62075 слов.
• Русский словарь из проекта Ispell, 128900 слов.
• Список имен, извлеченный из всех библиотек на моем linux-компьютере (libc.a и прочие), 136073 слов.

Общее количество после слияния — 326797 уникальных слов. При идеально равномерном распределении 32-битного хэша для достижения 50%-ной вероятности коллизии требуется 77163 слова. Так что коллизии должны иметь место.

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

Список коллизий для rs, bkdr, sdbm, ap, ly, rot13, faq6, lookup3 и crc32 можно посмотреть здесь.

Наиболее эффективные функции:

• rot13 — один циклический сдвиг и сложение
• lookup3 — один сдвиг и сложение (или больше)
• ly — одно умножение и сложение
• rs — два умножения

Результаты представлены на графике. Два явных аутсайдера — pjw и dek — выходят за пределы графика.

В предыдущем тесте данные имели общее свойство - неизменный старший бит каждого байта. Это могло повлиять на результат. Поэтому был проведен повторный тест, для которого были выбраны другие наборы данных:

• Немецкий словарь из проекта Ispell, 39612 слов.
• Венгерский словарь из проекта Ispell, 211880 слов.
• Итальянский словарь из проекта Ispell, 37268 слов.
• Шведский словарь из проекта Ispell, 24019 слов.

Общее количество после слияния — 310595 уникальных слов.

В тесте не участвовали алгоритмы js, pjw, djb и dek.

Наиболее эффективные функции:

• rs — два умножения
• ly — одно умножение и сложение
• rot13 — один циклический сдвиг и сложение

Результаты представлены на графике.