Jeg testet noen forskjellige algoritmer, og målte hastighet og antall kollisjoner .

Jeg brukte tre forskjellige nøkkelsett:

• En liste med 216 553 engelske ord ^{🕗  arkiv} (med små bokstaver)
• Tallene "1" til "216553" (tenk postnummer, og hvordan en dårlig hash tok ned msn.com ^{🕗  arkiv} )
• 216,553 » tilfeldig «(dvs. type 4 uuid ) GUIDer

For hvert korpus, antall kollisjoner og gjennomsnittlig tid brukt hashing ble spilt inn.

Jeg testet:

• DJB2
• DJB2a (variant som bruker xor i stedet for +)
• FNV-1 (32-bit)
• FNV-1a (32-bit)
• SDBM
• CRC32
• Murmur2 (32-bit)
• SuperFastHash

Resultater

Hvert resultat inneholder gjennomsnittlig hashtid og antall kollisjoner

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 

Merknader :

• LoseLose-algoritmen (der hash = hash + tegn) er virkelig forferdelig . Alt kolliderer i de samme 1 375 bøttene
• SuperFastHash er rask, med ting som ser ganske spredt ut; av min godhet antall kollisjonene. Jeg håper fyren som porterte det, fikk noe galt. Det er ganske ille
• CRC32 er ganske bra . Tregere og en oppslagstabell på 1k

Skjer kollisjoner egentlig?

Ja. Jeg begynte å skrive testprogrammet mitt for å se om hasjkollisjoner faktisk skjer – og ikke bare er en teoretisk konstruksjon.De skjer faktisk:

FNV-1 kollisjoner

• creamwove kolliderer med quists

FNV -1a kollisjoner

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

Murmur2-kollisjoner

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

DJB2-kollisjoner

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

DJB2a kollisjoner

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

CRC32-kollisjoner

• codding kolliderer med gnu
• exhibiters kolliderer med schlager

SuperFastHash-kollisjoner

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

Randomnessification

Det andre subjektive målet er hvor tilfeldig fordelt hasjene er. Kartlegging av de resulterende HashTables viser hvor jevnt dataene distribueres. Alle hashfunksjonene viser god fordeling når du kartlegger tabellen lineært:

Eller som en Hilbert Map ( XKCD er alltid relevant ):

Bortsett fra når hashing nummerstrenger ("1", "2", …, "216553") (for eksempel postnummer ), der mønstre begynner å dukke opp i de fleste hashingalgoritmene:

SDBM :

DJB2a :

FNV-1 :

Alle unntatt

Hvis du ønsker å lage et hash-kart fra en uforanderlig ordbok, vil du kanskje vurdere perfekt hashing https://en.wikipedia.org/wiki/Perfect_hash_function – under konstruksjonen av hash-funksjonen og hash-tabellen kan du garantere, for et gitt datasett, at det ikke blir noen kollisjoner.

Kommentarer

• Her ‘ er mer om (minimal) Perfect Hashing burtleburtle.net/bob/hash/perfect.html inkludert ytelsesdata, selv om det ikke ‘ ikke bruker den nyeste prosessoren osv.
• Det ‘ er ganske åpenbart, men det er verdt å påpeke at for å garantere ingen kollisjoner, må tastene ha samme størrelse som verdiene, med mindre ere er begrensninger for verdiene algoritmen kan kapitalisere på.
• @ devios1 Ditt utsagn er meningsløst. For det første er verdiene i en hash-tabell, perfekte eller ikke, uavhengige av tastene. For det andre er en perfekt hash-tabell bare et lineært verdigrunnlag, indeksert av resultatet av funksjonen som er laget slik at alle indeksene er unike.
• @MarcusJ Perfect hashing brukes vanligvis med mindre enn 100 nøkler, men ta en titt på cmph.sourceforge.net … fremdeles langt utenfor rekkevidden.
• @DavidCary Ingenting på din side link støtter kravet ditt. Muligens har du forvekslet O (1) med » ingen kollisjoner «, men de er ikke ‘ div i det hele tatt det samme. Selvfølgelig garanterer perfekt hashing ingen kollisjoner, men det krever at alle nøklene er kjent på forhånd, og at det er relativt få av dem. (Men se lenken til cmph ovenfor.)

Her er en liste over hashfunksjoner, men kortversjonen er:

Hvis du bare vil ha en god hash-funksjon , og kan ikke vente, djb2 er en av de beste streng-hash-funksjonene jeg vet. Den har utmerket fordeling og hastighet på mange forskjellige sett med nøkler og tabellstørrelser

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 er faktisk nullfølsom, da de fleste slike enkle hashfunksjoner, slik at du enkelt kan bryte slike hashes.Den har dårlig skjevhet for mange kollisjoner og dårlig fordeling, den bryter på de fleste smashasher kvalitetstester: Se github.com/rurban/smhasher/blob/master/doc/bernstein Hans cdb-database bruker den, men jeg vil ikke ‘ ikke bruke den med offentlig tilgang.
• DJB er ganske ille fra et ytelses- og distribusjonssynspunkt. Jeg vil ikke ‘ ikke bruke den i dag.
• @ConradMeyer Jeg ‘ satset, DJB kan bli spurt opp av en faktor på tre akkurat som i dette spørsmålet mitt og da slo det sannsynligvis ‘ d mest brukbare algoritmer. Når det gjelder distribusjonen, er jeg enig. En hasj som produserer kollisjoner selv for to bokstavstrenger, kan ‘ ikke være veldig bra.
• Gutter, jeg er i tvil. Du sier at djb2 er dårlig, men testresultatene i det aksepterte svaret viser at det er bra.
• Du kan i det minste bruke en fornuftig prime som gir mindre kollisjoner i stedet for 33. stackoverflow.com/a/2816747/21499

CityHash av Google er algoritmen du leter etter. Det er ikke bra for kryptografi, men er bra for å generere unike hashes.

Les bloggen for mer informasjon og -koden er tilgjengelig her .

CityHash er skrevet i C ++. Det er også en vanlig C-port .

Omtrent 32-biters støtte:

Alle CityHash-funksjonene er innstilt for 64-biters prosessorer. Når det er sagt, vil de kjøre (bortsett fra de nye som bruker SSE4.2) i 32-biters kode. De vil ikke være veldig raske. Det kan være lurt å bruke Murmur eller noe annet i 32-biters kode.

Kommentarer

• Er CityHash uttalt lik » City Sushi? »
• Har du en se på SipHash også, det er ment å erstatte MurmurHash / CityHash / etc.: 131002.net/siphash
• Se også FarmHash, en etterfølger av CitHash. code.google.com/p/farmhash
• xxHash hevder å være fem ganger raskere enn CityHash.
• plain C port link er ødelagt

Jeg har tegnet en kort hastighetssammenligning av forskjellige hashingalgoritmer ved hashing av filer.

De enkelte plottene skiller seg bare litt ut i lesemetoden og kan ignoreres her, siden alle filene ble lagret i en tmpfs. Derfor var ikke referanseindeksen IO-bundet hvis du lurer på.

• Lineær skala
• Logaritmisk skala

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

Konklusjoner:

• Ikke-kryptografiske hashfunksjoner som Murmur3, Cityhash og Spooky er ganske tett sammen. Man bør merke seg at Cityhash kan være raskere på CPUer med SSE 4.2s CRC instruksjon, som min CPU ikke har. SpookyHash var i mitt tilfelle alltid en liten bit før CityHash.
• MD5 ser ut til å være en god kompromiss når du bruker kryptografiske hashfunksjoner, selv om SHA256 kan være sikrere for kollisjonssårbarheter av MD5 og SHA1.
• Kompleksiteten til alle algoritmer er lineær – noe som egentlig ikke er overraskende siden de fungerer blokkvis. (Jeg ønsket å se om lesemetoden gjør en forskjell, så du kan bare sammenligne verdiene til høyre).
• SHA256 var tregere enn SHA512.
• Jeg undersøkte ikke tilfeldigheten til hash-funksjonene. Men her er en god sammenligning av hashfunksjonene som mangler i Ian Boyds svar . Dette påpeker at CityHash har noen problemer i hjørnesaker.

Kilden som ble brukt til tomtene:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (beklager den stygge koden)

Kommentarer

• Grafen for lineær skala kutter av y-akse-etiketten som sier hvilken mengde den plotter. Jeg antar at det sannsynligvis ville være » tid i sekunder «, samme som den logaritmiske skalaen. Det er ‘ det er verdt å fikse.

Jeg vet at det er ting som SHA-256 og slikt, men disse algoritmene er designet å være sikker , noe som vanligvis betyr at de er langsommere enn algoritmer som er mindre unike .

Antagelsen om at kryptografiske hashfunksjoner er mer unike, er feil, og faktisk kan det vises at den ofte er baklengs i praksis. I sannhet:

1. Kryptografiske hashfunksjoner bør ideelt sett være som ikke kan skilles fra tilfeldig ;
2. Men med ikke-kryptografiske hashfunksjoner er det ønskelig for dem å samhandle gunstig med sannsynlige innganger .

Hvilket betyr at en ikke-kryptografisk hash-funksjon godt kan ha færre kollisjoner kryptografisk for «godt» datasett — datasett det ble designet for.

Vi kan faktisk demonstrere dette med dataene i Ian Boyds svar og litt matte: Bursdagsproblem . Formelen for forventet antall kolliderende par hvis du velger n heltall fra settet [1, d] er dette (hentet fra Wikipedia):

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

Koble til n = 216,553 og d = 2 ^ 32 får vi ca 5.5 forventede kollisjoner . Ians tester viser for det meste resultater rundt det nabolaget, men med ett dramatisk unntak: de fleste funksjonene fikk null kollisjoner i fortløpende talltester. Sannsynligheten for å velge 216 553 32-bits tall tilfeldig og få null kollisjoner er omtrent 0,43%. Og det er bare for en funksjon – her har vi fem forskjellige hashfunksjonsfamilier med null kollisjoner!

Så det vi ser her er at hasjene som Ian testet samhandler gunstig med det påfølgende talldatasettet – dvs. de spres minimalt forskjellige innganger bredere enn en ideell kryptografisk hash-funksjon ville gjort. (Sideanmerkning: dette betyr at Ians grafiske vurdering av at FNV-1a og MurmurHash2 «ser tilfeldig ut» for ham i tallene datasettet kan tilbakevises fra hans egne data. Null kollisjon på et datasett av den størrelsen, for begge hashfunksjonene, er slående ikke tilfeldig!)

Dette er ikke en overraskelse fordi dette er en ønskelig oppførsel for mange bruksområder for hashfunksjoner. For eksempel er hash-tabellnøkler ofte veldig like; Ians svar nevner et problem MSN en gang hadde med postnummer hash-tabeller . Dette er en bruk der kollisjons unngåelse på sannsynlige innganger vinner over tilfeldig oppførsel.

En annen lærerik sammenligning her er kontrasten i designmålene mellom CRC og kryptografiske hashfunksjoner:

• CRC er designet for å fange feil som skyldes støyende kommunikasjonskanaler , som sannsynligvis vil være et lite antall bitflips;
• Crypto-hashes er designet for å fange modifikasjoner gjort av ondsinnede angripere , som er tildelt begrensede beregningsressurser, men vilkårlig mye kløkt.

Så for CRC er det igjen bra å ha færre kollisjoner enn tilfeldig i minimalt forskjellige innganger. Med kryptohash er dette nei-nei!

SHA-algoritmene (inkludert SHA-256) er designet for å være rask .

Faktisk kan hastigheten deres være et problem noen ganger. Spesielt er en vanlig teknikk for lagring av et passordavledet token å kjøre en standard hurtig hash-algoritme 10 000 ganger (lagring av hasj av hasj av hash av hash av … passord).

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

Utgang:

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 ‘ er relativt raskt, sikkert, for en kryptografisk hashingalgoritme . Men OP vil bare lagre verdier i en hashtable, og jeg tror ikke ‘ at en kryptografisk hashfunksjon virkelig er passende for det.
• Spørsmålet som ble tatt opp (tangentielt ser det nå ut) emnet for de kryptografiske hashfunksjonene. At ‘ er den biten jeg svarer på.
• Bare for å sette folk utenfor ideen om » Spesielt , er en vanlig teknikk for lagring av et passordavledet token å kjøre en standard hurtig hash-algoritme 10 000 ganger » – mens det er vanlig, at ‘ er bare dumt. Det er algoritmer designet for disse scenariene, f.eks. bcrypt. Bruk de riktige verktøyene.
• Kryptografiske hashes er designet for å ha høy gjennomstrømning, men det betyr ofte at de har høye oppsett, nedrivning, .rodata og / eller statlige kostnader .Når du vil ha en algoritme for en hashtable, har du vanligvis veldig korte nøkler, og mange av dem, men trenger ikke tilleggsgarantiene til en kryptografisk har. Jeg bruker en finjustert Jenkins en om gangen selv.
• @ChrisMorgan: i stedet for å bruke en kryptografisk sikker hash, kan HashTable DoS løses mye mer effektivt ved hjelp av hash-randomisering, slik at hvert løp av programmene eller til og med på hver hashtable, så dataene ‘ blir ikke gruppert i samme bøtte hver gang.

Bruk SipHash . Den har mange ønskelige egenskaper:

• Rask. En optimalisert implementering tar omtrent 1 syklus per byte.

• Sikker. SipHash er en sterk PRF (pseudorandom-funksjon). Dette betyr at det ikke kan skilles fra en tilfeldig funksjon (med mindre du kjenner den 128-biters hemmelige nøkkelen). Derfor:

  • Ingen grunn til å bekymre deg for at hash-bordsondene dine blir lineære på grunn av kollisjoner. Med SipHash vet du at du vil oppnå gjennomsnittlig ytelse i gjennomsnitt, uavhengig av innganger.

  • Immunitet mot hash-basert nektelse av tjenesteangrep.

  • Du kan bruke SipHash (spesielt versjonen med 128-bits utdata) som MAC (Melding godkjenningskode). Hvis du mottar en melding og en SipHash-tag, og taggen er den samme som fra å kjøre SipHash med den hemmelige nøkkelen din, vet du at den som opprettet hash også var i besittelse av din hemmelige nøkkel, og at verken meldingen hash har blitt endret siden.

Kommentarer

• Er ikke ‘ t SipHash overkill med mindre du trenger sikkerhet? Krever en 128-bit nøkkel som bare er et glorifisert hashfrø. For ikke å nevne at MurmurHash3 har 128-biters utgang og SipHash bare har en 64-biters utgang. Åpenbart har den større fordøyelsen en lavere kollisjonssjanse.
• @bryc Forskjellen er at SipHash vil fortsette å være veloppdragen, selv på ondsinnede innspill. En hash-tabell basert på SipHash kan brukes til data fra potensielt fiendtlige kilder, og kan bruke en algoritme som lineær sondering som er veldig følsom for detaljene i hash-funksjonen.
• Siphash (og relatert nyere prng stilfunksjoner) er mitt standardvalg for sikkerhet. For ytelse er xxhash vanskelig å slå. Det er mange dårlige råd om internett, selv i diskusjonene her. God ytelse på tilfeldige eller semi-tilfeldige innganger er meningsløs. Hva er worst case-ytelsen, med innspill fra den virkelige verden? Hva er resultatet med ondsinnede innganger? Hashtabellen din vil til slutt bli en angrepsvektor.

Det avhenger av dataene du hasher. Noen hashing fungerer bedre med spesifikke data som tekst. Noen hashingalgoritmer var spesifikt designet for å være gode for spesifikke data.

Paul Hsieh laget en gang rask hash . Han lister opp kildekode og forklaringer. Men den var allerede slått. 🙂

Java bruker dette enkelt multiplisere -og-legg til algoritme:

Hash-koden for et strengobjekt beregnes som

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

ved hjelp av int-aritmetikk, der s[i] er i ​ -strengen, n er lengden på strengen, og ^ indikerer eksponentiering. (Hashverdien til den tomme strengen er null.)

Det er sannsynligvis mye bedre der ute, men dette er ganske utbredt og ser ut til å være bra kompromiss mellom hastighet og unikhet.

Kommentarer

• Jeg vil ikke ‘ ikke bruke nøyaktig det samme en brukt her, da det ‘ fortsatt er relativt lett å produsere kollisjoner med dette. Det ‘ er definitivt ikke forferdelig, men det er mye bedre der ute. Og hvis det ‘ ikke er noen vesentlig grunn til å være kompatibel med Java, bør det ikke velges.
• Hvis du fortsatt velger dette av hash av en eller annen grunn, kan du i det minste bruke en bedre prime som 92821 som en multiplikator. Det reduserer kollisjoner mye. stackoverflow.com/a/2816747/21499
• Du kan like gjerne bruke FNV1a i stedet. Den ‘ er også en enkel multiplikasjonsbasert hash, men bruker en større multiplikator, som sprer hashen bedre.
• Du trenger ikke ‘ t vil gjøre s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Unngå kraftoperatøren (^) og gjør det på denne måten: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Ja, i koden er det (og bør gjøres) iterativt, det var bare lettere å forstå i en lukket formel.

Først og fremst, hvorfor trenger du å implementere din egen hashing? For de fleste oppgaver bør du få gode resultater med datastrukturer fra et standardbibliotek, forutsatt at det er en implementering tilgjengelig (med mindre du bare gjør dette for din egen utdannelse).

Så langt som faktiske hashingalgoritmer går, er min personlige favoritt FNV. 1

Her er et eksempel på implementering av 32-biters versjonen 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 er litt bedre med tilfeldighet. Bytt rekkefølgen på * og ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619