Przetestowałem kilka różnych algorytmów, mierząc szybkość i liczbę kolizji .

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

• Lista 216 553 angielskich słów ^{🕗  archiwum} (małymi literami)
• Liczby "1" do "216553" (pomyśl o kodach pocztowych i jak słaby hash zniszczył msn.com ^{🕗  archiwum} )
• 216,553 ” losowe „(tj. wpisz 4 uuid ) identyfikatory GUID

Dla każdego korpusu, liczba kolizji i średni czas spędzony na haszowaniu zostało nagrane.

Przetestowałem:

• DJB2
• DJB2a (wariant wykorzystujący xor zamiast +)
• FNV-1 (32-bitowy)
• FNV-1a (32-bitowy)
• SDBM
• CRC32
• Murmur2 (32-bitowy)
• SuperFastHash

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 :

• Algorytm LoseLose (gdzie hash = hash + znak) jest naprawdę okropny . Wszystko zderza się w tych samych 1375 zasobnikach.
• SuperFastHash jest szybki, a rzeczy wyglądają na dość rozproszone; na mój Boże zderzenia liczby . Mam nadzieję, że facet, który go przeportował, zrobił coś nie tak; jest bardzo źle
• CRC32 jest całkiem niezłe . Wolniej i 1k tablica przeglądowa

Czy faktycznie zdarzają się kolizje?

Tak. Zacząłem pisać swój program testowy, aby sprawdzić, czy kolizje hash faktycznie się zdarzają – i nie są tylko konstrukcją teoretyczną.Rzeczywiście się zdarzają:

Kolizje FNV-1

• creamwove koliduje z quists

FNV -1a kolizje

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

Kolizje szmerów2

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

Kolizje 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

Kolizje DJB2a

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

Kolizje CRC32

• codding koliduje z gnu
• exhibiters koliduje z schlager

Kolizje SuperFastHash

• dahabiah koliduje z drapability
• encharm koliduje z enclave
• grahams koliduje z gramary
• … wyciąć 79 kolizje …
• night koliduje z vigil
• koliduje z vigils
• finks koliduje z vinic

Losowość

Inną subiektywną miarą jest to, jak losowo rozmieszczone są hashe. Odwzorowanie wynikowych HashTables pokazuje, jak równomiernie rozprowadzane są dane. Wszystkie funkcje skrótu pokazują dobrą dystrybucję podczas liniowego mapowania tabeli:

Lub jako Mapa Hilberta ( XKCD jest zawsze aktualna ):

Z wyjątkiem sytuacji, gdy haszowanie ciągów liczb ("1", "2", …, "216553") (na przykład kody pocztowe ), gdzie zaczynają się wzorce pojawia się w większości algorytmów haszujących:

SDBM :

DJB2a :

FNV-1 :

Wszystkie oprócz

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 konstruowania funkcji skrótu i tablicy mieszającej można zagwarantować, że dla danego zbioru danych nie będzie kolizji.

Komentarze

• Tutaj ' więcej informacji na temat (minimalnego) idealnego haszowania burtleburtle.net/bob/hash/perfect.html , w tym dane dotyczące wydajności, chociaż nie ' nie używa najnowszego procesora itp.
• Jest to ' dość oczywiste, ale warto zauważyć, że aby zagwarantować brak kolizji, klucze musiałyby mieć ten sam rozmiar co wartości, chyba że th Istnieją ograniczenia wartości, na których algorytm może wykorzystać.
• @ devios1 Twoje stwierdzenie jest bez znaczenia. Po pierwsze, wartości w tabeli skrótów, idealne lub nie, są niezależne od kluczy. Po drugie, idealna tablica mieszająca to po prostu liniowa tablica wartości indeksowanych przez wynik funkcji, która została utworzona w taki sposób, że wszystkie indeksy są unikalne.
• @MarcusJ Idealne mieszanie jest zwykle używane z mniej niż 100 klucze, ale spójrz na cmph.sourceforge.net … wciąż daleko poniżej Twojego zasięgu.
• @DavidCary Nic na Twoim link popiera Twoje roszczenie. Prawdopodobnie pomyliłeś O (1) z ” brakiem kolizji „, ale nie są one ' t w ogóle to samo. Oczywiście idealne haszowanie gwarantuje brak kolizji, ale wymaga, aby wszystkie klucze były znane z wyprzedzeniem i było ich stosunkowo niewiele. (Ale zobacz link do cmph powyżej.)

Tutaj jest lista funkcji haszujących, ale krótka wersja to:

Jeśli chcesz mieć dobrą funkcję haszującą i nie mogę się doczekać, djb2 jest jedną z najlepszych funkcji skrótu ciągów znaków, jakie znam. Ma doskonałą dystrybucję i szybkość w wielu różnych zestawach 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; } 

Komentarze

• W rzeczywistości djb2 jest wrażliwy na zero, jak większość takich prostych funkcji skrótu, więc możesz łatwo złamać takie skróty.Ma złe nastawienie, zbyt wiele kolizji i złą dystrybucję, psuje się w większości drobniejszych testów jakości: patrz github.com/rurban/smhasher/blob/master/doc/bernstein Używa go jego baza danych cdb, ale nie ' nie używałbym go z dostępem publicznym.
• DJB jest dość kiepski z punktu widzenia wydajności i dystrybucji. Nie ' nie użyłbym go dzisiaj.
• @ConradMeyer I ' d zakład, DJB można przyspieszyć przez trzykrotnie, tak jak w moim pytaniu , a następnie ' d prawdopodobnie pokonuje 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 ' nie być naprawdę dobry.
• Chłopaki, mam wątpliwości. Mówisz, że djb2 jest zły, ale wyniki testu zaakceptowanej odpowiedzi pokazują, że jest dobra.
• Możesz przynajmniej użyć rozsądnej liczby pierwszej, która powoduje mniej kolizji zamiast 33. stackoverflow.com/a/2816747/21499

CityHash od 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, oraz kod jest dostępny tutaj .

CityHash jest napisany w C ++. Istnieje również zwykły port C .

Informacje o obsłudze 32-bitowej:

Wszystkie funkcje CityHash są dostosowane do procesorów 64-bitowych. To powiedziawszy, będą działać (z wyjątkiem nowych, które używają SSE4.2) w kodzie 32-bitowym. Jednak nie będą one zbyt szybkie. Możesz użyć Szeptu lub czegoś innego w kodzie 32-bitowym.

Komentarze

• Czy CityHash jest wymawiane podobnie do ” City Sushi? ”
• Masz spójrz na SipHash, ma on zastąpić MurmurHash / CityHash / etc.: 131002.net/siphash
• Zobacz także FarmHash, następca CitHash. code.google.com/p/farmhash
• xxHash twierdzi, że jest 5x szybszy niż CityHash.
• plain C port link jest uszkodzony.

Wykreśliłem krótkie porównanie różnych algorytmów haszowania podczas haszowania plików.

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

• Linear Scale
• Skala logarytmiczna

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 instrukcją SSE 4.2s CRC, której mój procesor nie ma. SpookyHash był w moim przypadku zawsze trochę przed CityHash.
• MD5 wydaje się być dobrym kompromisem przy korzystaniu z kryptograficznych funkcji skrótu, chociaż SHA256 może być bezpieczniejszy dla luki kolizyjne MD5 i SHA1.
• Złożoność wszystkich algorytmów jest liniowa – co nie jest zaskakujące, ponieważ działają blokowo. (Chciałem sprawdzić, czy metoda czytania robi różnicę, więc możesz po prostu porównać najbardziej prawe wartości).
• SHA256 był wolniejszy niż SHA512.
• Nie badałem losowości funkcje skrótu. Ale tutaj to dobre porównanie funkcji skrótu, których brakuje w odpowiedzi Iana Boyda . To wskazuje, że CityHash ma pewne problemy w przypadkach narożnych.

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

• https://github.com/sahib/rmlint/tree/gh-pages/plots (przepraszam za brzydki kod)

Komentarze

• Liniowy wykres skali odcina etykietę osi y, która mówi, jaką wielkość wykreśla. Wydaje mi się, że prawdopodobnie byłby to ” czas w sekundach „, taki sam jak skala logarytmiczna. Warto go ' naprawić.

Wiem, że istnieją rzeczy takie jak SHA-256 i tym podobne, ale te algorytmy są zaprojektowane być bezpiecznym , co zwykle oznacza, że działają wolniej niż algorytmy mniej unikatowe .

Założenie, że kryptograficzne funkcje skrótu są bardziej unikalne, jest błędne i faktycznie można wykazać, że w praktyce często jest odwrotne. Prawdę mówiąc:

1. Kryptograficzne funkcje skrótu idealnie powinny być nieodróżnialne od losowych ;
2. Jednak w przypadku niekryptograficznych funkcji skrótu pożądane jest, aby współdziałały korzystnie z prawdopodobnymi danymi wejściowymi .

Co oznacza, że niekryptograficzna funkcja skrótu może mieć mniej kolizji niż kryptograficzny dla „dobrego” zbioru danych – zbiorów danych, dla których został zaprojektowany.

Możemy to faktycznie zademonstrować za pomocą danych w odpowiedzi Iana Boyda i odrobinę matematyki: Problem z urodzinami . Wzór na oczekiwaną liczbę zderzających się par, jeśli wybierzesz losowo n liczby całkowite ze zbioru [1, d] (zaczerpnięte z Wikipedii):

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

Podłączanie n = 216,553 i d = 2 ^ 32 otrzymujemy około 5.5 oczekiwanych kolizji . Testy Iana pokazują głównie wyniki w tej okolicy, ale z jednym dramatycznym wyjątkiem: większość funkcji otrzymała zero kolizji w kolejne testy liczbowe. Prawdopodobieństwo losowego wybrania 216 553 32-bitowych liczb i uzyskania zera kolizji wynosi około 0,43%. A to tylko dla jednej funkcji – tutaj mamy pięć różnych rodzin funkcji skrótu z zerem Kolizje!

Widzimy więc, że skróty, które testował Ian, oddziałują korzystnie z zestawem danych kolejnych liczb – tj. „ponownie rozpraszają minimalnie różne dane wejściowe szersze niż idealna kryptograficzna funkcja skrótu. (Uwaga dodatkowa: oznacza to, że graficzna ocena Iana, że FNV-1a i MurmurHash2 „wyglądają dla niego losowo” w zbiorze danych liczbowych, może zostać obalona na podstawie jego własnych danych. Zero kolizji na zestawie danych o tym rozmiarze, dla obie funkcje skrótu są uderzająco nielosowe!)

Nie jest to zaskakujące, ponieważ jest to pożądane zachowanie w wielu zastosowaniach funkcji skrótu.Na przykład klucze tablicy skrótów są często bardzo podobne; Odpowiedź Iana wspomina o problemie MSN, który kiedyś miał z tabelami mieszania kodu pocztowego . Jest to zastosowanie, w którym unikanie kolizji dla prawdopodobnych danych wejściowych wygrywa z zachowaniem podobnym do przypadkowego.

Kolejnym pouczającym porównaniem jest kontrast w celach projektowych między CRC a kryptograficznymi funkcjami mieszającymi:

• CRC jest tak zaprojektowany, aby wychwytywał błędy wynikające z zakłóceń w kanałach komunikacyjnych , które mogą być niewielka liczba przerzutów bitów;
• Hasze kryptograficzne są przeznaczone do wychwytywania modyfikacji dokonanych przez złośliwych atakujących , którym przydzielono ograniczone zasoby obliczeniowe, ale arbitralnie dużo sprytu.

Tak więc w przypadku CRC ponownie dobrze jest mieć mniej kolizji niż przypadkowo w minimalnie różnych wejściach. W przypadku haszów kryptograficznych nie ma mowy!

Algorytmy SHA (w tym SHA-256) to zaprojektowane jako szybkie .

W rzeczywistości ich szybkość może czasami stanowić problem. W szczególności powszechną techniką przechowywania tokena wyprowadzonego z hasła jest uruchomienie standardowego szybkiego algorytmu mieszającego 10000 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 

Wyjście:

Rehearsal ------------------------------------ 1.480000 0.000000 1.480000 ( 1.391229) --------------------------- total: 1.480000sec user system total real 1.400000 0.000000 1.400000 ( 1.382016) 

Komentarze

• To ' jest stosunkowo szybkie, jasne, jak na kryptograficzny algorytm haszujący . Ale OP chce tylko przechowywać wartości w tablicy haszującej, a ja nie ' nie sądzę, aby kryptograficzna funkcja skrótu była do tego odpowiednia.
• Pytanie, które się pojawiło (stycznie, teraz się pojawia) temat kryptograficznych funkcji skrótu. Właśnie na to ' odpowiadam.
• Tylko po to, by zniechęcić ludzi do pomysłu ” , powszechną techniką przechowywania tokena uzyskanego z hasła jest uruchomienie standardowego szybkiego algorytmu wyznaczania wartości skrótu 10 000 razy ” – choć często jest to ' jest po prostu głupi. Istnieją algorytmy zaprojektowane dla takich scenariuszy, np. bcrypt. Używaj odpowiednich narzędzi.
• Hasze kryptograficzne są projektowane z myślą o dużej przepustowości, ale to często oznacza, że mają wysoką konfigurację, porzucenie, .rodata i / lub koszty stanu .Kiedy potrzebujesz algorytmu do tablicy haszującej, zwykle masz bardzo krótkie klucze i dużo ich, ale nie potrzebujesz dodatkowych gwarancji kryptograficznych. Sam używam zmodyfikowanego Jenkinsa pojedynczo.
• @ChrisMorgan: zamiast używać kryptograficznie bezpiecznego skrótu, HashTable DoS można rozwiązać znacznie wydajniej za pomocą randomizacji skrótu, dzięki czemu każdy przebieg programy lub nawet na każdej tablicy hashy, więc dane nie ' nie są grupowane w tym samym zasobniku za każdym razem.

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

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

• Bezpieczny. SipHash to silna funkcja PRF (funkcja pseudolosowa). Oznacza to, że jest nie do odróżnienia od funkcji losowej (chyba że znasz 128-bitowy tajny klucz). Dlatego:

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

  • Odporność na ataki typu „odmowa usługi” oparte na hashach.

  • Możesz użyć SipHash (zwłaszcza wersji z 128-bitowym wyjściem) jako MAC (Kod uwierzytelniania wiadomości). Jeśli otrzymasz wiadomość i tag SipHash, a tag jest taki sam, jak w przypadku uruchomienia SipHash z Twoim tajnym kluczem, to wiesz, że ktokolwiek utworzył hash, był również w posiadaniu twojego tajnego klucza i że ani wiadomość, ani hash zostały zmienione od tego czasu.

Komentarze

• Isn ' t SipHash przesadza, chyba że potrzebujesz ochrony? Wymaga 128-bitowego klucza, który jest tylko gloryfikowanym ziarnem mieszania. Nie wspominając o tym, że MurmurHash3 ma 128-bitowe wyjście, a SipHash ma tylko 64-bitowe wyjście. Oczywiście większe podsumowanie ma mniejszą szansę na kolizję.
• @bryc Różnica polega na tym, że SipHash będzie nadal zachowywał się dobrze, nawet w przypadku złośliwych danych wejściowych. Tablica mieszająca 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óry jest bardzo wrażliwy na szczegóły funkcji skrótu.
• Siphash (i powiązane nowsze prng style) to mój domyślny wybór ze względu na bezpieczeństwo. Jeśli chodzi o wydajność, xxhash jest trudny do pokonania. W Internecie jest mnóstwo złych porad, nawet podczas tutejszych dyskusji. Dobra wydajność przy wejściach losowych lub półlosowych jest bez znaczenia. Jaka jest najgorsza wydajność w przypadku rzeczywistych danych wejściowych? Jaki jest skutek złośliwych danych wejściowych? Twoja tablica skrótów ostatecznie stanie się wektorem ataku.

To zależy od haszowanych danych. Niektóre funkcje haszowania działają lepiej w przypadku określonych danych, takich jak tekst. Niektóre algorytmy haszujące zostały specjalnie zaprojektowane tak, aby były dobre dla określonych danych.

Paul Hsieh stworzył kiedyś szybkie haszowanie . Wymienia kod źródłowy i wyjaśnienia. Ale został już pobity. 🙂

Java używa tego prostego mnożenia -and-add algorytm:

Kod skrótu dla obiektu String jest obliczany jako

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

przy użyciu arytmetyki int, gdzie s[i] to i ​ -ty znak ciągu, n to długość ciągu, a ^ oznacza potęgowanie. (Wartość skrótu pustego ciągu wynosi zero.)

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

Komentarze

• Nie ' nie użyłbym dokładnie tego samego użyty tutaj, ponieważ ' jest nadal stosunkowo łatwy do spowodowania kolizji. To ' s zdecydowanie nie jest straszne, ale są tam znacznie lepsze. A jeśli ' nie ma żadnego istotnego powodu, aby być zgodnym z Javą, nie należy wybrać.
• Jeśli nadal wybierzesz tę Z jakiegoś powodu możesz przynajmniej użyć lepszej liczby pierwszej, takiej jak 92821, jako mnożnika. To znacznie zmniejsza liczbę kolizji. stackoverflow.com/a/2816747/21499
• Równie dobrze możesz zamiast tego użyć FNV1a. ' jest również prostym hashem opartym na mnożeniu, ale używa większego mnożnika, który lepiej rozprasza hash.
• Nie ' nie chcę robić s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Unikaj operatora potęgi (^) i zrób to w ten sposób: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Tak, w kodzie jest to (i powinno być) zrobione iteracyjnie, po prostu łatwiej było to zrozumieć w zamkniętej formule.

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

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

Oto przykład implementacji wersji 32-bitowej w języku 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; } 

Komentarze

• Wariant FNV-1a jest nieco lepszy z przypadkowością. Zmień kolejność * i ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619