Jag testade några olika algoritmer, mätte hastighet och antal kollisioner .

Jag använde tre olika nyckeluppsättningar:

• En lista med 216 553 engelska ord ^{🕗  arkiv} (i gemener)
• Siffrorna "1" till "216553" (tänk postnummer och hur en dålig hash tog ner msn.com ^{🕗  arkiv} )
• 216,553 ” slumpmässiga ”(dvs typ 4 uuid ) GUIDs

För varje corpus, antalet kollisioner och den genomsnittliga tiden som hashing spelades in.

Jag testade:

• DJB2
• DJB2a (variant med xor snarare än +)
• FNV-1 (32-bit)
• FNV-1a (32-bitars)
• SDBM
• CRC32
• Murmur2 (32-bitars)
• SuperFastHash

Resultat

Varje resultat innehåller den genomsnittliga hashtiden och antalet kollisioner

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 

Anteckningar :

• LoseLose-algoritmen (där hash = hash + tecken) är verkligen hemskt . Allt kolliderar i samma 1 375 hinkar
• SuperFastHash är snabbt, med saker som ser ganska utspridda ut; av min godhet antal kollisioner. Jag hoppas killen som portade det fick något fel. Det är ganska dåligt
• CRC32 är ganska bra . Långsammare och en 1k-uppslagstabell

Händer kollisioner faktiskt?

Ja. Jag började skriva mitt testprogram för att se om hashkollisioner faktiskt inträffar – och inte bara är en teoretisk konstruktion.De händer verkligen:

FNV-1-kollisioner

• creamwove kolliderar med quists

FNV -1a kollisioner

• costarring kolliderar med liquid
• declinate kolliderar med macallums
• altarage kolliderar med zinke
• altarages kolliderar med zinkes

Murmur2-kollisioner

• cataract kolliderar med periti
• roquette kolliderar med skivie
• shawl kolliderar med stormbound
• dowlases kolliderar med tramontane
• cricketings kolliderar med twanger
• longans kolliderar med whigs

DJB2-kollisioner

• hetairas kolliderar med mentioner
• heliotropes kolliderar med neurospora
• depravement kolliderar med serafins
• stylist kolliderar med subgenera
• joyful kolliderar med synaphea
• redescribed kolliderar med urites
• dram kolliderar med vivency

DJB2a-kollisioner

• haggadot kolliderar med loathsomenesses
• adorablenesses kolliderar med rentability
• playwright kolliderar med snush
• playwrighting kolliderar med snushing
• treponematoses kolliderar med waterbeds

CRC32-kollisioner

• codding kolliderar med gnu
• exhibiters kolliderar med schlager

SuperFastHash-kollisioner

• dahabiah kolliderar med drapability
• encharm kolliderar med enclave
• grahams kolliderar med gramary
• … klipp 79 kollisioner …
• night kolliderar med vigil
• kolliderar med vigils
• finks kolliderar med vinic

Slumpmässighet

Det andra subjektiva måttet är hur slumpmässigt fördelade hasharna är. Kartläggning av de resulterande HashTables visar hur jämnt data distribueras. Alla hashfunktioner visar bra fördelning vid tabell linjär mappning:

Eller som Hilbert Map ( XKCD är alltid relevant ):

Förutom när hashing nummersträngar ("1", "2", …, "216553") (till exempel postnummer ), där mönster börjar att dyka upp i de flesta hashingalgoritmerna:

SDBM :

DJB2a :

FNV-1 :

Alla utom

Om du vill skapa en hash-karta från en oförändrad ordbok, kanske du vill överväga perfekt hashing https://en.wikipedia.org/wiki/Perfect_hash_function – under konstruktionen av hashfunktionen och hashtabellen kan du garantera, för en viss dataset, att det inte kommer att bli några kollisioner.

Kommentarer

• Här ’ är mer om (minimal) Perfect Hashing burtleburtle.net/bob/hash/perfect.html inklusive prestandadata, även om den inte ’ inte använder den senaste processorn etc.
• Det ’ är ganska uppenbart, men värt att påpeka att för att garantera inga kollisioner måste nycklarna ha samma storlek som värdena, såvida inte här är begränsningar för de värden som algoritmen kan dra nytta av.
• @ devios1 Ditt uttalande är meningslöst. För det första är värdena i en hashtabell, perfekta eller inte, oberoende av tangenterna. För det andra är en perfekt hash-tabell bara en linjär uppsättning värden, indexerade av resultatet av funktionen som har skapats så att alla index är unika.
• @MarcusJ Perfect hashing används vanligtvis med mindre än 100 nycklar, men ta en titt på cmph.sourceforge.net … fortfarande långt borta från ditt intervall.
• @DavidCary Inget till ditt länk stöder ditt anspråk. Möjligen har du förväxlat O (1) med ” inga kollisioner ”, men de är inte ’ t alls samma sak. Naturligtvis garanterar perfekt hashing inga kollisioner, men det kräver att alla nycklar är kända i förväg och att det är relativt få av dem. (Men se länken till cmph ovan.)

Här är en lista med hashfunktioner, men den korta versionen är:

Om du bara vill ha en bra hashfunktion , och kan inte vänta, djb2 är en av de bästa stränghashfunktionerna jag känner till. Den har utmärkt fördelning och hastighet på många olika uppsättningar nycklar och tabellstorlekar

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

Kommentarer

• Djb2 är faktiskt nollkänslig, eftersom de flesta sådana enkla hashfunktioner, så att du enkelt kan bryta sådana hashes.Den har en dålig förspänning för många kollisioner och en dålig fördelning, den bryter vid de flesta smashasher kvalitetstester: Se github.com/rurban/smhasher/blob/master/doc/bernstein Hans cdb-databas använder den, men jag skulle inte ’ inte använda den med allmän tillgång.
• DJB är ganska dålig ur en prestations- och distributionssynpunkt. Jag skulle inte ’ inte använda den idag.
• @ConradMeyer Jag ’ satsade, DJB kan snabbas upp av en faktor på tre precis som i den här frågan min och då slog den ’ förmodligen de mest användbara algoritmerna. När det gäller distributionen håller jag med. En hash som producerar kollisioner även för två bokstavssträngar kan ’ inte vara riktigt bra.
• Killar, jag tvivlar. Du säger att djb2 är dåligt, men testresultaten för det accepterade svaret visar att det är bra.
• Du kan åtminstone använda en förnuftig prime som ger mindre kollisioner istället för 33. stackoverflow.com/a/2816747/21499

CityHash av Google är den algoritm du letar efter. Det är inte bra för kryptografi men är bra för att skapa unika hash.

Läs bloggen för mer information och -kod finns här .

CityHash är skrivet i C ++. Det finns också en vanlig C-port .

Om 32-bitars stöd:

Alla CityHash-funktioner är inställda för 64-bitars processorer. Med det sagt kommer de att köras (förutom de nya som använder SSE4.2) i 32-bitars kod. De kommer dock inte att vara mycket snabba. Du kanske vill använda Murmur eller något annat i 32-bitars kod.

Kommentarer

• Är CityHash uttalat liknar ” City Sushi? ”
• Har du en titta på SipHash också, det är tänkt att ersätta MurmurHash / CityHash / etc.: 131002.net/siphash
• Se även FarmHash, en efterträdare till CitHash. code.google.com/p/farmhash
• xxHash påstår sig vara fem gånger snabbare än CityHash.
• plain C port länken är trasig

Jag har ritat en kort hastighetsjämförelse av olika hashingalgoritmer vid hashing-filer.

De enskilda ritningarna skiljer sig bara något i läsmetoden och kan ignoreras här, eftersom alla filer lagrades i en tmpfs. Därför var inte riktmärket IO-bundet om du undrar.

• Linjär skala
• Logaritmisk skala

Algoritmer inkluderar: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Slutsatser:

• Icke-kryptografiska hashfunktioner som Murmur3, Cityhash och Spooky är ganska nära varandra. Man bör notera att Cityhash kan vara snabbare på processorer med SSE 4.2s CRC instruktioner, som min CPU inte har. SpookyHash var i mitt fall alltid lite innan CityHash.
• MD5 verkar vara en bra avvägning när man använder kryptografiska hashfunktioner, även om SHA256 kan vara säkrare för kollisionssårbarheter för MD5 och SHA1.
• Komplexiteten hos alla algoritmer är linjär – vilket verkligen inte är förvånande eftersom de fungerar blockvis. (Jag ville se om läsningsmetoden gör skillnad så att du bara kan jämföra värdena längst till höger.
• SHA256 var långsammare än SHA512.
• Jag undersökte inte slumpmässigheten hos hashfunktionerna. Men här är en bra jämförelse av hashfunktionerna som saknas i Ian Boyds svar . Detta påpekar att CityHash har vissa problem i hörnfall.

Källan som används för tomterna:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (ledsen för den fula koden)

Kommentarer

• Diagrammet för linjär skala skär av y-axelns etikett som säger vilken mängd den plottar. Jag antar att det antagligen skulle vara ” tid i sekunder ”, samma som den logaritmiska skalan. Det ’ är värt att fixa.

Jag vet att det finns saker som SHA-256 och sådant, men dessa algoritmer är designade att vara säker , vilket vanligtvis betyder att de är långsammare än algoritmer som är mindre unika .

Antagandet att kryptografiska hashfunktioner är mer unika är fel och det kan faktiskt visas att det ofta är bakåt i praktiken. I sanning:

1. Kryptografiska hashfunktioner bör helst vara som inte kan skiljas från slumpmässigt ;
2. Men med icke-kryptografiska hashfunktioner är det önskvärt för dem att interagerar positivt med troliga ingångar .

Vilket innebär att en icke-kryptografisk hashfunktion mycket väl kan ha färre kollisioner än en kryptografisk för ”bra” datamängd – datamängder som den var designad för.

Vi kan faktiskt visa detta med data i Ian Boyds svar och lite matematik: Födelsedagsproblem . Formeln för det förväntade antalet kolliderande par om du väljer n heltal slumpmässigt från uppsättningen [1, d] är detta (hämtad från Wikipedia):

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

Anslutning n = 216,553 och d = 2 ^ 32 får vi ungefär 5.5 förväntade kollisioner . Ians tester visar mestadels resultat runt området, men med ett dramatiskt undantag: de flesta funktionerna fick nollkollisioner i på varandra följande siffror. Sannolikheten för att välja 216 553 32-bitars nummer slumpmässigt och få nollkollisioner är cirka 0,43%. Och det är bara för en funktion – här har vi fem olika hashfunktionsfamiljer med noll kollisioner!

Så vad vi ser här är att hasharna som Ian testade samverkar gynnsamt med den efterföljande siffrorna – dvs. de sprider sig minimalt olika ingångar bredare än en perfekt kryptografisk hash-funktion skulle göra. (Sidanot: detta betyder att Ians grafiska bedömning att FNV-1a och MurmurHash2 ”ser slumpmässigt ut” för honom i siffrorna datamängden kan motbevisas från hans egna data. Nollkollisioner på en datamängd av den storleken, för båda hashfunktionerna är slående otrolig!)

Detta är inte en överraskning eftersom detta är ett önskvärt beteende för många användningar av hashfunktioner. Ians svar nämner ett problem som MSN en gång hade med postnummer hashtabeller . Detta är en användning där kollisionsundvikande på troligt ingångar vinner över slumpmässigt liknande beteende.

En annan lärorik jämförelse här är kontrasten i designmålen mellan CRC och kryptografiska hashfunktioner:

• CRC är utformad för att fånga fel som orsakas av bullriga kommunikationskanaler , som sannolikt kommer att vara ett litet antal bitflipar;
• Crypto-hash är utformade för att fånga modifieringar gjorda av skadliga angripare , som tilldelas begränsade beräkningsresurser men godtyckligt mycket skicklighet.

Så för CRC är det återigen bra att ha färre kollisioner än slumpmässigt i minimalt olika ingångar. Med kryptohash är detta nej-nej!

SHA-algoritmerna (inklusive SHA-256) är designad att vara snabb .

Faktum är att deras hastighet ibland kan vara ett problem. I synnerhet är en vanlig teknik för lagring av ett lösenord härledd token att köra en standard snabb hash-algoritm 10 000 gånger (lagra hash för hash för hash för hash av … lösenord).

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

Output:

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

Kommentarer

• Det ’ är relativt snabbt, säkert, för en kryptografisk hashingalgoritm . Men OP vill bara lagra värden i en hashtable, och jag tycker inte ’ att en kryptografisk hashfunktion verkligen är lämplig för det.
• Frågan som tas upp (tangentiellt verkar det nu) ämnet för de kryptografiska hashfunktionerna. Det är ’ som jag svarar på.
• Bara för att avskräcka människor från idén om ” Speciellt , en vanlig teknik för att lagra ett lösenord härledd token är att köra en standard snabb hash-algoritm 10 000 gånger ” – medan det är vanligt att ’ är helt enkelt dumt. Det finns algoritmer som är utformade för dessa scenarier, t.ex. bcrypt. Använd rätt verktyg.
• Kryptografiska haschar är utformade för att ha hög genomströmning, men det betyder ofta att de har höga inställningar, nedbrytning, .rodata och / eller statskostnader .När du vill ha en algoritm för en hashtable har du vanligtvis mycket korta nycklar och många av dem, men behöver inte de ytterligare garantierna för en kryptografisk har. Jag använder en justerad Jenkins en i taget själv.
• @ChrisMorgan: snarare än att använda en kryptografiskt säker hash kan HashTable DoS lösas mycket mer effektivt med hash-randomisering, så att varje körning av programmen eller till och med på varje hashtable, så data delas inte ’ i samma hink varje gång.

Använd SipHash . Den har många önskvärda egenskaper:

• Snabbt. En optimerad implementering tar cirka en cykel per byte.

• Säker. SipHash är en stark PRF (pseudorandom-funktion). Det betyder att det inte går att skilja från en slumpmässig funktion (såvida du inte känner till den 128-bitars hemliga nyckeln). Därav:

  • Du behöver inte oroa dig för att dina hashtabellprober blir linjära på grund av kollisioner. Med SipHash vet du att du får genomsnittliga fall i genomsnitt, oavsett ingångar.

  • Immunitet mot hash-baserad denial of service-attacker.

  • Du kan använda SipHash (särskilt versionen med en 128-bitars utgång) som MAC (Meddelandeautentiseringskod). Om du får ett meddelande och en SipHash-tagg, och taggen är densamma som den från att köra SipHash med din hemliga nyckel, vet du att den som skapade hash också hade din hemliga nyckel och att varken meddelandet eller hash har ändrats sedan.

Kommentarer

• Är inte ’ t SipHash överkill om du inte behöver säkerhet? Kräver en 128-bitars nyckel som bara är en förhärligad hashfrö. För att inte tala om MurmurHash3 har 128-bitars utdata och SipHash har bara en 64-bitars utgång. Uppenbarligen har den större smälten en lägre kollisionschans.
• @bryc Skillnaden är att SipHash kommer att fortsätta att vara välskött, även på skadlig inmatning. En hash-tabell baserad på SipHash kan användas för data från potentiellt fientliga källor och kan använda en algoritm som linjär sondering som är mycket känslig för detaljerna i hashfunktionen.
• Siphash (och relaterad nyare prng stilfunktioner) är mitt standardval för säkerhet. För prestanda är xxhash svår att slå. Det finns massor av dåliga råd om internet, även i diskussionerna här. Bra prestanda på slumpmässiga eller semi-slumpmässiga ingångar är meningslöst. Vad är det värsta fallet med ingångar från verkliga världen? Vad är resultatet med skadliga ingångar? Din hashtabell blir så småningom en attackvektor.

Det beror på vilken data du hasar. Vissa hashing fungerar bättre med specifika data som text. Vissa hashingalgoritmer var specifikt utformade för att vara bra för specifika data.

Paul Hsieh gjorde en gång snabb hash . Han listar källkod och förklaringar. Men det var redan misshandlat. 🙂

Java använder detta enkla multiplicera -och lägg till algoritm:

Hashkoden för ett strängobjekt beräknas som

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

med int-aritmetik, där s[i] är strängens i ​ -tecken, n är strängens längd och ^ indikerar exponentiering. (Hash-värdet för den tomma strängen är noll.)

Det finns nog mycket bättre där ute men det är ganska utbrett och verkar vara bra kompromiss mellan hastighet och unikhet.

Kommentarer

• Jag skulle ’ inte använda exakt samma en som används här, eftersom det ’ fortfarande är relativt lätt att producera kollisioner med detta. Det ’ s definitivt inte hemskt, men det finns mycket bättre där ute. Och om det inte finns ’ någon anledning att vara kompatibel med Java ska det inte väljas.
• Om du ändå väljer det här sätt att haska av någon anledning kan du åtminstone använda en bättre prime som 92821 som en multiplikator. Det minskar kollisionerna mycket. stackoverflow.com/a/2816747/21499
• Du kan lika gärna använda FNV1a istället. Det ’ är också en enkel multiplikationsbaserad hash, men använder en större multiplikator som sprider hash bättre.
• Du don ’ vill inte göra s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Undvik eloperatören (^) och gör det så här: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Ja, i koden är det (och bör göras) iterat, det var bara lättare att förstå i en sluten formel.

Först och främst, varför behöver du implementera din egen hashing? För de flesta uppgifter bör du få bra resultat med datastrukturer från ett standardbibliotek, förutsatt att det finns en implementering tillgänglig (såvida du inte bara gör detta för din egen utbildning).

När det gäller faktiska hashingalgoritmer är min personliga favorit FNV. 1

Här är ett exempel på implementering av 32-bitarsversionen i 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; } 

Kommentarer

• FNV-1a-varianten är något bättre med slumpmässighet. Byt ordningen på * och ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619