Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Несколько примитивных хеш-функций и их свойства

Anna | 24.06.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
1-й байт
FAQ6 0
2-й байт
FAQ6 1
3-й байт
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
1-й байт
Rot13 0
2-й байт
Rot13 1
3-й байт
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-битное значение
<imgsrc=”http: s30.postimg.org=”" snn9s0eh9=”" image.jpg”=”" alt=”Ly”>
1-й байт
Ly 0
2-й байт
Ly 1
3-й байт
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
1-й байт
Rs 0
2-й байт
Rs 1
3-й байт
Rs 2
четвертый байт
Rs 3

Продуктивность

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

DJB 100
SDBM 111
BKDR 113
H37 113
Ly 122
Js 125
Rs 125
Rot13 145
AP 159
ELF 184
PJW 191
FAQ6 205

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

Ly 122
Rs 125
Rot13 145
FAQ6 205

Итоги

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

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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB