Какой алгоритм хеширования лучше всего подходит для уникальности и скорости?
Какой алгоритм хеширования лучше всего подходит для уникальности и скорости? Примеры (хорошие) использования включают хеш-словари.
Я знаю, что есть такие вещи, как SHA-256 и такие, но эти алгоритмы разработаны безопасно , что обычно означает, что они медленнее, чем алгоритмы, менее unique . Я хочу, чтобы алгоритм хэша был быстрым, но оставался достаточно уникальным, чтобы избежать столкновений.
11 ответов
Я проверил несколько разных алгоритмов, измеряя скорость и количество столкновений.
Я использовал три разных набора клавиш:
- Список из 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
и 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
Примечание . Опять же, я помещаю SuperFastHash
. Но никто не знает, какой тип 4 или типы 1, 3 и 5. Так что проще назвать их «случайными» GUID.
Зеркала всех английских слов
Если вы хотите создать хэш-карту из неизменяемого словаря, вы можете рассмотреть идеальное хеширование 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 .
Все функции 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 и т. д., но эти алгоритмы разработаны как безопасные , что обычно означает, что они медленнее, чем алгоритмы, эм> уникальный .
Предположение о том, что криптографические хеш-функции более уникальны, неверно, и на самом деле можно доказать, что он часто обращается назад на практике. По правде говоря:
- Криптографические хеш-функции в идеале должны быть неотличимы от случайных ;
- Но с некриптографическими хеш-функциями желательно, чтобы они взаимодействовали благоприятно с вероятными входами .
Это означает, что некриптографическая хеш-функция может иметь меньшее количество коллизий , чем криптографическая для «хороших» наборов данных, которые были созданы для них.
Мы можем на самом деле продемонстрировать это с помощью данных в ответе Иана Бойда и немного математики: проблема с днем рождения . Формула для ожидаемого числа встречных пар, если вы выбрали целые числа 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;
}