Am testat câțiva algoritmi diferiți, măsurând viteza și numărul de coliziuni .

Am folosit trei seturi de chei diferite:

• O listă de 216.553 de cuvinte în limba engleză ^{🕗  arhivă} (cu litere mici)
• Numerele "1" până la "216553" (gândiți-vă la coduri poștale și cum un hash slab a luat jos msn.com / a> 🕗  arhivă )
• 216.553 ” aleatoriu „(de exemplu, tip 4 uuid ) GUID-uri

Pentru fiecare corpus, numărul de coliziuni și timpul mediu petrecut în hash a fost înregistrat.

Am testat:

• DJB2
• DJB2a (varianta care utilizează xor mai degrabă decât +)
• FNV-1 (32 de biți)
• FNV-1a (32 de biți)
• SDBM
• CRC32
• Murmur2 (32 de biți)
• SuperFastHash

Rezultate

Fiecare rezultat conține timpul de hash mediu și numărul de coliziuni

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 

Note :

• Algoritmul LoseLose (unde hash = hash + caracter) este cu adevărat îngrozitor . Totul se ciocnește în aceleași 1.375 de găleți
• SuperFastHash este rapid, lucrurile arătând destul de împrăștiate; după bunătatea mea, coliziunile număr . Sper că tipul care l-a portat a greșit ceva; este destul de rău
• CRC32 este destul de bun . Mai lent și un tabel de căutare de 1k

Se întâmplă efectiv coliziunile?

Da. Am început să scriu programul meu de testare pentru a vedea dacă se întâmplă coliziuni hash de fapt – și nu sunt doar o construcție teoretică.Într-adevăr, se întâmplă:

Coliziuni FNV-1

• creamwove se ciocnește de quists

FNV -1a coliziuni

• costarring se ciocnește cu liquid
• declinate se ciocnește cu macallums
• altarage se ciocnește cu zinke
• altarages se ciocnește cu zinkes

Coliziuni Murmur2

• cataract se ciocnește cu periti
• roquette se ciocnește cu skivie
• shawl se ciocnește cu stormbound
• dowlases se ciocnește cu tramontane
• cricketings se ciocnește cu twanger
• longans se ciocnește cu whigs

coliziuni DJB2

• hetairas se ciocnește cu mentioner
• heliotropes se ciocnește cu neurospora
• depravement se ciocnește cu serafins
• stylist se ciocnește cu subgenera
• joyful se ciocnește cu synaphea
• redescribed se ciocnește cu urites
• dram se ciocnește cu vivency

coliziuni DJB2a

• haggadot se ciocnește cu loathsomenesses
• adorablenesses se ciocnește cu rentability
• playwright se ciocnește cu snush
• playwrighting se ciocnește cu snushing
• treponematoses se ciocnește cu waterbeds

coliziuni CRC32

• codding se ciocnește cu gnu
• exhibiters se ciocnește cu schlager

coliziuni SuperFastHash

• dahabiah se ciocnește cu drapability
• encharm se ciocnește cu enclave
• grahams se ciocnește cu gramary
• … trage 79 de coliziuni …
• night se ciocnește cu vigil
• se ciocnește cu vigils
• finks se ciocnește cu vinic

Randomnessification

Cealaltă măsură subiectivă este cât de distribuite aleatoriu sunt hashurile. Cartarea HashTables rezultate arată cât de uniform sunt distribuite datele. Toate funcțiile hash prezintă o distribuție bună la maparea liniară a tabelului:

Sau ca Hilbert Map ( XKCD este întotdeauna relevant ):

Cu excepția codurilor de număr hashing ("1", "2", …, "216553") (de exemplu, coduri poștale ), unde încep modelele să apară în majoritatea algoritmilor de hash:

SDBM :

DJB2a :

FNV-1 :

Toate cu excepția

Dacă doriți să creați o hartă hash dintr-un dicționar neschimbător, vă recomandăm să luați în considerare hash perfect https://en.wikipedia.org/wiki/Perfect_hash_function – în timpul construcției funcției hash și a tabelului hash, puteți garanta, pentru un set de date dat, că nu vor exista coliziuni.

Comentarii

• Aici ‘ mai multe despre (minim) Hashing perfect burtleburtle.net/bob/hash/perfect.html inclusiv date despre performanță, deși nu ‘ nu folosește cel mai recent procesor etc.
• Este ‘ destul de evident, dar merită subliniat faptul că, pentru a garanta că nu există coliziuni, cheile ar trebui să aibă aceeași dimensiune ca valorile, cu excepția cazului în care Există constrângeri asupra valorilor pe care algoritmul le poate valorifica.
• @ devios1 Afirmația dvs. nu are sens. În primul rând, valorile dintr-un tabel hash, perfecte sau nu, sunt independente de chei. În al doilea rând, un tabel hash perfect este doar o matrice liniară de valori, indexate după rezultatul funcției create astfel încât toți indicii să fie unici.
• @MarcusJ Hash perfect este de obicei utilizat cu mai puțin de 100 tastele, dar aruncați o privire la cmph.sourceforge.net … încă departe de raza dvs. de acțiune.
• @DavidCary linkul acceptă revendicarea dvs. Este posibil să fi confundat O (1) cu ” fără coliziuni „, dar acestea nu sunt ‘ nu este deloc același lucru. Desigur, hashing-ul perfect nu garantează coliziuni, dar necesită ca toate tastele să fie cunoscute în prealabil și să fie relativ puține. (Dar consultați linkul către cmph de mai sus.)

Aici este o listă de funcții hash, dar versiunea scurtă este:

Dacă doriți doar să aveți o funcție hash bună și nu pot aștepta, djb2 este una dintre cele mai bune funcții de hash șir pe care le cunosc. Are o distribuție și o viteză excelente pe multe seturi diferite de chei și dimensiuni de masă

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

Comentarii

• De fapt, djb2 este zero, deoarece majoritatea acestor funcții hash simple, astfel încât să puteți sparge cu ușurință astfel de hash-uri.Are o prejudecată proastă, prea multe coliziuni și o distribuție defectuoasă, se rupe la majoritatea testelor de calitate smashher: Vezi github.com/rurban/smhasher/blob/master/doc/bernstein Baza de date a CD-ului său îl folosește, dar nu l-aș folosi ‘ cu acces public.
• DJB este destul de rău din punct de vedere al performanței și al distribuției. Nu ‘ l-aș folosi astăzi.
• @ConradMeyer Pariez ‘, DJB poate fi accelerat de un factor de trei la fel ca în această întrebare a mea și apoi ‘ a bătut probabil cei mai mulți algoritmi utilizabili. În ceea ce privește distribuția, sunt de acord. Un hash care produce coliziuni chiar și pentru două șiruri de litere nu poate ‘ să fie foarte bun.
• Băieți, am îndoieli. Spuneți că djb2 este rău, dar rezultatele testului răspunsului acceptat arată că este bun.
• S-ar putea să utilizați cel puțin un prim sensibil care produce mai puține coliziuni în loc de 33. stackoverflow.com/a/2816747/21499

CityHash by Google este algoritmul pe care îl căutați. Nu este bun pentru criptografie, dar este bun pentru a genera hash-uri unice.

Citiți blogul pentru mai multe detalii și este disponibil aici .

CityHash este scris în C ++. Există, de asemenea, un port C simplu .

Despre suportul pe 32 de biți:

Toate funcțiile CityHash sunt reglate pentru procesoare pe 64 de biți. Acestea fiind spuse, vor rula (cu excepția celor noi care utilizează SSE4.2) în cod pe 32 de biți. Nu vor fi însă foarte rapide. Poate că doriți să utilizați Murmur sau altceva în codul de 32 de biți.

Comentarii

• Se pronunță CityHash similar cu ” Sushi de oraș? ”
• Aveți un uitați-vă și la SipHash, este menit să înlocuiască MurmurHash / CityHash / etc.: 131002.net/siphash
• De asemenea, consultați FarmHash, un succesor al CitHash. code.google.com/p/farmhash
• xxHash susține că este de 5 ori mai rapid decât CityHash.
• plain C port link-ul este rupt

Am trasat o comparație de viteză scurtă a diferiților algoritmi de hash atunci când hashează fișiere.

Graficele individuale diferă ușor doar în metoda de citire și pot fi ignorate aici, deoarece toate fișierele au fost stocate într-un tmpfs. Prin urmare, criteriul de referință nu a fost legat de IO dacă vă întrebați.

• Scală liniară
• Scară logaritmică

Algoritmii includ: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Concluzii:

• Funcțiile hash non-criptografice precum Murmur3, Cityhash și Spooky sunt destul de apropiate. Ar trebui să rețineți că Cityhash poate fi mai rapid pe procesoarele cu SSE 4.2s CRC, pe care CPU-ul meu nu le are. SpookyHash a fost întotdeauna un pic în cazul meu înainte de CityHash.
• MD5 pare să fie un bun compromis atunci când se utilizează funcții hash criptografice, deși SHA256 poate fi mai sigur pentru vulnerabilități de coliziune ale MD5 și SHA1.
• Complexitatea tuturor algoritmilor este liniară – ceea ce nu este deloc surprinzător, deoarece funcționează în bloc. (Am vrut să văd dacă metoda de citire face diferența, deci puteți compara doar valorile din dreapta).
• SHA256 a fost mai lent decât SHA512.
• Nu am investigat aleatoritatea funcțiile hash. Dar aici este o comparație bună a funcțiilor hash care lipsesc în răspunsul Ian Boyds . Acest lucru subliniază că CityHash are unele probleme în cazurile de colț.

Sursa utilizată pentru parcele:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (îmi pare rău pentru codul urât)

Comentarii

• Graficul la scară liniară întrerupe eticheta axei y, care spune ce cantitate trasează. Cred că probabil ar fi ” timp în secunde „, la fel ca scara logaritmică. Merită rezolvat ‘.

Știu că există lucruri precum SHA-256 și altele, dar acești algoritmi sunt proiectați să fie securizat , ceea ce înseamnă, de obicei, că este mai lent decât algoritmii care sunt mai puțin unici .

Presupunerea că funcțiile hash criptografice sunt mai unice este greșită și, de fapt, se poate demonstra că este adesea înapoi în practică. În realitate:

1. În mod ideal, funcțiile de hash criptografice ar trebui să fie indistincte de aleatorii ;
2. Dar cu funcții hash non-criptografice, este de dorit ca aceștia să să interacționeze favorabil cu intrările probabile .

Ceea ce înseamnă că o funcție hash non-criptografică poate avea mai puține coliziuni decât unul criptografic pentru un set de date „bun” – seturi de date pentru care a fost conceput.

Putem demonstra acest lucru cu datele din răspunsul lui Ian Boyd și un pic de matematică: Problemă de ziua de naștere . Formula pentru numărul așteptat de perechi care se ciocnesc dacă alegeți n numere întregi la întâmplare din setul [1, d] este aceasta (preluată din Wikipedia):

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

Conectarea n = 216.553 și d = 2 ^ 32 primim aproximativ 5.5 coliziuni așteptate . Testele lui Ian arată în mare parte rezultate în jurul cartierului respectiv, dar cu o excepție dramatică: majoritatea funcțiilor au zero coliziuni în teste de numere consecutive. Probabilitatea de a alege 216.553 de numere pe 32 de biți la întâmplare și de a obține coliziuni zero este de aproximativ 0,43%. Și asta este doar pentru o funcție – aici avem cinci familii de funcții hash distincte cu zero coliziuni!

Deci, ceea ce vedem aici este că hash-urile pe care Ian le-a testat interacționează favorabil cu setul de date de numere consecutive – adică, ele „dispersează minim diferite intrări mai larg decât ar fi o funcție hash criptografică ideală. (Notă laterală: aceasta înseamnă că evaluarea grafică a lui Ian că FNV-1a și MurmurHash2 îi „par aleatorii” în setul de date numerice pot fi respinse din propriile sale date. Zero coliziuni pe un set de date de acea dimensiune, pentru ambele funcții hash, este izbitor de neobișnuit!)

Aceasta nu este o surpriză, deoarece acesta este un comportament de dorit pentru multe utilizări ale funcțiilor hash. De exemplu, tastele tabelului hash sunt adesea foarte similare; Răspunsul lui Ian menționează o problemă pe care MSN a avut-o odată cu tabelele de hash cod poștal . Aceasta este o utilizare în care evitarea coliziunilor la intrările probabile câștigă comportamentul aleatoriu.

O altă comparație instructivă aici este contrastul dintre obiectivele de proiectare dintre funcțiile CRC și hash criptografice:

• CRC este conceput pentru a detecta erori rezultate din canalele de comunicații zgomotoase , care probabil vor fi un număr mic de bit flips;
• Hash-urile criptografice sunt concepute pentru a prinde modificările făcute de atacatorii rău intenționati , cărora li se alocă resurse de calcul limitate, dar în mod arbitrar multă istețime.

Deci, pentru CRC este din nou bine să existe mai puține coliziuni decât aleatorii în intrări minim diferite. Cu hashuri criptografice, acesta este un nu-nu!

Algoritmii SHA (inclusiv SHA-256) sunt proiectat pentru a fi rapid .

De fapt, viteza lor poate fi uneori o problemă. În special, o tehnică obișnuită pentru stocarea unui token derivat din parolă este de a rula un algoritm hash rapid standard de 10.000 de ori (stocarea hashului hashului hashului hashului hashului … parolei).

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

Ieșire:

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

Comentarii

• ‘ este relativ rapid, sigur, pentru un algoritm de hash criptografic . Dar OP vrea doar să stocheze valori într-un hashtable și nu cred că ‘ cred că o funcție hash criptografică este cu adevărat potrivită pentru asta.
• Întrebarea a fost ridicată (tangențial, acum apare) subiectul funcțiilor hash criptografice. Acesta este ‘ bitul la care răspund.
• Doar pentru a amâna oamenii de la ideea ” În special , o tehnică obișnuită pentru stocarea unui token derivat din parolă este rularea unui algoritm de hash rapid rapid de 10.000 de ori ” – în timp ce obișnuit, acela ‘ e pur și simplu prost. Există algoritmi proiectați pentru aceste scenarii, de exemplu, bcrypt. Utilizați instrumentele potrivite.
• Hash-urile criptografice sunt concepute pentru a avea un randament ridicat, dar asta înseamnă adesea că au configurare ridicată, eliminare, .rodata și / sau costuri de stat .Când doriți un algoritm pentru un hashtable, de obicei aveți chei foarte scurte și multe dintre ele, dar nu aveți nevoie de garanțiile suplimentare pe care le are o criptografică. Folosesc singur un Jenkins modificat unul câte unul.
• @ChrisMorgan: mai degrabă decât folosind un hash securizat criptografic, HashTable DoS poate fi rezolvat mult mai eficient folosind hash randomization, astfel încât fiecare rundă de programele sau chiar pe fiecare hashtable, astfel încât datele nu ‘ nu sunt grupate în același compartiment de fiecare dată.

Utilizați SipHash . Are multe proprietăți dorite:

• Rapid. O implementare optimizată durează aproximativ 1 ciclu pe octet.

• Secure. SipHash este un PRF puternic (funcție pseudorandom). Aceasta înseamnă că nu se distinge de o funcție aleatorie (cu excepția cazului în care știți cheia secretă pe 128 de biți). Prin urmare:

  • Nu este nevoie să vă faceți griji cu privire la faptul că sondele dvs. de tabel hash devin timp liniar din cauza coliziunilor. Cu SipHash, știți că veți obține performanța medie a cazurilor în medie, indiferent de intrări.

  • Imunitate la atacuri de refuzare a serviciului bazate pe hash.

  • Puteți utiliza SipHash (în special versiunea cu ieșire pe 128 de biți) ca MAC (Cod de autentificare a mesajului). Dacă primiți un mesaj și o etichetă SipHash, iar eticheta este aceeași cu cea de la rularea SipHash cu cheia dvs. secretă, atunci știți că oricine a creat hash-ul era de asemenea în posesia cheii dvs. secrete și că nici mesajul, nici hash-ul a fost modificat de atunci.

Comentarii

• Isn ‘ t SipHash exagerat dacă nu aveți nevoie de securitate? Necesită o cheie de 128 de biți, care este doar o semință hash glorificată. Ca să nu mai vorbim de MurmurHash3 are o ieșire pe 128 de biți, iar SipHash are doar o ieșire pe 64 de biți. Evident, rezumatul mai mare are o șansă mai mică de coliziune.
• @bryc Diferența este că SipHash va continua să se comporte bine, chiar și în caz de intrare rău intenționată. Un tabel hash bazat pe SipHash poate fi utilizat pentru date din surse potențial ostile și poate utiliza un algoritm, cum ar fi sondarea liniară, care este foarte sensibil la detaliile funcției hash.
• Siphash (și prng mai recent conexe funcții de stil) este alegerea mea implicită pentru securitate. Pentru performanță, xxhash este greu de învins. Există o mulțime de sfaturi proaste pe internet, chiar și în discuțiile de aici. Performanța bună la intrările aleatorii sau semi-aleatorii nu are sens. Care este cel mai prost caz de performanță, cu intrări din lumea reală? Care este rezultatul cu intrări dăunătoare? Tabelul dvs. de hash va deveni în cele din urmă un vector de atac.

Depinde de datele pe care le hash. Unele hash funcționează mai bine cu date specifice, cum ar fi textul. Unii algoritmi de hash au fost concepuți special pentru a fi buni pentru date specifice.

Paul Hsieh a făcut odată hash rapid . El listează codul sursă și explicațiile. Dar a fost deja bătut. 🙂

Java utilizează acest simplu înmulțire -și adăugați algoritm:

Codul hash pentru un obiect String este calculat ca

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

folosind aritmetica int, unde s[i] este i ​ – al treilea caracter al șirului, n este lungimea șirului și ^ indică exponențierea. (Valoarea hash a șirului gol este zero.)

Probabil că există altele mult mai bune, dar acest lucru este destul de răspândit și pare a fi compromis între viteză și unicitate.

Comentarii

• Nu aș folosi ‘ exact același lucru unul folosit aici, deoarece ‘ este încă relativ ușor de produs coliziuni cu aceasta. ‘ nu categoric nu este teribil, dar există altele mult mai bune acolo. Și dacă ‘ nu există niciun motiv semnificativ pentru a fi compatibil cu Java, nu ar trebui să fie ales nu .
• Dacă totuși alegeți acest lucru mod de hash, dintr-un anumit motiv, ați putea folosi cel puțin un prim mai bun, cum ar fi 92821 ca multiplicator. Asta reduce coliziunile mult. stackoverflow.com/a/2816747/21499
• La fel de bine puteți utiliza FNV1a. ‘ este, de asemenea, un hash simplu bazat pe multiplicare, dar folosește un multiplicator mai mare, care dispersează mai bine hash-ul.
• Nu ‘ nu vreau să fac s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Evitați operatorul de alimentare (^) și faceți acest lucru: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Da, în cod este (și ar trebui să fie) realizat iterativ, a fost doar mai ușor de înțeles într-o formulă închisă.

În primul rând, de ce trebuie să îți implementezi propriul hash? Pentru majoritatea sarcinilor, ar trebui să obțineți rezultate bune cu structurile de date dintr-o bibliotecă standard, presupunând că există o implementare disponibilă (cu excepția cazului în care faceți acest lucru doar pentru propria educație).

În ceea ce privește algoritmii de hashing reali, favoritul meu personal este FNV. 1

Iată un exemplu de implementare a versiunii pe 32 de biți în 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; } 

Comentarii

• Varianta FNV-1a este ușor mai bună la întâmplare. Schimbați ordinea * și ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619