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

Я использовал три разных набора клавиш:

• Список из 216 553 английских слов (в нижнем регистре)
• Цифры "1" до "216553" (думаю, почтовые индексы и как плохой хеш снял msn.com )
• 216,553 «случайный» (т. е. тип 4 uuid ) GUIDs

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

Я тестировал:

• DJB2
• DJB2a (вариант с использованием xor, а не +) литий>
• FNV-1 (32-разрядная версия)
• FNV-1a (32-разрядная версия)
• SDBM
• CRC32
• Murmur2 (32-разрядная версия)
• SuperFastHash

Результаты

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

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

Примечания

• алгоритм LoseLose (где hash = hash + character) действительно ужасен . Все сталкивается с теми же 1,375 ведрами.
• SuperFastHash быстрый, с вещами, выглядящими довольно разбросанными; по моей доброте столкновений number . Я надеюсь, что парень, который портировал его, получил что-то не так; это довольно плохо
• CRC32 является довольно хорошим . Медленнее и таблица поиска 1k.

Действительно ли происходят столкновения?

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

Конфликты FNV-1

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

Конфликты FNV-1a

• 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
• ... snip 79 коллизий ...
• night сталкивается с vigil
• nights сталкивается с vigils
• finks сталкивается с vinic

Randomnessification

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

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

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

SDBM

думаю вижу тонкие вертикальные шаблоны. С Мурмуром я вообще не вижу шаблонов. Как вы думаете?

Дополнительный "216553" в приведенной выше таблице обозначает, насколько плохая случайность. Если Numbers является лучшим, а FNV-1a хуже:

FNV-1a

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

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

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

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

алгоритм FNV-1a :

*

Если константы FNV-1a и DJB2x зависят от требуемого размера хеша возврата:

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

Подробнее см. главную страницу FNV .

Как практический вопрос:

• 32-бит hash = FNV_offset_basis for each octetOfData to be hashed hash = hash xor octetOfData hash = hash * FNV_prime return hash ,
• 64-разрядный FNV_offset_basis и
• 128-битный FNV_prime может быть полезен

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

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

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

Hash Size    Prime                       Offset
===========  =========================== =================================
32-bit       16777619                    2166136261
64-bit       1099511628211               14695981039346656037
128-bit      309485009821345068724781371 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

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

UInt32

В этом случае 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 в качестве моего хэш-хеширования de facto . Но теперь я перехожу к Murmur2:

• Быстрее
• Лучше randomnessification всех классов ввода

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

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

  

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

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

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

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

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

Обновление

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

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

  

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

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

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

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

Зеркала всех английских слов

• https://web.archive.org/web /20070221060514/http://www.sitopreferito.it/html/all_english_words.html
• https://drive.google.com/file/d/0B3BLwu7Vb2U-dEw1VkUxc3U4SG8 /смотреть? УСП = совместное использование

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

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

  

Если вы просто хотите иметь хорошую хеш-функцию и не можете ждать, 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;
}

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

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

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

О 32-разрядной поддержке:

  

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

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

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

#!/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)

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

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

• Линейная шкала
• Логарифмический масштаб

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

Выводы:

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

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

• https://github.com/sahib/rmlint/tree/gh-pages/участки (извините за уродливый код)

  

Я знаю, что есть такие вещи, как 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%. И это только для одной функции - здесь мы имеем пять различных семейств хеш-функций с нулевыми столкновениями!

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

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

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

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

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

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

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

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

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

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

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

  • Иммунитет к атакам отказа в обслуживании, основанным на хеше.

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

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

  

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

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

     

с использованием int арифметики, где s[i] является i â € n - это длина строки, а n указывает на возведение в степень. (Хэш-значение пустой строки равно нулю.)

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

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

Насколько эффективны алгоритмы хэширования, моим личным фаворитом является 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;
}