Który algorytm mieszania jest najlepszy dla wyjątkowości i szybkości?


1388

Który algorytm mieszania jest najlepszy dla wyjątkowości i szybkości? Przykłady (dobrych) zastosowań obejmują słowniki skrótów.

Wiem, że istnieją rzeczy takie jak SHA-256 i tym podobne, ale te algorytmy są zaprojektowane tak, aby były bezpieczne , co zwykle oznacza, że ​​są wolniejsze niż algorytmy mniej unikalne . Chcę algorytmu skrótu zaprojektowanego tak, aby był szybki, ale pozostać dość unikalny, aby uniknąć kolizji.


9
W jakim celu bezpieczeństwo lub inne?
Orbling

19
@Orbling, do implementacji słownika skrótów. Tak więc kolizje powinny być ograniczone do minimum, ale nie ma to żadnego celu bezpieczeństwa.
Earlz

4
Pamiętaj, że będziesz musiał spodziewać się co najmniej niektórych kolizji w tabeli skrótów, w przeciwnym razie tabela będzie musiała być ogromna, aby móc obsłużyć nawet stosunkowo niewielką liczbę kluczy ...
Dean Harding

19
Wspaniały post! Czy mógłbyś także sprawdzić xxHash Yanna Colleta (twórca lub LZ4), który jest dwa razy szybszy niż Murmur? Strona główna: code.google.com/p/xxhash Więcej informacji: fastcompression.blogspot.fr/2012/04/…

24
@zvrba Zależy od algorytmu. bcrypt ma działać wolno.
Izkata,

Odpowiedzi:


2461

Testowałem różne algorytmy, mierząc prędkość i liczbę kolizji.

Użyłem trzech różnych zestawów kluczy:

Dla każdego korpusu rejestrowano liczbę kolizji i średni czas haszowania.

Testowałem:

Wyniki

Każdy wynik zawiera średni czas mieszania i liczbę kolizji

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

Uwagi :

Czy faktycznie dochodzi do kolizji?

Tak. Zacząłem pisać mój program testowy, aby sprawdzić, czy rzeczywiście występują kolizje skrótów - i nie są to tylko teoretyczne konstrukcje. Rzeczywiście się zdarzają:

Zderzenia FNV-1

  • creamwove koliduje z quists

Zderzenia FNV-1a

  • costarring koliduje z liquid
  • declinate koliduje z macallums
  • altarage koliduje z zinke
  • altarages koliduje z zinkes

Kolizje Murmur2

  • cataract koliduje z periti
  • roquette koliduje z skivie
  • shawl koliduje z stormbound
  • dowlases koliduje z tramontane
  • cricketings koliduje z twanger
  • longans koliduje z whigs

Zderzenia DJB2

  • hetairas koliduje z mentioner
  • heliotropes koliduje z neurospora
  • depravement koliduje z serafins
  • stylist koliduje z subgenera
  • joyful koliduje z synaphea
  • redescribed koliduje z urites
  • dram koliduje z vivency

Zderzenia DJB2a

  • haggadot koliduje z loathsomenesses
  • adorablenesses koliduje z rentability
  • playwright koliduje z snush
  • playwrighting koliduje z snushing
  • treponematoses koliduje z waterbeds

Zderzenia CRC32

  • codding koliduje z gnu
  • exhibiters koliduje z schlager

Kolizje SuperFastHash

  • dahabiah koliduje z drapability
  • encharm koliduje z enclave
  • grahams koliduje z gramary
  • ... snip 79 kolizji ...
  • night koliduje z vigil
  • nights koliduje z vigils
  • finks koliduje z vinic

Randomnessification

Inną subiektywną miarą jest losowe rozmieszczenie skrótów. Odwzorowanie powstałych tabel skrótów pokazuje, jak równomiernie dane są rozmieszczone. Wszystkie funkcje skrótu wykazują dobry rozkład podczas liniowego mapowania tabeli:

Wpisz opis zdjęcia tutaj

Lub jako mapa Hilberta ( XKCD jest zawsze odpowiedni ):

Wpisz opis zdjęcia tutaj

Z wyjątkiem gdy mieszania ciągów numer ( "1", "2", ..., "216553") (na przykład kody pocztowe ), gdzie wzorce zaczynają się pojawiać w większości algorytmów mieszaja:

SDBM :

Wpisz opis zdjęcia tutaj

DJB2a :

Wpisz opis zdjęcia tutaj

FNV-1 :

Wpisz opis zdjęcia tutaj

Wszystkie oprócz FNV-1a , które nadal wyglądają dla mnie dość losowo:

Wpisz opis zdjęcia tutaj

W rzeczywistości Murmur2 wydaje się mieć jeszcze lepszą losowość Numbersniż FNV-1a:

Wpisz opis zdjęcia tutaj

Kiedy patrzę na FNV-1amapę „liczbową”, myślę, że widzę subtelne pionowe wzory. Dzięki Murmurowi nie widzę żadnych wzorów. Co myślisz?


Dodatek *w tabeli wskazuje, jak zła jest losowość. Z FNV-1abycia najlepszym, a DJB2xbędąc najgorsze:

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

Pierwotnie napisałem ten program, aby zdecydować, czy w ogóle muszę się martwić o kolizje: tak.

A potem okazało się, że funkcje haszujące były wystarczająco losowe.

Algorytm FNV-1a

Skrót FNV1 występuje w wariantach, które zwracają skróty 32, 64, 128, 256, 512 i 1024 bitów.

Algorytm FNV-1a jest:

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

Gdzie stałe FNV_offset_basisi FNV_primezależą od żądanego rozmiaru zwracanej wartości skrótu:

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

Szczegółowe informacje można znaleźć na głównej stronie FNV .

Wszystkie moje wyniki dotyczą wariantu 32-bitowego.

FNV-1 lepszy niż FNV-1a?

Nie. FNV-1a jest lepszy. Podczas używania angielskiego słowa corpus doszło do większej liczby kolizji z FNV-1a:

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

Teraz porównaj małe i wielkie litery:

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

W tym przypadku FNV-1a nie jest „400%” gorszy niż FN-1, tylko 20% gorzej.

Myślę, że ważniejsze jest to, że istnieją dwie klasy algorytmów, jeśli chodzi o kolizje:

  • rzadkie kolizje : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
  • typowe kolizje : SuperFastHash, Loselose

A potem jest to, jak równomiernie rozłożone są skróty:

  • znakomita dystrybucja: Murmur2, FNV-1a, SuperFastHas
  • doskonała dystrybucja: FNV-1
  • dobra dystrybucja: SDBM, DJB2, DJB2a
  • okropna dystrybucja: Loselose

Aktualizacja

Szmer? Jasne, czemu nie


Aktualizacja

@ whatshisname zastanawiał się, jak będzie działać CRC32 , dodał liczby do tabeli.

CRC32 jest całkiem niezły . Mało kolizji, ale wolniej, i narzut 1-krotnej tabeli odnośników.

Zniszcz wszystkie błędne informacje o dystrybucji CRC - moje złe


Do dzisiaj miałem używać FNV-1a jako mojego de facto algorytmu haszującego tablicę skrótów. Ale teraz przełączam się na Murmur2:

  • Szybciej
  • Lepsza losowość wszystkich klas danych wejściowych

I naprawdę, naprawdę mam nadzieję, że coś jest nie tak z SuperFastHashalgorytmem, który znalazłem ; szkoda być popularnym.

Aktualizacja: Od głównej MurmurHash3 w Google :

(1) - SuperFastHash ma bardzo słabe właściwości kolizji, które zostały udokumentowane gdzie indziej.

Myślę, że to nie tylko ja.

Aktualizacja: Zrozumiałem, dlaczego Murmurjest szybszy od innych. MurmurHash2 działa na czterech bajtach jednocześnie. Większość algorytmów jest bajt po bajcie :

for each octet in Key
   AddTheOctetToTheHash

Oznacza to, że gdy klucze stają się dłuższe, Murmur ma szansę zabłysnąć.


Aktualizacja

Identyfikatory GUID są zaprojektowane tak, aby były unikalne, a nie losowe

Terminowy post Raymonda Chena potwierdza fakt, że „losowe” identyfikatory GUID nie są przeznaczone do ich losowości. One lub ich część nie są odpowiednie jako klucz skrótu:

Nawet algorytm GUID w wersji 4 nie jest gwarantowany jako nieprzewidywalny, ponieważ algorytm nie określa jakości generatora liczb losowych. Artykuł w Wikipedii dotyczący GUID zawiera podstawowe badania, które sugerują, że przyszłe i poprzednie GUID można przewidzieć na podstawie wiedzy o stanie generatora liczb losowych, ponieważ generator nie jest silny kryptograficznie.

Losowość to nie to samo, co unikanie kolizji; dlatego błędem byłoby wymyślić własny algorytm „mieszający”, przyjmując pewien podzbiór „losowego” przewodnika:

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);
}

Uwaga : Znów wstawiłem „przypadkowy GUID” w cudzysłowie, ponieważ jest to „losowy” wariant GUID. Bardziej dokładny opis byłby Type 4 UUID. Ale nikt nie wie, jaki jest typ 4 lub typy 1, 3 i 5. Łatwiej więc nazwać je „losowymi” identyfikatorami GUID.

Lustra wszystkich angielskich słów


41
Byłoby naprawdę interesujące zobaczyć, jak SHA się porównuje, nie dlatego, że jest dobrym kandydatem na algorytm mieszający, ale byłoby naprawdę interesujące zobaczyć, jak dowolny skrót kryptograficzny porównuje się z tymi stworzonymi dla algorytmów prędkości.
Michael

8
Niedawno robił obchód nowy hash o nazwie „xxHash” autorstwa Yanna Colleta. Zawsze jestem podejrzany o nowy skrót. Byłoby ciekawie zobaczyć to w swoim porównaniu (jeśli nie masz dość ludzi sugerujących losowe skróty, o których słyszeli, że mają zostać dodane ...)
th_in_gs

7
W rzeczy samej. Liczby wydajności ogłoszone na stronie projektu xxHash wyglądają imponująco, być może zbyt wiele, aby mogły być prawdziwe. Przynajmniej jest to projekt typu open source: code.google.com/p/xxhash
ATTracker

9
Cześć Ian, moja implementacja SuperFastHash w Delphi jest poprawna. Podczas implementacji stworzyłem zestaw testowy w C i Delphi, aby porównać wyniki mojej implementacji i implementacji referencyjnej. Nie ma różnic. Widzisz więc rzeczywistą złą wartość skrótu ... (Dlatego też opublikowałem implementację MurmurHash : landman-code.blogspot.nl/2009/02/... )
Davy Landman

19
Czy plakat zdaje sobie sprawę, że nie jest to po prostu niesamowita odpowiedź - to de facto światowy zasób referencyjny na ten temat? Za każdym razem, gdy muszę radzić sobie z hashami, to rozwiązuje mój problem tak szybko i autorytatywnie, że nigdy więcej nie potrzebuję niczego innego.
MaiaVictor

59

Jeśli chcesz utworzyć mapę skrótów z niezmiennego słownika, możesz rozważyć idealne haszowanie https://en.wikipedia.org/wiki/Perfect_hash_function - podczas budowy funkcji skrótu i ​​tabeli skrótów możesz zagwarantować, dla danego zestawu danych, że nie będzie kolizji.


2
Oto więcej informacji na temat (minimalnego) Perfect Hashing burtleburtle.net/bob/hash/perfect.html w tym danych o wydajności, chociaż nie używa najnowszego procesora itp.
Ellie Kesselman

4
To dość oczywiste, ale warto zauważyć, że aby zagwarantować brak kolizji, klucze musiałyby mieć taki sam rozmiar jak wartości, chyba że istnieją ograniczenia dotyczące wartości, na których algorytm może wykorzystać.
devios1

1
@ devios1 Twoje oświadczenie nie ma znaczenia. Po pierwsze, wartości w tablicy skrótów, doskonałe lub nie, są niezależne od kluczy. Po drugie, idealna tablica skrótów jest po prostu liniową tablicą wartości, indeksowaną przez wynik funkcji, która została tak spreparowana, aby wszystkie indeksy były unikalne.
Jim Balter,

1
@MarcusJ Idealne hashowanie jest zwykle używane z mniej niż 100 kluczami, ale spójrz na cmph.sourceforge.net ... wciąż daleko od twojego zasięgu.
Jim Balter,

1
@DavidCary Nic w twoim linku nie obsługuje twojego roszczenia. Być może pomyliłeś O (1) z „brakiem kolizji”, ale wcale nie są takie same. Oczywiście idealne mieszanie nie gwarantuje kolizji, ale wymaga, aby wszystkie klucze były znane z wyprzedzeniem i że było ich stosunkowo niewiele. (Ale patrz link do cmph powyżej.)
Jim Balter,

34

Oto lista funkcji skrótu, ale krótka wersja to:

Jeśli chcesz po prostu mieć dobrą funkcję skrótu i ​​nie możesz się doczekać, djb2to jedna z najlepszych funkcji skrótu, jakie znam. Ma doskonałą dystrybucję i szybkość dla wielu różnych zestawów kluczy i rozmiarów tabel

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
W rzeczywistości djb2 jest wrażliwy na zero, ponieważ większość takich prostych funkcji skrótu pozwala łatwo przerwać takie skróty. Ma złe nastawienie, zbyt wiele kolizji i złą dystrybucję, psuje się w większości tandetnych testów jakości: patrz github.com/rurban/smhasher/blob/master/doc/bernstein Jego baza danych cdb używa go, ale nie użyłbym tego z dostępem publicznym.
rurban

2
DJB jest dość zły z punktu widzenia wydajności i dystrybucji. Nie użyłbym tego dzisiaj.
Conrad Meyer

@ ConradMeyer Założę się, że DJB może zostać przyspieszony trzykrotnie, tak jak w moim pytaniu, a wtedy prawdopodobnie pokonałby większość użytecznych algorytmów. Jeśli chodzi o dystrybucję, zgadzam się. Hash powodujący kolizje nawet dla dwóch ciągów liter nie może być naprawdę dobry.
maaartinus

28

CityHash firmy Google to algorytm, którego szukasz. Nie nadaje się do kryptografii, ale jest dobry do generowania unikatowych skrótów.

Przeczytaj blog, aby uzyskać więcej informacji, a kod jest dostępny tutaj .

CityHash jest napisany w C ++. Jest też zwykły port C .

O obsłudze 32-bitowej:

Wszystkie funkcje CityHash są dostrojone dla procesorów 64-bitowych. To powiedziawszy, będą działać (z wyjątkiem nowych, które używają SSE4.2) w kodzie 32-bitowym. Nie będą jednak bardzo szybkie. Możesz użyć Murmur lub czegoś innego w 32-bitowym kodzie.


11
Czy CityHash jest wymawiane podobnie jak „City Sushi?”
Eric

2
Spójrz także na SipHash, który ma zastąpić MurmurHash / CityHash / etc. : 131002.net/siphash
Török Edwin

3
Zobacz także FarmHash, następca CitHash. code.google.com/p/farmhash
stevendaniels

7
xxHash twierdzi, że jest 5 razy szybszy niż CityHash.
Clay Bridges

plain C portlink jest zepsuty
makerj

20

Sporządziłem krótkie porównanie różnych algorytmów haszujących podczas haszowania plików.

Poszczególne wykresy różnią się tylko nieznacznie metodą odczytu i można je tutaj zignorować, ponieważ wszystkie pliki zostały zapisane w pliku tmpfs. Dlatego, jeśli zastanawiasz się, test nie był związany z IO.

Algorytmy obejmują: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Wnioski:

  • Niekryptograficzne funkcje skrótu, takie jak Murmur3, Cityhash i Spooky, są dość blisko siebie. Należy zauważyć, że Cityhash może być szybszy na procesorach z CRCinstrukcją SSE 4.2s , których mój procesor nie ma. SpookyHash był w moim przypadku zawsze trochę przed CityHash.
  • Wydaje się, że MD5 stanowi dobry kompromis podczas korzystania z funkcji skrótu kryptograficznego, chociaż SHA256 może być bardziej bezpieczny w przypadku luk MD5 i SHA1 w przypadku kolizji .
  • Złożoność wszystkich algorytmów jest liniowa - co naprawdę nie jest zaskakujące, ponieważ działają one blokowo. (Chciałem zobaczyć, czy metoda odczytu ma znaczenie, więc możesz po prostu porównać wartości skrajnie prawe).
  • SHA256 był wolniejszy niż SHA512.
  • Nie badałem losowości funkcji skrótu. Ale oto dobre porównanie funkcji skrótu, których brakuje w odpowiedzi Iana Boydsa . Wskazuje to, że CityHash ma pewne problemy w sprawach narożnych.

Źródło użyte do wykresów:


1
Wykres skali liniowej odcina etykietę osi y, która mówi, jaką ilość drukuje. Myślę, że prawdopodobnie byłby to „czas w sekundach”, taki sam jak skala logarytmiczna. Warto to naprawić.
Craig McQueen,

18

Algorytmy SHA (w tym SHA-256) są zaprojektowane tak, aby były szybkie .

W rzeczywistości ich prędkość może czasem stanowić problem. W szczególności powszechną techniką przechowywania tokenu pochodnego hasła jest uruchomienie standardowego algorytmu szybkiego hashowania 10 000 razy (przechowywanie skrótu skrótu skrótu skrótu ... hasła).

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

Wynik:

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

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)

57
Z pewnością jest to stosunkowo szybki algorytm szyfrujący . Ale OP chce po prostu przechowywać wartości w tablicy mieszającej i nie sądzę, by kryptograficzna funkcja skrótu była do tego odpowiednia.
Dean Harding

6
Pojawiło się pytanie (stycznie, wydaje się teraz) temat kryptograficznych funkcji skrótu. Na to trochę odpowiadam.
yfeldblum

15
Aby zniechęcić ludzi do pomysłu „W szczególności, powszechną techniką przechowywania tokena pochodzącego z hasła jest uruchomienie standardowego algorytmu szybkiego mieszania 10 000 razy” - choć często jest to po prostu głupie. Istnieją algorytmy zaprojektowane dla tych scenariuszy, np bcrypt. Użyj odpowiednich narzędzi.
TC1

3
Hashery kryptograficzne mają wysoką przepustowość, ale często oznacza to, że mają wysokie .rodatakoszty konfiguracji, porzucenia i / lub stanu. Kiedy potrzebujesz algorytmu dla tablicy mieszającej, zwykle masz bardzo krótkie klucze i wiele z nich, ale nie potrzebujesz dodatkowych gwarancji kryptograficznych. Sam korzystam z ulepszonej wersji Jenkinsa.
mirabilos,

1
@ChrisMorgan: zamiast używać kryptograficznie bezpiecznego skrótu, HashTable DoS można rozwiązać o wiele bardziej efektywnie za pomocą losowej funkcji skrótu, dzięki czemu każde uruchomienie programu lub nawet na każdym hashtable, aby dane nie były grupowane w tym samym segmencie za każdym razem .
Lie Ryan,

14

Wiem, że istnieją rzeczy takie jak SHA-256 i tym podobne, ale te algorytmy są zaprojektowane tak, aby były bezpieczne , co zwykle oznacza, że ​​są wolniejsze niż algorytmy mniej unikalne .

Założenie, że kryptograficzne funkcje skrótu są bardziej unikalne, jest błędne i w rzeczywistości można wykazać, że w praktyce często jest ono cofane. Wprawdzie:

  1. Funkcje skrótu kryptograficznego idealnie powinny być nierozróżnialne od przypadkowych ;
  2. Ale w przypadku niekryptograficznych funkcji skrótu pożądane jest, aby korzystały one z interakcji z prawdopodobnymi danymi wejściowymi .

Co oznacza, że ​​nieszyfrowa funkcja skrótu może mieć mniej kolizji niż kryptograficzna dla „dobrego” zestawu danych - zestawów danych, dla których została zaprojektowana.

Możemy to właściwie wykazać za pomocą danych zawartych w odpowiedzi Iana Boyda i odrobiny matematyki: problem urodzinowy . Wzór na oczekiwaną liczbę kolidujących par, jeśli wybierzesz nlosowo liczby całkowite ze zbioru, [1, d]jest następujący (wzięty z Wikipedii):

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

Podłączając n= 216 553 i d= 2 ^ 32 otrzymujemy około 5,5 oczekiwanych kolizji . Testy Iana przeważnie pokazują wyniki w tej okolicy, ale z jednym dramatycznym wyjątkiem: większość funkcji uzyskała zerową kolizję w kolejnych testach liczbowych. Prawdopodobieństwo losowego wyboru 216 553 liczb 32-bitowych i uzyskania zerowych kolizji wynosi około 0,43%. I to tylko dla jednej funkcji - tutaj mamy pięć różnych rodzin funkcji skrótu z zerowymi kolizjami!

Widzimy więc, że skróty, które testował Ian, działają korzystnie z zestawem danych z kolejnymi liczbami - tzn. Rozpraszają minimalnie różne dane wejściowe szerzej niż idealna funkcja skrótu kryptograficznego. (Uwaga dodatkowa: oznacza to, że graficzną ocenę Iana, że ​​FNV-1a i MurmurHash2 „wyglądają mu losowo” w zestawie danych liczbowych, można odrzucić na podstawie jego własnych danych. Zero zderzeń na zestawie danych tego rozmiaru dla obu funkcji skrótu, jest uderzająco nielosowy!)

Nie jest to niespodzianką, ponieważ jest to pożądane zachowanie dla wielu zastosowań funkcji skrótu. Na przykład klucze tabeli skrótów są często bardzo podobne; Odpowiedź Iana wspomina o problemie, jaki MSN miał kiedyś z tablicami skrótu kodów pocztowych . Jest to zastosowanie, w którym unikanie kolizji na prawdopodobnych danych wejściowych wygrywa z zachowaniem losowym.

Innym pouczającym porównaniem tutaj jest kontrast w celach projektowych między CRC a kryptograficznymi funkcjami skrótu:

  • CRC jest przeznaczony do wychwytywania błędów wynikających z głośnych kanałów komunikacyjnych , które prawdopodobnie będą niewielką liczbą bitów;
  • Skrypty kryptograficzne są zaprojektowane do przechwytywania modyfikacji dokonywanych przez złośliwych atakujących , którym przydzielono ograniczone zasoby obliczeniowe, ale dowolnie sprytnie.

Więc dla CRC to kolejny dobry mieć mniej kolizji niż losowo minimalnie różnych wejść. W przypadku skrótów kryptograficznych jest to nie-nie!


10

Użyj SipHash . Ma wiele pożądanych właściwości:

  • Szybki. Zoptymalizowana implementacja zajmuje około 1 cyklu na bajt.

  • Bezpieczne. SipHash jest silnym PRF (funkcja pseudolosowa). Oznacza to, że nie można go odróżnić od funkcji losowej (chyba że znasz 128-bitowy tajny klucz). W związku z tym:

    • Nie musisz się martwić, że sondy tabeli skrótów staną się liniowe z powodu kolizji. Dzięki SipHash wiesz , że średnio uzyskasz średnią wydajność, niezależnie od danych wejściowych.

    • Odporność na ataki typu odmowa usługi oparte na haszowaniu.

    • Możesz użyć SipHash (szczególnie wersja ze 128-bitowym wyjściem) jako MAC (Message Authentication Code). Jeśli otrzymasz wiadomość i znacznik SipHash, a znacznik jest taki sam, jak po uruchomieniu SipHash z tajnym kluczem, to wiesz, że ktokolwiek stworzył skrót, był również w posiadaniu twojego tajnego klucza i że ani wiadomość, ani hash został zmieniony od tego czasu.


1
Czy nie jest przesada SipHash, chyba że potrzebujesz bezpieczeństwa? Wymaga 128-bitowego klucza, który jest po prostu uwielbionym ziarnem mieszania. Nie wspominając o MurmurHash3 ma 128-bitowe wyjście, a SipHash tylko 64-bitowe wyjście. Oczywiście większy skrót ma mniejszą szansę na kolizję.
bryc

@bryc Różnica polega na tym, że SipHash nadal będzie dobrze się zachowywał, nawet przy złośliwych danych wejściowych. Tabela skrótów oparta na SipHash może być używana do danych z potencjalnie wrogich źródeł i może wykorzystywać algorytm taki jak sondowanie liniowe, które jest bardzo wrażliwe na szczegóły funkcji skrótu.
Demi

9

To zależy od haszowanych danych. Niektóre skróty działają lepiej z określonymi danymi, takimi jak tekst. Niektóre algorytmy mieszające zostały specjalnie zaprojektowane tak, aby były odpowiednie dla określonych danych.

Paul Hsieh kiedyś zrobił szybki skrót . Wymienia kod źródłowy i objaśnienia. Ale już zostało pobite. :)


6

Java używa tego prostego algorytmu wielokrotnego dodawania i dodawania:

Kod skrótu dla obiektu String jest obliczany jako

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

używając int arytmetyczne, gdzie s[i]jest i -tego postaci napisu, nto długość łańcucha, i ^wskazuje potęgowanie. (Wartość skrótu pustego ciągu wynosi zero).

Prawdopodobnie są o wiele lepsze, ale jest to dość powszechne i wydaje się być dobrym kompromisem między szybkością a wyjątkowością.


12
Nie użyłbym dokładnie tego samego, którego tu użyłem, ponieważ nadal jest stosunkowo łatwo tworzyć z tym kolizje. To zdecydowanie nie jest straszne, ale są znacznie lepsze. A jeśli nie ma istotny powód, aby być kompatybilny z Java, powinno nie być wybrane.
Joachim Sauer

4
Jeśli nadal z jakiegoś powodu wybierzesz ten sposób mieszania, możesz przynajmniej użyć lepszej liczby pierwszej, takiej jak 92821, jako multiplikatora. To znacznie zmniejsza kolizje. stackoverflow.com/a/2816747/21499
Hans-Peter Störr

1
Równie dobrze możesz użyć FNV1a. Jest to również prosty skrót oparty na pomnożeniu, ale wykorzystuje większy mnożnik, który lepiej rozprasza skrót.
bryc

4

Po pierwsze, dlaczego musisz wdrożyć swój własny skrót? W przypadku większości zadań powinieneś uzyskać dobre wyniki ze strukturami danych ze standardowej biblioteki, zakładając, że dostępna jest implementacja (chyba że robisz to tylko dla własnej edukacji).

Jeśli chodzi o rzeczywiste algorytmy mieszające, moim ulubionym jest FNV. 1

Oto przykładowa implementacja 32-bitowej wersji w 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
Wariant FNV-1a jest nieco lepszy z przypadkowością. Zamień kolejność *i ^: h = (h * 16777619) ^ p[i]==>h = (h ^ p[i]) * 16777619
Ian Boyd
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.