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

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

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

1231 голос | спросил Earlz 19 FebruaryEurope/MoscowbSat, 19 Feb 2011 03:03:26 +0300000000amSat, 19 Feb 2011 03:03:26 +030011 2011, 03:03:26

11 ответов


2230

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

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

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

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

Результаты

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

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

Примечания

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

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

Конфликты 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 показывает, насколько равномерно распределяются данные. Все хэш-функции показывают хорошее распределение при линейном сопоставлении таблицы:

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

<p> Или как <a href= Карта Гильберта ( XKCD всегда уместен ):

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

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

SDBM

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

<p> <strong> DJB2a </STRONG> </p>

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


Дополнительный "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.

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

ответил Ian Boyd 23 PMpMon, 23 Apr 2012 16:42:36 +040042Monday 2012, 16:42:36
49

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

ответил Damien 25 Mayam12 2012, 07:16:03
33

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

  

Если вы просто хотите иметь хорошую хеш-функцию и не можете ждать, 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;
}
ответил Dean Harding 19 FebruaryEurope/MoscowbSat, 19 Feb 2011 04:13:08 +0300000000amSat, 19 Feb 2011 04:13:08 +030011 2011, 04:13:08
26

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

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

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

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

  

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

ответил Vipin Parakkat 25 Maypm12 2012, 14:29:36
18

Алгоритмы 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)
ответил yfeldblum 19 FebruaryEurope/MoscowbSat, 19 Feb 2011 03:21:30 +0300000000amSat, 19 Feb 2011 03:21:30 +030011 2011, 03:21:30
15

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

Отдельные графики немного отличаются в методе чтения и могут игнорироваться здесь, поскольку все файлы были сохранены в 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 есть некоторые проблемы в угловых случаях.

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

ответил Sahib 22 J000000Tuesday14 2014, 22:00:29
10
  

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

ответил sacundim 25 J000000Monday16 2016, 23:11:44
9

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

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

ответил user712092 4 PM00000020000002231 2011, 14:26:22
8

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

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

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

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

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

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

ответил Demi 21 AMpThu, 21 Apr 2016 03:53:57 +030053Thursday 2016, 03:53:57
5

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

  

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

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

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

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

ответил biziclop 19 FebruaryEurope/MoscowbSat, 19 Feb 2011 03:23:04 +0300000000amSat, 19 Feb 2011 03:23:04 +030011 2011, 03:23:04
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;
}
ответил 19 FebruaryEurope/MoscowbSat, 19 Feb 2011 07:42:34 +0300000000amSat, 19 Feb 2011 07:42:34 +030011 2011, 07:42:34

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132