Пользователь
0,0
рейтинг
13 апреля 2014 в 06:55

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

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

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

Благодарю за внимание.
@madcomaker
карма
20,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (58)

  • –4
    Непонятно какие давались на вход строки? То что нулевой байт там отсутствовал видно по коду конечно, но что на счет остальных байт? Это были просто случайные ASCII строки или просто случайные наборы байт от 1 до 255? Или это был большой предопределенный набор?
    • +5
      Третий абзац:
      В качестве тестовых данных я воспользовался тремя словарями из вышеупомянутой статьи
  • –1
    Интересно было бы посмотреть ещё на функции с 64-битным результатом.
    • НЛО прилетело и опубликовало эту надпись здесь
    • +6
      Пожалуй только в академических целях. 32-битный хеш, удовлетворяющий поставленным требованиям, позволяет построить 4-уровневую хеш-таблицу на одной хеш-функции, при необходимости количество уровней можно увеличить, применив две или более функции. Думаю, даже возможности одной вряд ли будут исчерпаны в реальном проекте.

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


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

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

    CRC32
    Adler-32
    • НЛО прилетело и опубликовало эту надпись здесь
    • +2
      Упустил из виду Адлер, а CRC32 рассматривал, но решил, что у нее все-таки другое поле применения. Пожалуй, стоит наверстать упущенное.
  • 0
    Спасибо.
    Со словарями мне пока ещё не приходилось воевать, и эту часть работы я ещё не проделывал. Вы же её сделали за меня.
  • +3
    Можете выложить исходный код с тестовыми данными, чтобы иметь возможность быстро протестировать/сравнить собственные хэш-функции?
    • +4
      Для публикации код придется немного подчистить, но принципиальных проблем нет, подчищу и выложу.
      • 0
        Благодарю.
  • 0
    Самое интересное: какой алгоритм используется в std::hash / boost::hash, и есть ли надобность делать велосипед.
    • 0
      Что касается std::hash:
      The actual hash functions are implementation-dependent
    • +5
      Что касается конкретных реализаций:

      в libstdc++ (поставляется с GCC): murmur2
      в lib++ (clang): murmur2 на 32-битных платформах, cityhash64 на 64-битных
      в MS Visual C++: FNV
  • 0
    Скажу два слова в пользу защиты «старичка 37» — на этапе прототипирования он может быть удобен как наиболее доступный и легко запоминающийся. Затем эта функция может быть заменена по ситуации.

    С другой стороны у меня лично не возникало желания писать самому хеш функцию, а причины простые — либо работа идет с использованием инструментария какого-либо (Согласен с предыдущим оратором), либо с помощью managed языков, в которых опять же разумные функции подсчета.
    • +2
      У «старичка 37» есть младший брат — «старичок 31» (он, например, использовался для строк в Java до недавнего времени).
      Преимущество 31 в том, что умножение можно заменить на сдвиг и вычитание (x * 31 == (x << 5) - x). Т.е. функция станет ещё быстрее.
      • 0
        При этом в стандартной реализации 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
        Заметим также, что x*37 = (x<<5) + ((x<<2) + x). А как известно, +((x<<2) + x) в x86 заменяется одной волшебной коммандой LEA по индексу, те не совсем быстрее.
      • 0
        Ну, скорость для хеш-функции это не всегда преимущество.
        • 0
          для не-криптографической — всегда
          вы же не станете строить модель безопасности на 32-битном хэше
  • +8
    Что-то у вас не так с измерением производительности.
    Не может функция с двумя сдвигами (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
      А попробуйте пожалуйста с -O3
      • +1
        Если просто указать -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
          Интересно, а какой у вес процессор и разрядность?

          У меня таки Rs быстрее чем rot13 (gcc 4.8.1 Флаги -O3 -std=c++11, x86-64, Intel Core2 Duo P8600)
          • 0
            Процессор 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
              Я вижу 2 отличия:
              1. Atom по архитектуре сильно отличается от «больших» процессоров. Тайминги инструкций могут быть сильно другими и у атома нет out-of-order
              2. Код RsHash у меня сильно другой (смотрите в комментарии ниже) — с двумя умножениями вместо многочисленных lea
              • 0
                Интересно. Даже когда я выбираю 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
                  Такой код как у вас генерируется, если использовать опцию -mtune=nocona (это самый старый из 64-битных). Видимо, MinGW по умолчанию оптимизирует для него.
                  Попробуйте на вашей системе -mtune=native или -mtune=atom, может результаты станут лучше.
                  • +1
                    Вот результаты с -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
      В Rot13: 2 сложения, 2 сдвига и «или». Из них только 2 сдвига могут выполняться параллельно (если есть аппаратная возможность). То есть критический путь — 2 сложения, сдвиг и «или».
      В Rs 2 умножения и одно сложение, при этом второе умножение независимо от первого. На критическом пути одно умножение и одно сложение.
      То есть ситуация не такая однозначная, на современных процессорах Rs вполне может быть быстрее.
      • +4
        Поправлю сам себя: на самом деле то что делается в 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
      Несомненно, тестировались только сами функции плюс очень небольшие и постоянные для всех случаев накладные расходы на организацию циклов. Результат получается как усреднение ста прогонов всеми данными по каждой функции. С любыми оптимизациями, а также без оных, Rs уверенно обгоняет Rot13. В первую секунду подумал, что действительно чего-то намудрил, но нет, проверил тщательно — все верно. Очевидно, умножения таки выполняются параллельно, а сдвиги нет.
      • 0
        По крайней мере, это не всегда так, как видно из моего обсуждения с encyclopedist выше.
        (хотя, мой Atom, наверное, не самый лучший ориентир...)
  • 0
    Я в свое время, смотрел как разные хэшфунции влияют на скорость кастомного HashMap — так вот, скорость менялась на 1%. Даже такие «тупые» функции как «брать пару средних букв» как-то работали. Те идеальная равномерность — не сильно важно, а недостатки будут всегда — например, атаку по ключу можно делать и на идеальную ХФ. /Статья отличная, спасибо!/
    • +1
      Так автор как раз пишет, что задумал многоуровневый хеш. Для обычного, да еще и с простым модулем, понятно, разницы нет.

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

    WHY???
  • +1
    В ключевых библиотеках 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
      Слышали, как уже почти 15 лет в Яве реализован HashSet? Пойдите, сделайте доброе дело…
      • +1
        Ява — это к ораклоидам, не ко мне:) С тенденциями JVM потреблять в пять раз больше памяти (для словарей) чем Питон, даже не хочется задумываться, почему так.
        • 0
          Это к тому что даже очевидная неэффективность чего-то не означает, что улучшение с радостью примут в монструозный проект. Кстати, что-такого «построено на хешах» в оконной библиотеке и почему это хоть как-то влияет на скорость?
          • +1
            GLib по сравнению с Java — крошечный проект. Всего 2 мегабайта. Это не оконная библиотека, а библиотека общего назначения для Си, на хэшах там ООП (GObject). Более-менее представление о библиотеке может дать та же Википедия. И в отличие от ораклоидов, GLib свободный проект куда относительно без проблем любой может прислать патч.

            Производительность объектной системы неважная даже по сравнению с плюсами, но её ключ — универсальность (есть биндиги практически ко всему), чем не может похвастатья даже Qt. С появлением интроспекции стала серебряной пулей вавилонского столпотворения языков программирования.
            • 0
              Если на хешах там свойства объектов, то качество хеш-функции не играет роли, потому что ключей очень мало. Там, наоборот, по идее надо делать все максимально просто, даже если теоретически это может быть хуже при совпадении определенных условий.
    • 0
      Тут даже не я не выбрал, а тесты не выбрали. Возможно, на других данных результаты оказались бы другими. Для таких масштабных нововведений объем тестов все же желательно увеличить раз в… сто.
      • 0
        Так суть в этом и состоит — выбрать вариант, который в реальных боевых условиях показывает себя с наилучшей стороны. Тесты с академической точки зрения вещь интересная, но практически — сначала делаем продукт, далее, если узкое место — хэши — начинаем перебирать в поисках лучшего алгоритма. Конечно есть показательная порка плюсовой unordered_map, реализации boost (которая оказалась совсем не boost), но там и разница в несколько раз и отличаются они скорее организацией памяти, нежели хэш-функциями (они везде пользователем задаются).
  • +2
    Жаль, что FNV не попала в тестирование, её часто используют на строках.
  • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Насчёт полиномиального хэша («любимица») — можете, пожалуйста, попробовать с большим основанием, скажем, 23917 вместо 37? Вполне возможно, что проблемы возникают из-за того, что основание намного меньше даже диапазона значений. Скажем, на небольших строках это провал.
    • 0
      Кстати да. В Питоне и свежей библиотеке AutoValue 1000003. Правда, не знаю, откуда оно взялось. А 23917 откуда?
      • 0
        Количество коллизий полиномиального хэша становится меньше, если в качестве основания взять простое число.
        • +1
          Это ясно, но простых чисел много, почему именно эти? Только не говорите что действительно с потолка…
          • 0
            Скорее всего не с потолка, а по результатам тестов для разных простых чисел на каких-то более или менее правдоподобных данных.
    • 0
      Конечно можно. Это число для примера или использовалось где-то? Просто перебрать все возможные числа… интересно, но затратно. В обозримое время в планах собрать все, что здесь было упомянуто, и повторить испытания с бОльшим набором функций.
      • 0
        Простое число, большее основания. Согласно легендам среди олимпиадников, в качестве оснований лучше использовать простые числа, а брать по модулю либо 2^k (чтобы заменить взятие по модулю на битовые операции), либо по другому большому простому (подробнее здесь и здесь). На самом деле это ничем не обосновано (как сказано по второй ссылке) — надо лишь брать большое число, взаимно простое с модулем. Если взять маленькое (как 37), то проблемы легко могут начаться уже из-за того, что 2*37+0=0*37+74. То есть даже если не брать по модулю, а всё считать в длинной арифметике, то коллизии всё равно получаются, что как-то нехорошо.
  • +2
    Есть ещё вот такая отличная штука: 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
  • 0
    Почему так важно, чтобы на гистограмме не было «всплесков»? Что может случиться плохого, если несколько таких всплесков будут?
    • 0
      «всплески» означают, что выбранная функция для слишком многих вариантов входных данных даёт одинаковый результат. В итоге вам придётся хранить все эти результаты в одной ячейке хеш-таблицы, а значит при поиске — перебирать их все. Оценка среднего времени поиска возрастает.

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