Какой алгоритм хеширования лучше всего подходит для уникальности и скорости?

1388

Какой алгоритм хеширования лучше всего подходит для уникальности и скорости? Примеры (хороших) применений включают хеш-словари.

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

Earlz
источник
9
Для каких целей безопасность или другое?
Orbling
19
@ Orbling, для реализации хеш-словаря. Таким образом, столкновения должны быть сведены к минимуму, но это не имеет цели безопасности вообще.
Earlz
4
Обратите внимание, что вам нужно ожидать, по крайней мере, некоторых коллизий в вашей хэш-таблице, в противном случае таблица должна быть огромной, чтобы можно было обрабатывать даже относительно небольшое количество ключей ...
Дин Хардинг,
19
Отличный пост! Не могли бы вы также проверить xxHash Янна Коллета (создатель или LZ4), который в два раза быстрее, чем Murmur? Домашняя страница: code.google.com/p/xxhash Дополнительная информация: fastcompression.blogspot.fr/2012/04/…
24
@zvrba Зависит от алгоритма. bcrypt разработан, чтобы быть медленным.
Изката

Ответы:

2461

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

Я использовал три разных набора ключей:

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

Я проверял:

Результаты

Каждый результат содержит среднее время хеширования и количество столкновений.

Hash           Lowercase      Random UUID  Numbers
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis▪
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis▪▪▪
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis▪▪▪
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
SuperFastHash     164 ns      344 ns         118 ns
                   85 collis    4 collis   18742 collis
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis
LoseLose          338 ns        -             -
               215178 collis

Примечания :

Действительно ли случаются столкновения?

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

Столкновения ФНВ-1

  • creamwove сталкивается с quists

Столкновения ФНВ-1а

  • costarring сталкивается с liquid
  • declinate сталкивается с macallums
  • altarage сталкивается с zinke
  • altarages сталкивается с zinkes

Murmur2 столкновения

  • cataract сталкивается с periti
  • roquette сталкивается с skivie
  • shawl сталкивается с stormbound
  • dowlases сталкивается с tramontane
  • cricketings сталкивается с twanger
  • longans сталкивается с whigs

DJB2 столкновения

  • hetairas сталкивается с mentioner
  • heliotropes сталкивается с neurospora
  • depravement сталкивается с serafins
  • stylist сталкивается с subgenera
  • joyful сталкивается с synaphea
  • redescribed сталкивается с urites
  • dram сталкивается с vivency

DJB2a столкновения

  • haggadot сталкивается с loathsomenesses
  • adorablenesses сталкивается с rentability
  • playwright сталкивается с snush
  • playwrighting сталкивается с snushing
  • treponematoses сталкивается с waterbeds

CRC32 столкновения

  • codding сталкивается с gnu
  • exhibiters сталкивается с schlager

SuperFastHash столкновения

  • dahabiah сталкивается с drapability
  • encharm сталкивается с enclave
  • grahams сталкивается с gramary
  • ... отсечь 79 столкновений ...
  • night сталкивается с vigil
  • nights сталкивается с vigils
  • finks сталкивается с vinic

Randomnessification

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

Введите описание изображения здесь

Или как карта Гильберта ( XKCD всегда актуален ):

Введите описание изображения здесь

Кроме случаев , когда хэширования число строк ( "1", "2", ..., "216553") (например, почтовые индексы ), где модели начинают появляться в большинстве алгоритмов хэширования:

SDBM :

Введите описание изображения здесь

DJB2a :

Введите описание изображения здесь

FNV-1 :

Введите описание изображения здесь

Все, кроме FNV-1a , которые все еще выглядят довольно случайными для меня:

Введите описание изображения здесь

Фактически, Murmur2, кажется, имеет даже лучшую случайность с Numbersчем FNV-1a:

Введите описание изображения здесь

Когда я смотрю на FNV-1aкарту «число», я думаю, что вижу тонкие вертикальные узоры. С Murmur я не вижу никаких закономерностей. Как вы думаете?


Дополнительное значение *в таблице обозначает, насколько плоха случайность. С FNV-1aявляется лучшим, и DJB2xявляется худшим:

      Murmur2: .
       FNV-1a: .
        FNV-1: ▪
         DJB2: ▪▪
        DJB2a: ▪▪
         SDBM: ▪▪▪
SuperFastHash: .
          CRC: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
     Loselose: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
                                        ▪
                                 ▪▪▪▪▪▪▪▪▪▪▪▪▪
                        ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
          ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪

Первоначально я написал эту программу, чтобы решить, нужно ли мне беспокоиться о столкновениях.

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

Алгоритм FNV-1a

Хэш FNV1 поставляется в вариантах, которые возвращают 32, 64, 128, 256, 512 и 1024-битные хэши.

Алгоритм FNV-1a является:

hash = FNV_offset_basis
for each octetOfData to be hashed
    hash = hash xor octetOfData
    hash = hash * FNV_prime
return hash

Где константы FNV_offset_basisи FNV_primeзависят от размера возвращаемого хеша:

Hash Size  
===========
32-bit
    prime: 2^24 + 2^8 + 0x93 = 16777619
    offset: 2166136261
64-bit
    prime: 2^40 + 2^8 + 0xb3 = 1099511628211
    offset: 14695981039346656037
128-bit
    prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
    offset: 144066263297769815596495629667062367629
256-bit
    prime: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
    offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
512-bit
    prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
    offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
1024-bit
    prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
    offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915

Смотрите главную страницу FNV для деталей.

Все мои результаты с 32-битным вариантом.

FNV-1 лучше, чем FNV-1a?

FNV-1a лучше вокруг. Было больше столкновений с FNV-1a при использовании английского слова corpus:

Hash    Word Collisions
======  ===============
FNV-1   1
FNV-1a  4

Теперь сравните строчные и прописные буквы:

Hash    lowercase word Collisions  UPPERCASE word collisions
======  =========================  =========================
FNV-1   1                          9
FNV-1a  4                          11

В этом случае FNV-1a не «на 400%» хуже, чем FN-1, только на 20% хуже.

Я думаю, что более важным выводом является то, что существует два класса алгоритмов, когда речь идет о столкновениях:

  • редкие столкновения : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
  • Общие коллизии : SuperFastHash, Loselose

И затем, насколько равномерно распределены хэши:

  • выдающийся дистрибутив: Murmur2, FNV-1a, SuperFastHas
  • отличное распределение: FNV-1
  • хорошее распределение: SDBM, DJB2, DJB2a
  • ужасное распределение: Loselose

Обновить

Ропщите? Конечно почему нет


Обновить

@whatshisname задалась вопросом, как будет работать CRC32 , добавила числа в таблицу.

CRC32 довольно хорош . Мало коллизий, но медленнее, и накладные расходы таблицы поиска 1k.

Отсеки все ошибочные материалы о распространении CRC - мой плохой


До сегодняшнего дня я собирался использовать FNV-1a в качестве своего фактического алгоритма хэширования хеш-таблицы. Но теперь я перехожу на Murmur2:

  • Быстрее
  • Лучшая рандомизация всех классов ввода

И я действительно, очень надеюсь, что что-то не так с SuperFastHashалгоритмом, который я нашел ; это слишком плохо, чтобы быть таким же популярным.

Обновление: с домашней страницы MurmurHash3 в Google :

(1) - SuperFastHash имеет очень плохие свойства столкновения, которые были задокументированы в другом месте.

Так что, думаю, это не только я.

Обновление: я понял, почему Murmurбыстрее, чем другие. MurmurHash2 работает с четырьмя байтами одновременно. Большинство алгоритмов побайтно :

for each octet in Key
   AddTheOctetToTheHash

Это означает, что когда ключи становятся длиннее, Murmur получает шанс сиять.


Обновить

GUID разработаны для того, чтобы быть уникальными, а не случайными

Своевременное сообщение Рэймонда Чена подтверждает тот факт, что «случайные» GUID не предназначены для их случайности. Они или их часть не подходят в качестве хеш-ключа:

Даже алгоритм GUID Версии 4 не гарантированно непредсказуем, поскольку алгоритм не определяет качество генератора случайных чисел. Статья Википедии для GUID содержит первичное исследование, которое предполагает, что будущие и предыдущие GUID могут быть предсказаны на основе знания состояния генератора случайных чисел, поскольку генератор не является криптографически стойким.

Randomess - это не то же самое, что избегать столкновений; вот почему было бы ошибкой пытаться изобрести свой собственный алгоритм «хэширования», взяв некоторое подмножество «случайного» guid:

int HashKeyFromGuid(Guid type4uuid)
{
   //A "4" is put somewhere in the GUID.
   //I can't remember exactly where, but it doesn't matter for
   //the illustrative purposes of this pseudocode
   int guidVersion = ((type4uuid.D3 & 0x0f00) >> 8);
   Assert(guidVersion == 4);

   return (int)GetFirstFourBytesOfGuid(type4uuid);
}

Примечание : опять же, в кавычки я помещаю «случайный GUID» , потому что это «случайный» вариант GUID. Более точное описание будет Type 4 UUID. Но никто не знает, что типа 4 или 1, 3 и 5. Так что проще назвать их «случайными» GUID.

Все английские слова зеркал

Ян Бойд
источник
41
Было бы действительно интересно посмотреть, как сравнивается SHA, а не потому, что он является хорошим кандидатом для алгоритма хеширования, но было бы очень интересно увидеть, как любой криптографический хэш сравнивается с этим, созданным для алгоритмов скорости.
Майкл
8
Новый хэш по имени 'xxHash' от Yann Collet недавно делал раунды. Я всегда с подозрением отношусь к новому хешу. Было бы интересно увидеть это в вашем сравнении (если вы не устали от людей, предлагающих добавлять случайные хэши, о которых они слышали ...)
th_in_gs
7
На самом деле. Показатели производительности, объявленные на странице проекта xxHash, выглядят впечатляюще, может быть, слишком много, чтобы быть правдой. Ну, по крайней мере, это проект с открытым исходным кодом: code.google.com/p/xxhash
ATTracker
9
Привет Ян, моя реализация SuperFastHash в Delphi верна. При реализации я создал набор тестов в C и Delphi, чтобы сравнить результаты моей реализации и эталонной реализации. Там нет никаких различий. Итак, что вы видите, так это хеш хэш ... (Вот почему я также опубликовал реализацию MurmurHash : landman-code.blogspot.nl/2009/02/… )
Дейви Лэндман,
20
Знает ли автор, что это не просто потрясающий ответ - это фактический справочный ресурс в мире по этому вопросу? В любое время мне нужно иметь дело с хэшами, это решает мою проблему так быстро и авторитетно, что мне больше ничего не нужно.
MaiaVictor
59

Если вы хотите создать хеш-карту из неизменного словаря, вы можете рассмотреть возможность идеального хеширования https://en.wikipedia.org/wiki/Perfect_hash_function - во время создания хеш-функции и хеш-таблицы вы можете гарантировать: для данного набора данных, что не будет столкновений.

Damien
источник
2
Вот еще о (минимальном) Perfect Hashing burtleburtle.net/bob/hash/perfect.html, включая данные о производительности, хотя он не использует самый современный процессор и т. Д.
Элли Кессельман,
4
Это довольно очевидно, но стоит отметить, что для того, чтобы гарантировать отсутствие коллизий, ключи должны быть того же размера, что и значения, если только нет ограничений на значения, на которых алгоритм может извлечь выгоду.
devios1
1
@ devios1 Ваше утверждение не имеет смысла. Во-первых, значения в хэш-таблице, совершенные или нет, не зависят от ключей. Во-вторых, идеальная хеш-таблица - это просто линейный массив значений, индексируемый результатом функции, которая была создана таким образом, чтобы все индексы были уникальными.
Джим Балтер
1
@MarcusJ Идеальное хеширование обычно используется с менее чем 100 ключами, но взгляните на cmph.sourceforge.net ... все еще далеко от вашего диапазона.
Джим Балтер
1
@DavidCary Ничто по вашей ссылке не поддерживает вашу заявку. Возможно, вы перепутали O (1) с «без столкновений», но это совсем не одно и то же. Конечно, идеальное хеширование гарантирует отсутствие коллизий, но для этого необходимо, чтобы все ключи были известны заранее и их было относительно немного. (Но смотрите ссылку на cmph выше.)
Джим Балтер
34

Вот список хеш-функций, но короткая версия:

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

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}
Дин Хардинг
источник
6
На самом деле djb2 чувствителен к нулю, как и большинство таких простых хеш-функций, поэтому вы легко можете разбить такие хеш-функции. Это плохо смещение слишком много столкновений и плохое распределения, он ломает на большинство smhasher испытаний качества: См github.com/rurban/smhasher/blob/master/doc/bernstein Его база данных CDB использует его, но я бы не использовать его с публичным доступом.
Рурбан
2
DJB довольно плох с точки зрения производительности и распространения. Я бы не использовал это сегодня.
Конрад Мейер
@ConradMeyer Бьюсь об заклад, DJB может быть ускорен в три раза, как и в этом моем вопросе, и тогда он, вероятно, побьет большинство используемых алгоритмов. По поводу раздачи я согласен. Хеш, создающий коллизии даже для двухбуквенных строк, не может быть действительно хорошим.
Maaartinus
28

CityHash от Google - это алгоритм, который вы ищете. Это не хорошо для криптографии, но хорошо для генерации уникальных хэшей.

Прочитайте блог для получения более подробной информации и код доступен здесь .

CityHash написан на C ++. Там также есть обычный порт C .

О 32-битной поддержке:

Все функции CityHash настроены для 64-битных процессоров. Тем не менее, они будут работать (за исключением новых, которые используют SSE4.2) в 32-битном коде. Они не будут очень быстрыми. Вы можете использовать Murmur или что-то еще в 32-битном коде.

Випин Параккат
источник
11
Является ли CityHash похожим на "City Sushi?"
Эрик
2
Взгляните также на SipHash, он предназначен для замены MurmurHash / CityHash / и т.д. : 131002.net/siphash
Török Edwin
3
Также см. FarmHash, преемник CitHash. code.google.com/p/farmhash
stevendaniels
7
xxHash утверждает, что в 5 раз быстрее, чем CityHash.
Глиняные Мосты
plain C portссылка не работает
makerj
20

Я составил краткое сравнение скорости различных алгоритмов хэширования при хэшировании файлов.

Отдельные графики лишь незначительно отличаются в методе чтения и могут быть проигнорированы здесь, так как все файлы были сохранены в tmpfs. Поэтому, если вам интересно, тест не был связан с IO.

Алгоритмы включают в себя: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Выводы:

  • Некриптографические хеш-функции, такие как Murmur3, Cityhash и Spooky, довольно близки друг к другу. Следует отметить, что Cityhash может быть быстрее на процессорах с CRCинструкцией SSE 4.2s , которой нет у моего процессора. SpookyHash был в моем случае всегда чуть-чуть до CityHash.
  • MD5 представляется хорошим компромиссом при использовании криптографических хеш-функций, хотя SHA256 может быть более безопасным для уязвимостей коллизий MD5 и SHA1.
  • Сложность всех алгоритмов линейна - что на самом деле неудивительно, поскольку они работают блочно. (Я хотел посмотреть, если метод чтения имеет значение, так что вы можете просто сравнить самые правильные значения).
  • SHA256 был медленнее, чем SHA512.
  • Я не исследовал случайность хэш-функций. Но вот хорошее сравнение хеш-функций, отсутствующих в ответе Иана Бойдса . Это указывает на то, что у CityHash есть некоторые проблемы в угловых случаях.

Источник, используемый для участков:

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

Алгоритмы SHA (включая SHA-256) предназначены для быстрой работы .

На самом деле их скорость иногда может быть проблемой. В частности, распространенным методом хранения токена, полученного из пароля, является запуск стандартного алгоритма быстрого хеширования 10 000 раз (сохранение хэша хэша хэша пароля ...).

#!/usr/bin/env ruby
require 'securerandom'
require 'digest'
require 'benchmark'

def run_random_digest(digest, count)
  v = SecureRandom.random_bytes(digest.block_length)
  count.times { v = digest.digest(v) }
  v
end

Benchmark.bmbm do |x|
  x.report { run_random_digest(Digest::SHA256.new, 1_000_000) }
end

Выход:

Rehearsal ------------------------------------
   1.480000   0.000000   1.480000 (  1.391229)
--------------------------- total: 1.480000sec

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)
yfeldblum
источник
57
Конечно, это довольно быстрый алгоритм криптографического хеширования . Но OP просто хочет хранить значения в хеш-таблице, и я не думаю, что криптографическая хеш-функция действительно подходит для этого.
Дин Хардинг
6
Вопрос, поднятый (как ни странно, теперь кажется), был предметом криптографических хеш-функций. Это то, на что я отвечаю.
yfeldblum
15
Просто чтобы отвлечь людей от идеи: «В частности, распространенная техника хранения токена, полученного из пароля, - запуск стандартного алгоритма быстрого хеширования 10 000 раз» - хотя это обычное явление, это просто глупо. Для этих сценариев разработаны алгоритмы, например bcrypt. Используйте правильные инструменты.
TC1
3
Криптографические хеши разработаны для обеспечения высокой пропускной способности, но это часто означает, что они требуют больших затрат на настройку, демонтаж .rodataи / или состояние. Когда вам нужен алгоритм для хеш-таблицы, у вас обычно есть очень короткие ключи и их много, но вам не нужны дополнительные гарантии криптографического ключа. Я сам использую измененный Дженкинс по отдельности.
Мирабилось
1
@ChrisMorgan: вместо использования криптографически безопасного хэша, HashTable DoS может быть решен гораздо более эффективно с помощью рандомизации хэшей, так что каждый запуск программ или даже в каждой хеш-таблице, так что данные не будут сгруппированы в одно и то же ведро каждый раз ,
Ли Райан
14

Я знаю, что есть такие вещи, как SHA-256 и тому подобное, но эти алгоритмы предназначены для обеспечения безопасности , что обычно означает, что они медленнее, чем алгоритмы, которые менее уникальны .

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

  1. Криптографические хеш-функции в идеале должны быть неотличимы от случайных ;
  2. Но с некриптографическими хеш-функциями желательно, чтобы они благоприятно взаимодействовали с вероятными входными данными .

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

На самом деле мы можем продемонстрировать это с помощью данных в ответе Яна Бойда и немного математики: проблема дня рождения . Формула для ожидаемого числа сталкивающихся пар, если вы nслучайным образом выбираете целые числа из набора [1, d]: (взято из Википедии):

n - d + d * ((d - 1) / d)^n

При nподключении = 216,553 и d= 2 ^ 32 мы получаем около 5,5 ожидаемых коллизий . Тесты Яна в основном показывают результаты в окрестностях, но с одним существенным исключением: большинство функций получили нулевые коллизии в последовательных числовых тестах. Вероятность случайного выбора 216 553 32-битных чисел и получения нулевых коллизий составляет около 0,43%. И это только для одной функции - здесь у нас есть пять различных семейств хэш-функций с нулевыми столкновениями!

Итак, что мы видим здесь, так это то, что проверенные Яном хеши благоприятно взаимодействуют с последовательным набором чисел, т. Е. Они распределяют минимально разные входные данные более широко, чем идеальная криптографическая хеш-функция. (Примечание: это означает, что графическая оценка Яна, что FNV-1a и MurmurHash2 «выглядят случайными» для него в наборе данных номеров, может быть опровергнута из его собственных данных. Нулевые коллизии в наборе данных такого размера для обеих хеш-функций, поразительно неслучайно!)

Это не удивительно, потому что это желательное поведение для многих применений хеш-функций. Например, ключи хеш-таблицы часто очень похожи; В ответе Яна упоминается проблема, с которой MSN когда-то сталкивалась с хеш-таблицами почтового индекса . Это использование, когда предотвращение столкновений на вероятных входах выигрывает у случайного поведения.

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

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

Поэтому для CRC опять же хорошо иметь меньше коллизий, чем случайных, при минимально разных входах. С крипто хешами это нет-нет!

sacundim
источник
10

Используйте SipHash . У него много желательных свойств:

  • Быстрый. Оптимизированная реализация занимает около 1 цикла на байт.

  • Secure. SipHash - это сильный PRF (псевдослучайная функция). Это означает, что он неотличим от случайной функции (если вы не знаете 128-битный секретный ключ). Следовательно:

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

    • Невосприимчивость к атакам типа «отказ в обслуживании» на основе хеш-функции.

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

Деми
источник
1
Не является ли SipHash излишним, если вам не нужна безопасность? Требуется 128-битный ключ, который является просто прославленным хешем. Не говоря уже о MurmurHash3 имеет 128-битный выход, а SipHash имеет только 64-битный выход. Очевидно, что больший дайджест имеет меньшую вероятность столкновения.
bryc
@ Bryc Разница в том, что SipHash будет продолжать вести себя хорошо, даже при злонамеренном вводе. Хеш-таблица на основе SipHash может использоваться для данных из потенциально враждебных источников и может использовать алгоритм, такой как линейное зондирование, который очень чувствителен к деталям хеш-функции.
Деми
9

Это зависит от данных, которые вы хэшируете. Некоторое хеширование лучше работает с конкретными данными, такими как текст. Некоторые алгоритмы хеширования были специально разработаны, чтобы быть подходящими для конкретных данных.

Пол Се однажды сделал быстрый хэш . Он перечисляет исходный код и объяснения. Но это уже было побито. :)

user712092
источник
6

Java использует этот простой алгоритм умножения и сложения:

Хеш-код для объекта String вычисляется как

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

используя INT арифметику, где s[i]является я -й символ строки, nдлина строки, и ^указывает , возведение в степень. (Значение хеша пустой строки равно нулю.)

Вероятно, есть намного лучшие, но это довольно широко распространено и кажется хорошим компромиссом между скоростью и уникальностью.

biziclop
источник
12
Я бы не использовал точно такой же, как здесь, поскольку с этим все еще относительно легко создавать коллизии. Это определенно не страшно, но есть гораздо лучшие. И если нет веских причин для совместимости с Java, его не следует выбирать.
Иоахим Зауэр
4
Если по какой-то причине вы все еще выберете этот способ хеширования, вы можете по крайней мере использовать лучшее простое число, например 92821, в качестве мультипликатора. Это значительно уменьшает коллизии. stackoverflow.com/a/2816747/21499
Ханс-Петер Стёрр
1
Вы могли бы также использовать FNV1a вместо этого. Это также простой хэш, основанный на умножении, но использующий множитель большего размера, который лучше рассеивает хеш.
Брай
4

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

Что касается реальных алгоритмов хеширования, то мой личный фаворит - FNV. 1

Вот пример реализации 32-битной версии на C:

unsigned long int FNV_hash(void* dataToHash, unsigned long int length)
{
  unsigned char* p = (unsigned char *) dataToHash;
  unsigned long int h = 2166136261UL;
  unsigned long int i;

  for(i = 0; i < length; i++)
    h = (h * 16777619) ^ p[i] ;

  return h;
}

источник
2
Вариант FNV-1a немного лучше со случайностью. Поменяйте местами порядок *и ^: h = (h * 16777619) ^ p[i]==>h = (h ^ p[i]) * 16777619
Ян Бойд