СоХабр закрыт.

С 13.05.2019 изменения постов больше не отслеживаются, и новые посты не сохраняются.

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

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

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

  • функция должна возвращать 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% и соотнес с ним время работы остальных функций. Получилось следующее:
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-битному значению, так и по отдельным байтам и захабрили (для истории?) их исходный код. Следует отметить, что не вошедшие в четверку «лидеров» функции могут оказаться предпочтительными при других условиях, например, если полученное значение берется по какому-либо модулю. Мы такие случаи не рассматривали.

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

комментарии (55)

–4
xiWera ,  

Непонятно какие давались на вход строки? То что нулевой байт там отсутствовал видно по коду конечно, но что на счет остальных байт? Это были просто случайные ASCII строки или просто случайные наборы байт от 1 до 255? Или это был большой предопределенный набор?

+5
nagimov ,  

Третий абзац:

В качестве тестовых данных я воспользовался тремя словарями из вышеупомянутой статьи
–1
a553 ,  

Интересно было бы посмотреть ещё на функции с 64-битным результатом.

+1
+3 –2
AnatolyB ,  

Просто обратите внимение на SipHash.

...PEP[*] proposes SipHash as default string and bytes hash algorithm...

* PEP — Python Enhancement Proposal.

...It is fast and small despite its cryptographic properties. Due to the fact that it was designed by well known security and crypto experts, it is safe to assume that its secure for the near future.

+6
madcomaker ,   * (был изменён)

Пожалуй только в академических целях. 32-битный хеш, удовлетворяющий поставленным требованиям, позволяет построить 4-уровневую хеш-таблицу на одной хеш-функции, при необходимости количество уровней можно увеличить, применив две или более функции. Думаю, даже возможности одной вряд ли будут исчерпаны в реальном проекте.

Если же речь о криптографии, здесь таких задач попросту не ставилось.

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


Боюсь все 32 разряда от 32-разрядного хэша мы используем нечасто. Это ж хэштаблица на 4 миллиарда элементов должна быть чтоб их заюзать :)

Плюс интересно насколько данный результат для 32-разрядного хэша зависел от входных данных. Всё-таки строки из словаря это далеко не произвольные данные, и символы в них тоже…
+4
1010101001000100110100111 ,  

А, почему так незаслуженно обошли стороной такие хорошие штуки, как:

CRC32
Adler-32

+10
AnatolyB ,  
А, почему так незаслуженно обошли стороной такие хорошие штуки

Стоит заметить, что «CRC wasn't designed as a hash function and shouldn't be used as one».

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

MurmurHash
CityHash
SipHash
+2
madcomaker ,  

Упустил из виду Адлер, а CRC32 рассматривал, но решил, что у нее все-таки другое поле применения. Пожалуй, стоит наверстать упущенное.

0
+1 –1
scumware ,  

Спасибо.
Со словарями мне пока ещё не приходилось воевать, и эту часть работы я ещё не проделывал. Вы же её сделали за меня.

+3
+4 –1
byte ,   * (был изменён)

Можете выложить исходный код с тестовыми данными, чтобы иметь возможность быстро протестировать/сравнить собственные хэш-функции?

+4
+5 –1
madcomaker ,  

Для публикации код придется немного подчистить, но принципиальных проблем нет, подчищу и выложу.

0
byte ,  

Благодарю.

0
+2 –2
tenzink ,  

Самое интересное: какой алгоритм используется в std::hash / boost::hash, и есть ли надобность делать велосипед.

0
+1 –1
alphashooter ,  

Что касается std::hash:

The actual hash functions are implementation-dependent
+5
encyclopedist ,  

Что касается конкретных реализаций:

в libstdc++ (поставляется с GCC): murmur2
в lib++ (clang): murmur2 на 32-битных платформах, cityhash64 на 64-битных
в MS Visual C++: FNV

0
+1 –1
QtRoS ,  

Скажу два слова в пользу защиты «старичка 37» — на этапе прототипирования он может быть удобен как наиболее доступный и легко запоминающийся. Затем эта функция может быть заменена по ситуации.

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

+2
sabio ,  

У «старичка 37» есть младший брат — «старичок 31» (он, например, использовался для строк в Java до недавнего времени).
Преимущество 31 в том, что умножение можно заменить на сдвиг и вычитание (x * 31 == (x << 5) - x). Т.е. функция станет ещё быстрее.

0
lany ,  

При этом в стандартной реализации HashMap выход обычной hashCode-функции дополнительно перетасовывался:

hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
Видимо, это решало часть проблем «младшего брата».
+2
1dash ,  

Заметим также, что x*37 = (x

0
Gero ,  

Ну, скорость для хеш-функции это не всегда преимущество.

0
sabio ,  

для не-криптографической — всегда
вы же не станете строить модель безопасности на 32-битном хэше

+8
+9 –1
sabio ,  

Что-то у вас не так с измерением производительности.
Не может функция с двумя сдвигами (Rot13) быть медленнее функции с двумя умножениями (Rs).

В моём тесте Rot13 более чем в два раза быстрее Rs: 820 ms против 1820 ms
Замерял так:

    clock_t volatile start;
    clock_t volatile stop;

    start = clock();
    for (int i=0; i<10000000; i++) {
        HashRs("abcdefghijk");
    }
    stop = clock();
    printf("HashRs took %d ms\n", ms_elapsed(start, stop));

Не идеально, но для быстрого теста сойдёт.
Компилировал gcc из MinGW 4.6.1 с параметрами -O1 -std=c99.

Вы точно тестировали именно сами функции, а не, скажем, чтение слов из файла, сохранение результатов для построения гистограмм и пр.?

В целом, после усреднения результатов пяти запусков у меня получилась такая картина:
DJB — 100%
Rot13 — 106%
FAQ6 — 129%
Ly — 172%
Rs — 238%
0
encyclopedist ,  

А попробуйте пожалуйста с -O3

+1
sabio ,  

Если просто указать -O3, компилятор, похоже, выбрасывает «бесполезные» вызовы функций, и все циклы выполняются за одно и то же время, +- 5 мс

Я попробовал на скорую руку это предотвратить. Тест стал таким:

    total = 0;
    start = clock();
    for (int i=0; i<10000000; i++) {
        total += HashRs("abcdefklm");
    }
    stop = clock();
    printf("HashRs took %d ms (total = %ld)\n", ms_elapsed(start, stop), total);


Вот результат:
DJBHash took 594 ms
HashRot13 took 647 ms
HashFAQ6 took 792 ms
HashLy took 1105 ms
HashRs took 1425 ms

Rs, по-прежнему, в хвосте с более чем двукратным отставанием от Rot13.
0
encyclopedist ,  

Интересно, а какой у вес процессор и разрядность?

У меня таки Rs быстрее чем rot13 (gcc 4.8.1 Флаги -O3 -std=c++11, x86-64, Intel Core2 Duo P8600)

0
sabio ,  

Процессор 64-битный, но слабенький — Atom D510

Если интересно, вот какие инструкции генерирует MinGW 4.6.1 для -O3 -std=c99:

Код
_HashRot13:
LFB16:
	.cfi_startproc
	movl	4(%esp), %ecx
	movb	(%ecx), %dl
	xorl	%eax, %eax
	testb	%dl, %dl
	je	L27
	.p2align 2,,3
L26:
	movzbl	%dl, %edx
	addl	%eax, %edx
	movl	%edx, %eax
	roll	$13, %eax
	subl	%eax, %edx
	movl	%edx, %eax
	incl	%ecx
	movb	(%ecx), %dl
	testb	%dl, %dl
	jne	L26
	ret
L27:
	ret
	.cfi_endproc


_HashRs:
LFB13:
	.cfi_startproc
	pushl	%esi
	.cfi_def_cfa_offset 8
	.cfi_offset 6, -8
	pushl	%ebx
	.cfi_def_cfa_offset 12
	.cfi_offset 3, -12
	movl	12(%esp), %ebx
	movb	(%ebx), %dl
	xorl	%eax, %eax
	testb	%dl, %dl
	je	L10
	movl	$63689, %ecx
	.p2align 2,,3
L11:
	imull	%ecx, %eax
	movzbl	%dl, %edx
	addl	%edx, %eax
	leal	(%ecx,%ecx,4), %edx
	leal	(%ecx,%edx,4), %edx
	leal	(%ecx,%edx,8), %esi
	leal	0(,%esi,8), %edx
	subl	%esi, %edx
	sall	$5, %edx
	subl	%ecx, %edx
	leal	(%edx,%edx,4), %edx
	leal	(%ecx,%edx,2), %ecx
	incl	%ebx
	movb	(%ebx), %dl
	testb	%dl, %dl
	jne	L11
L10:
	popl	%ebx
	.cfi_def_cfa_offset 8
	.cfi_restore 3
	popl	%esi
	.cfi_def_cfa_offset 4
	.cfi_restore 6
	ret
	.cfi_endproc

+1
encyclopedist ,  

Я вижу 2 отличия:
1. Atom по архитектуре сильно отличается от «больших» процессоров. Тайминги инструкций могут быть сильно другими и у атома нет out-of-order
2. Код RsHash у меня сильно другой (смотрите в комментарии ниже) — с двумя умножениями вместо многочисленных lea

0
sabio ,  

Интересно. Даже когда я выбираю GCC 4.6.x в GCC Explorer, код остаётся таким, как у вас.
Получается MinGW, построенный на базе того же самого GCC, всё же как-то по-другому компилирует?

Интересно ещё и то, что инлайн-код тоже другой. В частности, в функции HashRot13 используется roll, а заинлайнен — rorl.

Код
L30:
	movb	$97, %dl
	xorl	%ecx, %ecx
	movl	$LC2, %eax
	.p2align 2,,3
L31:
	movzbl	%dl, %edx
	addl	%ecx, %edx
	movl	%edx, %ecx
	rorl	$19, %ecx
	subl	%ecx, %edx
	movl	%edx, %ecx
	incl	%eax
	movb	(%eax), %dl
	testb	%dl, %dl
	jne	L31
0
encyclopedist ,  

Такой код как у вас генерируется, если использовать опцию -mtune=nocona (это самый старый из 64-битных). Видимо, MinGW по умолчанию оптимизирует для него.
Попробуйте на вашей системе -mtune=native или -mtune=atom, может результаты станут лучше.

+1
sabio ,   * (был изменён)

Вот результаты с -mtune:

        no -mtune  -mtune=native  -mtune=atom
DJB        617 ms         433 ms       408 ms
Rot13      685 ms         469 ms       491 ms
Rs        1492 ms         560 ms       576 ms
FAQ6       838 ms         637 ms       618 ms
Ly        1170 ms         683 ms       699 ms


С -mtune скорость действительно увеличилась в 1.5 раза.
Но при этом Rs, как и раньше, уступает Rot13. Хотя, разрыв и сократился значительно.
+2
encyclopedist ,  

В Rot13: 2 сложения, 2 сдвига и «или». Из них только 2 сдвига могут выполняться параллельно (если есть аппаратная возможность). То есть критический путь — 2 сложения, сдвиг и «или».
В Rs 2 умножения и одно сложение, при этом второе умножение независимо от первого. На критическом пути одно умножение и одно сложение.
То есть ситуация не такая однозначная, на современных процессорах Rs вполне может быть быстрее.

+4
encyclopedist ,  

Поправлю сам себя: на самом деле то что делается в rot13 это один циклический сдвиг. Два сдвига нужны лишь для того, чтобы выразить его в терминах С. Современные компиляторы способны заменить их на один. В результате получается такой код для этих функций (gcc.godbolt.org):

ROT13Hash(char*, unsigned int):
	testl	%esi, %esi
	je	.L4
	subl	$1, %esi
	xorl	%eax, %eax
	leaq	1(%rdi,%rsi), %rcx
.L3:
	movzbl	(%rdi), %edx
	addq	$1, %rdi
	addl	%edx, %eax
	movl	%eax, %edx
	rorl	$19, %edx
	subl	%edx, %eax
	cmpq	%rcx, %rdi
	jne	.L3
	rep; ret
.L4:
	xorl	%eax, %eax
	ret
RSHash(char*, unsigned int):
	testl	%esi, %esi
	je	.L9
	subl	$1, %esi
	xorl	%eax, %eax
	movl	$63689, %edx
	leaq	1(%rdi,%rsi), %rsi
.L8:
	movzbl	(%rdi), %ecx
	addq	$1, %rdi
	imull	%edx, %eax
	imull	$378551, %edx, %edx
	addl	%ecx, %eax
	cmpq	%rsi, %rdi
	jne	.L8
	rep; ret
.L9:
	xorl	%eax, %eax
	ret


То есть мы имеем (за исключением общей части — загрузки, инкремента указателя и проверки условия):
rot13: сложение, сдвиг, вычитание. Все последовательно.
Rs: 2 умножения (параллельно) и сложение.
0
madcomaker ,  

Несомненно, тестировались только сами функции плюс очень небольшие и постоянные для всех случаев накладные расходы на организацию циклов. Результат получается как усреднение ста прогонов всеми данными по каждой функции. С любыми оптимизациями, а также без оных, Rs уверенно обгоняет Rot13. В первую секунду подумал, что действительно чего-то намудрил, но нет, проверил тщательно — все верно. Очевидно, умножения таки выполняются параллельно, а сдвиги нет.

0
sabio ,  

По крайней мере, это не всегда так, как видно из моего обсуждения с encyclopedist выше.
(хотя, мой Atom, наверное, не самый лучший ориентир...)

0
1dash ,   * (был изменён)

Я в свое время, смотрел как разные хэшфунции влияют на скорость кастомного HashMap — так вот, скорость менялась на 1%. Даже такие «тупые» функции как «брать пару средних букв» как-то работали. Те идеальная равномерность — не сильно важно, а недостатки будут всегда — например, атаку по ключу можно делать и на идеальную ХФ. /Статья отличная, спасибо!/

+1
leventov ,  

Так автор как раз пишет, что задумал многоуровневый хеш. Для обычного, да еще и с простым модулем, понятно, разницы нет.

С другой стороны, 1% это может быть замедление в 100 раз на 0,01% ключей. А предсказуемость пауз иногда ключевая вещь.

–1
+1 –2
Sannis ,  
Словари были преобразованы в windows-1251

WHY???
+1
RPG ,   * (был изменён)

В ключевых библиотеках Linux GNOME всё зиждется на DJB. В Qt — PJW. И ни одну из них вы не выбрали? Гораздо интереснее будет взять эти хэш-функции, засунуть по очереди в центральные библиотеки и посмотреть на практический результат. В GLib вся объектная система построена на хэшах — так что у вас есть шанс сделать доброе дело, если грамотно докажете непригодность используемых хэшей.

Вот ещё коммент для размышления из исходников Qt:

// ### Qt 5: see tests/benchmarks/corelib/tools/qhash/qhash_string.cpp
// Hashing of the whole string is a waste of cycles.

/*
    These functions are based on Peter J. Weinberger's hash function
    (from the Dragon Book). The constant 24 in the original function
    was replaced with 23 to produce fewer collisions on input such as
    "a", "aa", "aaa", "aaaa", ...
*/


P.S. Надо конечно заметить, что Qt использует для строк UTF-16, а GLib — UTF-8, поэтому хэш-таблицы GLib неоднократно показывали превосходство над остальными реализациями, с GLib может потягаться только хэш от Google.
0
leventov ,  

Слышали, как уже почти 15 лет в Яве реализован HashSet? Пойдите, сделайте доброе дело…

+1
RPG ,   * (был изменён)

Ява — это к ораклоидам, не ко мне:) С тенденциями JVM потреблять в пять раз больше памяти (для словарей) чем Питон, даже не хочется задумываться, почему так.

0
leventov ,  

Это к тому что даже очевидная неэффективность чего-то не означает, что улучшение с радостью примут в монструозный проект. Кстати, что-такого «построено на хешах» в оконной библиотеке и почему это хоть как-то влияет на скорость?

+1
RPG ,   * (был изменён)

GLib по сравнению с Java — крошечный проект. Всего 2 мегабайта. Это не оконная библиотека, а библиотека общего назначения для Си, на хэшах там ООП (GObject). Более-менее представление о библиотеке может дать та же Википедия. И в отличие от ораклоидов, GLib свободный проект куда относительно без проблем любой может прислать патч.

Производительность объектной системы неважная даже по сравнению с плюсами, но её ключ — универсальность (есть биндиги практически ко всему), чем не может похвастатья даже Qt. С появлением интроспекции стала серебряной пулей вавилонского столпотворения языков программирования.

0
leventov ,  

Если на хешах там свойства объектов, то качество хеш-функции не играет роли, потому что ключей очень мало. Там, наоборот, по идее надо делать все максимально просто, даже если теоретически это может быть хуже при совпадении определенных условий.

0
madcomaker ,  

Тут даже не я не выбрал, а тесты не выбрали. Возможно, на других данных результаты оказались бы другими. Для таких масштабных нововведений объем тестов все же желательно увеличить раз в… сто.

0
RPG ,  

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

+2
pravic ,  

Жаль, что FNV не попала в тестирование, её часто используют на строках.

0
+1 –1
TolTol ,  

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

Это похоже на дефект в архитектуре приложения. Null-terminated stings — это рудимент, который сказывается на эффективности и безопасности.

Если приведенные в статье реализации хэшей требуют несколько процессорных тактов на обработку байта, то, например, CityHash при средней длине строки обрабатывает несколько байт за один процессорный такт.

+1
yeputons ,  

Насчёт полиномиального хэша («любимица») — можете, пожалуйста, попробовать с большим основанием, скажем, 23917 вместо 37? Вполне возможно, что проблемы возникают из-за того, что основание намного меньше даже диапазона значений. Скажем, на небольших строках это провал.

0
leventov ,  

Кстати да. В Питоне и свежей библиотеке AutoValue 1000003. Правда, не знаю, откуда оно взялось. А 23917 откуда?

0
Flux ,  

Количество коллизий полиномиального хэша становится меньше, если в качестве основания взять простое число.

+1
leventov ,  

Это ясно, но простых чисел много, почему именно эти? Только не говорите что действительно с потолка…

0
madcomaker ,  

Конечно можно. Это число для примера или использовалось где-то? Просто перебрать все возможные числа… интересно, но затратно. В обозримое время в планах собрать все, что здесь было упомянуто, и повторить испытания с бОльшим набором функций.

0
yeputons ,  

Простое число, большее основания. Согласно легендам среди олимпиадников, в качестве оснований лучше использовать простые числа, а брать по модулю либо 2^k (чтобы заменить взятие по модулю на битовые операции), либо по другому большому простому (подробнее здесь и здесь). На самом деле это ничем не обосновано (как сказано по второй ссылке) — надо лишь брать большое число, взаимно простое с модулем. Если взять маленькое (как 37), то проблемы легко могут начаться уже из-за того, что 2*37+0=0*37+74. То есть даже если не брать по модулю, а всё считать в длинной арифметике, то коллизии всё равно получаются, что как-то нехорошо.

+2
mmatrosov ,   * (был изменён)

Есть ещё вот такая отличная штука: programmers.stackexchange.com/q/49550/86824

Рассматривются хэши:

  • DJB2
  • DJB2a (variant using xor rather than +)
  • FNV-1 (32-bit)
  • FNV-1a (32-bit)
  • SDBM
  • CRC32
  • Murmur2 (32-bit)
  • SuperFastHash

Картинка для SDBM:
image