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

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

В статье 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

Еще пять вариантов:

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

Тест номер 1

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

Общее количество после слияния — 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

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

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

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

Алгоритм Коллизии
rs 5
bkdr 14
sdbm 14
ap 32
ly 8
rot13 10
faq6 13
lookup3 14
crc32 15

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

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

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

 
proj/hash/efficiency.txt · Последние изменения: 2006/06/17 14:33 vak
 
Copyright (C) 1996-2013 Serge Vakulenko
serge@vak.ru