====== Эффективность хэш-функций ======
(Есть вариант этой статьи [[hash:efficiency-en | на английском языке]])

В статье Arash Partow
[[http://www.partow.net/programming/hashfunctions/ |
"General Purpose Hash Function Algorithms"]]
приведены восемь вариантов 32-битных хэш-функций:
  * rs --- простая хэш-функция из книги Роберта Седжвика [[http://www.ozon.ru/context/detail/id/1425749/ | 'Фундаментальные алгоритмы на C']]
  * js --- побитовая хэш-функция от Justin Sobel
  * pjw --- алгоритм, основанный на работе Peter J. Weinberger
  * bkdr --- хэш-функция из книги Брайана Кернигана и Денниса Ритчи [[http://www.ozon.ru/context/detail/id/2480925/ | 'Язык программирования C']]
  * sdbm --- специальный алгоритм, используемый в проекте SDBM
  * djb --- алгоритм, разработанный профессором Daniel J. Bernstein
  * dek --- алгоритм, предложенный Дональдом Кнутом в книге [[http://www.ozon.ru/context/detail/id/2527036/ | 'Искусство программирования']]
  * ap --- алгоритм, разработанный Arash Partow

Еще пять вариантов:
  * faq6 --- номер 6 из [[http://burtleburtle.net/bob/hash/hashfaq.html | FAQ Боба Дженкинса]]
  * lookup3 --- автор [[http://burtleburtle.net/bob/hash/ | Боб Дженкинс]]
  * ly --- предложен [[http://leo.yuriev.ru/random | Леонидом Юрьевым]] (конгруэнтный генератор)
  * rot13 --- простой алгоритм с циклическим сдвигом, от Сергея Вакуленко
  * crc32 --- [[http://www.w3.org/TR/PNG-CRCAppendix.html | стандартная контрольная сумма]] с полиномом x<sup>32</sup>+x<sup>26</sup>+x<sup>23</sup>+x<sup>22</sup>+x<sup>16</sup>+x<sup>12</sup>+x<sup>11</sup>+x<sup>10</sup>+x<sup>8</sup>+x<sup>7</sup>+x<sup>5</sup>+x<sup>4</sup>+x<sup>2</sup>+x+1

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

===== Тест номер 1 =====
Для проверки эффективности хэш-функций были выбраны следующие тестовые данные:
  * {{usdict.gz | Американский словарь}} из проекта Ispell, 62075 слов.
  * {{rudict.gz | Русский словарь}} из проекта Ispell, 128900 слов.
  * {{symbols.gz | Список имен}}, извлеченный из всех библиотек на моем 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
можно посмотреть [[conflicts | здесь]].

Наиболее эффективные функции:
  * [[sources#ROT13 Hash Function| rot13]] --- один циклический сдвиг и сложение
  * [[sources#LOOKUP3 Hash Function| lookup3]] --- один сдвиг и сложение (или больше)
  * [[sources#LY Hash Function| ly]] --- одно умножение и сложение
  * [[sources#RS Hash Function| rs]] --- два умножения

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

{{hash-eff.png}}

----
===== Тест номер 2 =====
В предыдущем тесте данные имели общее свойство - неизменный старший бит каждого байта. Это могло повлиять на результат. Поэтому был проведен повторный тест, для которого были выбраны другие наборы данных:
  * {{dedict.gz | Немецкий словарь}} из проекта Ispell, 39612 слов.
  * {{hudict.gz | Венгерский словарь}} из проекта Ispell, 211880 слов.
  * {{itdict.gz | Итальянский словарь}} из проекта Ispell, 37268 слов.
  * {{sedict.gz | Шведский словарь}} из проекта 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	    |

Наиболее эффективные функции:
  * [[sources#RS Hash Function| rs]] --- два умножения
  * [[sources#LY Hash Function| ly]] --- одно умножение и сложение
  * [[sources#ROT13 Hash Function| rot13]] --- один циклический сдвиг и сложение

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

{{de-hu-se-it.png}}