Jeg testede nogle forskellige algoritmer med måling af hastighed og antal kollisioner .

Jeg brugte tre forskellige nøglesæt:

• En liste med 216.553 engelske ord ^{🕗  arkiv} (med små bogstaver)
• Tallene "1" til "216553" (tænk postnummer og hvordan en dårlig hash fjernede msn.com ^{🕗  arkiv} )
• 216.553 ” tilfældig “(dvs. type 4 uuid ) GUIDer

For hvert corpus er antallet af kollisioner og den gennemsnitlige tid brugt hashing blev optaget.

Jeg testede:

• DJB2
• DJB2a (variant ved hjælp af xor i stedet for +)
• FNV-1 (32-bit)
• FNV-1a (32-bit)
• SDBM
• CRC32
• Murmur2 (32-bit)
• SuperFastHash

Resultater

Hvert resultat indeholder den gennemsnitlige hashtid og antallet af 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 

Noter :

• LoseLose-algoritme (hvor hash = hash + tegn) er virkelig forfærdelig . Alt kolliderer i de samme 1.375 spande
• SuperFastHash er hurtig, med tingene ser ret spredte ud; af min godhed antallet kollisionerne. Jeg håber den fyr, der portede det, fik noget galt; det er ret dårligt
• CRC32 er ret godt . Langsommere og en opslagstabel på 1k

Er der faktisk kollisioner?

Ja. Jeg begyndte at skrive mit testprogram for at se, om hashkollisioner faktisk sker – og ikke kun er en teoretisk konstruktion.De sker faktisk:

FNV-1 kollisioner

• creamwove kolliderer med quists

FNV -1a kollisioner

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

Murmur2 kollisioner

• 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-kollisioner

• 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 kollisioner

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

CRC32-kollisioner

• codding kolliderer med gnu
• exhibiters kolliderer med schlager

SuperFastHash kollisioner

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

Randomnessification

Det andet subjektive mål er, hvor tilfældigt fordelte hasherne er. Kortlægning af de resulterende HashTables viser, hvor jævnt dataene fordeles. Alle hash-funktionerne viser god fordeling, når de kortlægger tabellen lineært:

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

Undtagen når hashing nummerstrenge ("1", "2", …, "216553") (f.eks. postnumre ), hvor mønstre begynder at dukke op i de fleste hashingalgoritmer:

SDBM :

DJB2a :

FNV-1 :

Alle undtagen

Hvis du ønsker at oprette et hash-kort fra en uændret ordbog, kan du overveje at foretage perfekt hashing https://en.wikipedia.org/wiki/Perfect_hash_function – under konstruktionen af hash-funktionen og hash-tabellen kan du garantere for et givet datasæt, at der ikke er nogen kollisioner.

Kommentarer

• Her ‘ er mere om (minimal) Perfect Hashing burtleburtle.net/bob/hash/perfect.html inklusive ydeevnedata, skønt den ikke ‘ ikke bruger den nyeste processor osv.
• Det ‘ er ret indlysende, men det er værd at påpege, at nøglerne for at garantere ingen kollisioner skal have samme størrelse som værdierne, medmindre der er begrænsninger for de værdier, som algoritmen kan udnytte.
• @ devios1 Din erklæring er meningsløs. For det første er værdierne i en hash-tabel, perfekte eller ej, uafhængige af nøglerne. For det andet er en perfekt hash-tabel bare en lineær række af værdier, indekseret af resultatet af en funktion, der er udformet, så alle indekserne er unikke.
• @MarcusJ Perfect hashing bruges normalt med mindre end 100 nøgler, men kig på cmph.sourceforge.net … stadig langt fra dit interval.
• @DavidCary Intet til din link understøtter dit krav. Muligvis har du forvekslet O (1) med ” ingen kollisioner “, men de er ikke ‘ t overhovedet den samme ting. Selvfølgelig garanterer perfekt hashing ingen kollisioner, men det kræver, at alle nøgler er kendt på forhånd, og at der er relativt få af dem. (Men se linket til cmph ovenfor.)

Her er en liste over hash-funktioner, men den korte version er:

Hvis du bare vil have en god hash-funktion , og kan ikke vente, djb2 er en af de bedste streng-hash-funktioner, jeg kender. Det har fremragende fordeling og hastighed på mange forskellige sæt nøgler og tabelstø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 nulfølsom, da de fleste sådanne enkle hashfunktioner, så du nemt kan bryde sådanne hashes.Det har en dårlig bias for mange kollisioner og en dårlig fordeling, det bryder på de fleste smhasher kvalitetstest: Se github.com/rurban/smhasher/blob/master/doc/bernstein Hans cdb-database bruger den, men jeg ville ikke ‘ ikke bruge den med offentlig adgang.
• DJB er ret dårlig set fra et præstations- og distributionssynspunkt. Jeg ville ikke ‘ ikke bruge det i dag.
• @ConradMeyer Jeg ‘ satsede, DJB kan øges med en faktor på tre ligesom i dette spørgsmål af mig , og så slog det ‘ sandsynligvis de mest anvendelige algoritmer. Med hensyn til distributionen er jeg enig. En hash, der producerer kollisioner, selv for to bogstavstrenge, kan ‘ ikke være rigtig god.
• Gutter, jeg er i tvivl. Du siger, at djb2 er dårligt, men testresultaterne af det accepterede svar viser, at det er godt.
• Du kan i det mindste bruge en fornuftig prime, der giver mindre kollisioner i stedet for 33. stackoverflow.com/a/2816747/21499

CityHash fra Google er den algoritme, du leder efter. Det er ikke godt for kryptografi, men det er godt til at generere unikke hashes.

Læs blog for at få flere oplysninger og -koden er tilgængelig her .

CityHash er skrevet i C ++. Der er også en almindelig C-port .

Omkring 32-bit support:

Alle CityHash-funktioner er indstillet til 64-bit processorer. Når det er sagt, vil de køre (bortset fra de nye, der bruger SSE4.2) i 32-bit kode. De vil dog ikke være meget hurtige. Det kan være en god idé at bruge Murmur eller noget andet i 32-bit kode.

Kommentarer

• Er CityHash udtalt svarende til ” City Sushi? ”
• Har en se også på SipHash, det er meningen at erstatte MurmurHash / CityHash / osv.: 131002.net/siphash
• Se også FarmHash, en efterfølger til CitHash. code.google.com/p/farmhash
• xxHash hævder at være 5 gange hurtigere end CityHash.
• plain C port link er brudt

Jeg har tegnet en kort hastighedssammenligning af forskellige hashingalgoritmer, når hashing filer.

De enkelte plotter adskiller sig kun lidt i læsemetoden og kan ignoreres her, da alle filer blev gemt i en tmpfs. Derfor var benchmarket ikke IO-bundet, hvis du undrer dig.

• Lineær skala
• Logaritmisk skala

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

Konklusioner:

• Ikke-kryptografiske hashfunktioner som Murmur3, Cityhash og Spooky er ret tæt på hinanden. Man skal bemærke, at Cityhash kan være hurtigere på CPUer med SSE 4.2s CRC instruktion, som min CPU ikke har. SpookyHash var i mit tilfælde altid en lille smule før CityHash.
• MD5 ser ud til at være en god kompromis, når man bruger kryptografiske hashfunktioner, selvom SHA256 kan være mere sikker på kollisionssårbarheder af MD5 og SHA1.
• Kompleksiteten af alle algoritmer er lineær – hvilket virkelig ikke er overraskende, da de fungerer blokvis. (Jeg ville se, om læsemetoden gør en forskel, så du bare kan sammenligne de længste værdier).
• SHA256 var langsommere end SHA512.
• Jeg undersøgte ikke tilfældigheden af hash-funktionerne. Men her er en god sammenligning af de hash-funktioner, der mangler i Ian Boyds svar . Dette påpeger, at CityHash har nogle problemer i hjørnesager.

Kilden, der er brugt til plottene:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (undskyld den grimme kode)

Kommentarer

• Grafen for lineær skala afskærer y-aksens etiket, der siger, hvilken mængde den planlægger. Jeg antager, at det sandsynligvis ville være ” tid i sekunder “, samme som den logaritmiske skala. Det er ‘ værd at rette.

Jeg ved, at der er ting som SHA-256 og sådan, men disse algoritmer er designet at være sikker , hvilket normalt betyder, at de er langsommere end algoritmer, der er mindre unikke .

Antagelsen om, at kryptografiske hashfunktioner er mere unikke, er forkert, og faktisk kan det vises, at den ofte er bagud i praksis. I sandhed:

1. Kryptografiske hashfunktioner skal ideelt set være der ikke kan skelnes fra tilfældig ;
2. Men med ikke-kryptografiske hashfunktioner er det ønskeligt, at de interagerer gunstigt med sandsynlige input .

Hvilket betyder, at en ikke-kryptografisk hash-funktion godt kan have færre kollisioner end en kryptografisk for “godt” datasæt – datasæt, som det var designet til.

Vi kan faktisk demonstrere dette med dataene i Ian Boyds svar og lidt matematik: Fødselsdagsproblem . Formlen for det forventede antal kolliderende par, hvis du vælger n tilfældige tal helt fra sættet [1, d] er dette (taget fra Wikipedia):

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

Tilslutning n = 216.553 og d = 2 ^ 32 får vi ca. 5.5 forventede kollisioner . Ians tests viser for det meste resultater omkring dette kvarter, men med en dramatisk undtagelse: de fleste af funktionerne fik nul kollisioner i fortløbende nummertest. Sandsynligheden for at vælge 216.553 32-bit numre tilfældigt og få nul kollisioner er omkring 0,43%. Og det er bare for en funktion – her har vi fem forskellige hashfunktionsfamilier med nul kollisioner!

Så hvad vi ser her er, at de hashes, som Ian testede, interagerer fordelagtigt med datasættet på hinanden følgende numre – dvs. de spredes minimalt forskellige input mere bredt end en ideel kryptografisk hash-funktion ville. (Sidebemærkning: dette betyder, at Ians grafiske vurdering af, at FNV-1a og MurmurHash2 “ser tilfældigt ud” for ham i tallene datasættet kan tilbagevises fra hans egne data. Nul kollisioner på et datasæt af den størrelse, for begge hash-funktioner, er slående ikke tilfældigt!)

Dette er ikke en overraskelse, fordi dette er en ønskelig opførsel for mange anvendelser af hash-funktioner. F.eks. er hash-tabel nøgler ofte meget ens; Ians svar nævner et problem, MSN engang havde med postnummer hash-tabeller . Dette er en anvendelse, hvor kollisionsundgåelse på sandsynlige input vinder tilfældig-lignende opførsel.

En anden instruktiv sammenligning her er kontrasten i designmålene mellem CRC og kryptografiske hashfunktioner:

• CRC er designet til at fange fejl som følge af støjende kommunikationskanaler , som sandsynligvis vil være et lille antal bitflip;
• Crypto-hashes er designet til at fange ændringer foretaget af ondsindede angribere , der er tildelt begrænsede beregningsressourcer, men vilkårligt meget kloge.

Så for CRC er det igen godt at have færre kollisioner end tilfældigt i minimalt forskellige input. Med krypto-hashes er dette et nej-nej!

SHA-algoritmerne (inklusive SHA-256) er designet til at være hurtig .

Faktisk kan deres hastighed nogle gange være et problem. Især er en almindelig teknik til lagring af et adgangskodeafledt token at køre en standard hurtig hash-algoritme 10.000 gange (lagring af hash af hash af hash af hash af … adgangskode).

#!/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 ‘ er relativt hurtigt, sikkert, for en kryptografisk hashingalgoritme . Men OP vil bare gemme værdier i en hashtable, og jeg tror ikke ‘ at en kryptografisk hash-funktion virkelig er passende til det.
• Spørgsmålet rejst (tangentielt ser det nu ud) emnet for de kryptografiske hash-funktioner. At ‘ er den bit, jeg reagerer på.
• Bare for at afskrække folk fra ideen om ” Især , en almindelig teknik til lagring af et adgangskodeafledt token er at køre en standard hurtig hash-algoritme 10.000 gange ” – mens det er almindeligt, at ‘ er bare dumt. Der er algoritmer designet til disse scenarier, f.eks. bcrypt. Brug de rigtige værktøjer.
• Kryptografiske hashes er designet til at have en høj kapacitet, men det betyder ofte, at de har høje opsætnings-, nedbrydnings-, .rodata og / eller statslige omkostninger .Når du vil have en algoritme til en hashtable, har du normalt meget korte nøgler og mange af dem, men har ikke brug for de ekstra garantier, som en kryptografisk har. Jeg bruger en tweaked Jenkins en ad gangen selv.
• @ChrisMorgan: I stedet for at bruge en kryptografisk sikker hash kan HashTable DoS løses meget mere effektivt ved hjælp af hash-randomisering, så hver kørsel af programmerne eller endda på hver hashtable, så dataene ‘ grupperes ikke i den samme spand hver gang.

Brug SipHash . Det har mange ønskelige egenskaber:

• Hurtigt. En optimeret implementering tager cirka 1 cyklus pr. byte.

• Sikker. SipHash er en stærk PRF (pseudorandom-funktion). Dette betyder, at den ikke kan skelnes fra en tilfældig funktion (medmindre du kender den 128-bit hemmelige nøgle). Derfor:

  • Ingen grund til at bekymre sig om, at dine hash-tabel-sonder bliver lineære på grund af kollisioner. Med SipHash ved du at du i gennemsnit får gennemsnitlig sagsydelse uanset input.

  • Immunitet mod hash-baseret denial of service-angreb.

  • Du kan bruge SipHash (især versionen med en 128-bit output) som en MAC (Beskedgodkendelseskode). Hvis du modtager en besked og et SipHash-tag, og tagget er det samme som at køre SipHash med din hemmelige nøgle, så ved du, at den, der oprettede hash, også var i besiddelse af din hemmelige nøgle, og at hverken meddelelsen eller hash er blevet ændret siden.

Kommentarer

• Isn ‘ t SipHash overkill, medmindre du har brug for sikkerhed? Kræver en 128-bit nøgle, som bare er et glorificeret hashfrø. For ikke at nævne MurmurHash3 har 128-bit output og SipHash har kun en 64-bit output. Det er klart, at den større fordøjelse har en mindre kollisionschance.
• @bryc Forskellen er, at SipHash fortsat vil være velopdragen, selv ved ondsindet input. En hash-tabel baseret på SipHash kan bruges til data fra potentielt fjendtlige kilder og kan bruge en algoritme såsom lineær sondering, der er meget følsom over for detaljerne i hash-funktionen.
• Siphash (og relateret nyere prng stilfunktioner) er mit standardvalg for sikkerhed. For ydeevne er xxhash svært at slå. Der er masser af dårlige hashing-råd på internettet, selv i diskussionerne her. God ydelse på tilfældige eller semi-tilfældige input er meningsløs. Hvad er den værst tænkelige ydeevne med input fra den virkelige verden? Hvad er resultatet med ondsindede input? Din hash-tabel bliver i sidste ende en angrepsvektor.

Det afhænger af de data, du hashing. Nogle hashing fungerer bedre med specifikke data som tekst. Nogle hashingalgoritmer var specifikt designet til at være gode til specifikke data.

Paul Hsieh lavede engang hurtig hash . Han lister kildekode og forklaringer. Men det var allerede slået. 🙂

Java bruger denne enkle gang -og-tilføj algoritme:

Hashkoden for et strengobjekt beregnes som

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

ved hjælp af int-aritmetik, hvor s[i] er i ​ -strengen, n er længden af strengen, og ^ angiver eksponentiering. (Hash-værdien for den tomme streng er nul.)

Der er sandsynligvis meget bedre derude, men dette er ret udbredt og synes at være en god kompromis mellem hastighed og unikhed.

Kommentarer

• Jeg ville ‘ ikke bruge nøjagtigt det samme en bruges her, da det ‘ stadig er relativt let at producere kollisioner med dette. Det ‘ er bestemt ikke forfærdeligt, men der er meget bedre derude. Og hvis der ‘ ikke er nogen væsentlig grund til at være kompatibel med Java, skal det ikke vælges.
• Hvis du stadig vælger dette af hash af en eller anden grund, kan du i det mindste bruge en bedre prime som 92821 som en multiplikator. Det reducerer kollisioner meget. stackoverflow.com/a/2816747/21499
• Du kan lige så godt bruge FNV1a i stedet. Det ‘ er også en simpel multiplikationsbaseret hash, men bruger en større multiplikator, som spreder hashen bedre.
• Du don ‘ vil ikke gøre s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Undgå el-operatøren (^) og gør det på denne måde: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Ja, i koden er det (og skal gøres) iterativt, det var bare lettere at forstå i en lukket formel.

Først og fremmest, hvorfor har du brug for at implementere din egen hashing? For de fleste opgaver skal du få gode resultater med datastrukturer fra et standardbibliotek, forudsat at der er en implementering tilgængelig (medmindre du bare gør dette for din egen uddannelse).

Hvad angår faktiske hashingalgoritmer, er min personlige favorit FNV. 1

Her er et eksempel på implementering af 32-bit versionen 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 lidt bedre med tilfældighed. Skift rækkefølgen af * og ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619