...

воскресенье, 13 апреля 2014 г.

[Из песочницы] Несколько простых хеш-функций и их свойства

В процессе работы над хеш-таблицей возник обычный вопрос: какую из известных хеш-функций использовать. Образцов таких функций в сети множество, есть и «любимчики», использовавшиеся ранее и показавшие неплохой результат, в основном оценивавшийся «на глаз» — длины цепочек в хеш-таблице на боевых данных «примерно равны», значит, все работает так, как нужно; отдельные выбросы… ну что ж, ну выбросы, бывает.



В этот раз, наткнувшись на статью и воодушевившись ею, решил получить более или менее объективную сравнительную оценку хеш-функций. Для этого были сформулированы требования к ним, в число которых вошли следующие:


  • функция должна возвращать 32-битное целое значение;

  • функция должна получать на входе zero-terminated string (без явно заданной длины);

  • функция должна быть достаточно быстрой (по сравнению с конкурентами);

  • функция должна давать как можно более равномерное распределение хэш-значения;

  • (несколько необычное требование, вытекающее из особенностей конкретного применения) функция должна давать как можно более равномерное распределение хэш-значения, если в качестве этого значения использовать любой байт возвращенного ею числа.




В качестве тестовых данных я воспользовался тремя словарями из вышеупомянутой статьи, автору которой весьма признателен за сэкономленное время. Словари были преобразованы в windows-1251 и слиты в один файл. Всего получилось 327049 различных слов.

Приступим




Первой жертвой экспериментов пала любимица с магической цифрой 37, ранее бездумно применявшаяся для хеширования всего и вся:

unsigned int HashH37(const char * str)
{

unsigned int hash = 2139062143;

for(; *str; str++)
hash = 37 * hash + *str;

return hash;

}




Одного взгляда на гистограмму было достаточно, чтобы понять, что выбросы, конечно, бывают, да, бывают… но не такие же

h37

Впрочем, младшие два байта результата вполне юзабельны

h37 0

h37 1

а вот старшие как раз и дают то, что доводит общую картину до категории «печальная»

h37 2

h37 3

Итак, по «любимице» вывод: там, где достаточно 16 бит результата, функция вполне пригодна, в качестве же полного 32-битного хеша не годится абсолютно.

Другие кандидаты




Естественно, после увиденного привычной хеш-функции пришлось подыскивать замену. Не мудрствуя лукаво, просмотрел все функции, подходящие по первому пункту (т.е. не требующие знания длины строки перед вычислением хеша), в статье, хеш-функциям и посвященной.

В число кандидатов попали (названия сохраняю оригинальные)


  • Js

  • PJW

  • ELF

  • BKDR

  • SDBM

  • DJB

  • AP

  • FAQ6

  • Rot13

  • Ly

  • Rs




Из перечисленных только функции FAQ6, Rot13, Ly и Rs показали удовлетворительные результаты. Для остальных без лишних слов приведу распределения полного 32-битного значения:
Функция Js



Js
Функция PJW



PJW
Функция ELF



ELF
Функция BKDR



BKDR
Функция SDBM



SDBM
Функция DJB



DJB
Функция AP



AP

Победители




Для признанных «подходящими» функций приведу полный код (немного измененный по сравнению с данным в статье-источнике, изменения в основном связаны с требованием отстутствия явно заданной длины хешируемой строки) и распределения как полного 32-битного значения, так и каждого байта.
Функция FAQ6


unsigned int HashFAQ6(const char * str)
{

unsigned int hash = 0;

for (; *str; str++)
{
hash += (unsigned char)(*str);
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);

return hash;

}




32-битное значение

FAQ6

первый байт

FAQ6 0

второй байт

FAQ6 1

третий байт

FAQ6 2

четвертый байт

FAQ6 3
Функция Rot13


unsigned int HashRot13(const char * str)
{

unsigned int hash = 0;

for(; *str; str++)
{
hash += (unsigned char)(*str);
hash -= (hash << 13) | (hash >> 19);
}

return hash;

}




32-битное значение

Rot13

первый байт

Rot13 0

второй байт

Rot13 1

третий байт

Rot13 2

четвертый байт

Rot13 3
Функция Ly


unsigned int HashLy(const char * str)
{

unsigned int hash = 0;

for(; *str; str++)
hash = (hash * 1664525) + (unsigned char)(*str) + 1013904223;

return hash;

}




32-битное значение

Ly

первый байт

Ly 0

второй байт

Ly 1

третий байт

Ly 2

четвертый байт

Ly 3
Функция Rs


unsigned int HashRs(const char * str)
{

static const unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;

for(; *str; str++)
{
hash = hash * a + (unsigned char)(*str);
a *= b;
}

return hash;

}




32-битное значение

Rs

первый байт

Rs 0

второй байт

Rs 1

третий байт

Rs 2

четвертый байт

Rs 3

Производительность




Из всех протестированных функций наибольшую скорость работы продемонстрировала DJB. Несмотря на то, что в число «годных» функций она не попала, затраченное ею время на обработку всех тестовых слов я принял за 100% и соотнес с ним время работы остальных функций. Получилось следующее:




















































DJB100
SDBM111
BKDR113
H37113
Ly122
Js125
Rs125
Rot13145
AP159
ELF184
PJW191
FAQ6205



Если оставить в таблице только выбранные для использования функции, получим




















Ly122
Rs125
Rot13145
FAQ6205

Выводы




Рассмотрев статистические характеристики некоторых известных хеш-функций, мы выбрали из них те, что показали наиболее равномерное распределение как по полному 32-битному значению, так и по отдельным байтам и захабрили (для истории?) их исходный код. Следует отметить, что не вошедшие в четверку «лидеров» функции могут оказаться предпочтительными при других условиях, например, если полученное значение берется по какому-либо модулю. Мы такие случаи не рассматривали.

Благодарю за внимание.


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Комментариев нет:

Отправить комментарий