Care algoritm hash este cel mai bun pentru unicitatea și viteza? Exemplu (bun) utilizări includ hash dicționare.
Știu că există lucruri, cum ar fi SHA-256 și astfel, dar acești algoritmi sunt proiectat fi sigur, care înseamnă, de obicei, acestea sunt mai lente decât algoritmi care sunt mai puțin unic. Vreau un hash algoritm conceput pentru a fi rapid, dar rămâne destul de unic pentru a evita coliziunile.
Am testat unele algoritmi diferite, măsurând viteza și numărul de coliziuni. Am folosit trei seturi principale:
"1"
la "216553"
(cred coduri ZIP, și cum o slabă dispersie a luat în jos msn.com) xor
mai degrabă decât +
) Fiecare rezultat conține medie hash timp, ș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:
Da. Am început să-mi scriu program de testare pentru a vedea dacă hash coliziuni de fapt se întâmple - și nu sunt doar un construct teoretic. Ei fac într-adevăr să se întâmple: FNV-1 coliziuni
creamwove
se ciocnește cu quists`
FNV-1a coliziuni dublă
se ciocnește cu "lichid" declinate
se ciocnește cu macallums` altarage
se ciocnește cu zinke` altarages
se ciocnește cu zinkes`
Murmur2 coliziuni cataractă
se ciocnește cu periti` roquette
se ciocnește cu skivie` sal
se ciocnește cu stormbound` dowlases
se ciocnește cu tramontane` cricketings
se ciocnește cu twanger` longans
se ciocnește cu liberali
DJB2 coliziuni hetairas
se ciocnește cu mentioner` heliotropes
se ciocnește cu neurospora` depravement
se ciocnește cu serafins` stilist
se ciocnește cu subgenuri` vesel
se ciocnește cu synaphea` redescribed
se ciocnește cu urites` dram
se ciocnește cu vivency`
DJB2a coliziuni haggadot
se ciocnește cu loathsomenesses` adorablenesses
se ciocnește cu rentabilitatea` dramaturg
se ciocnește cu snush` de scriere dramatică
se ciocnește cu snushing` treponematoses
se ciocnește cu paturi de apă`
CRC32 coliziuni codding
se ciocnește cu gnu` exhibiters
se ciocnește cu schlager`
SuperFastHash coliziuni dahabiah
se ciocnește cu drapability` encharm
se ciocnește cu enclave` grahami se ciocnește cu gramary
se ciocnește cu privegheri
turnători
se ciocnește cu vinic`
Randomnessification Alte subiective măsură este modul aleatoriu distribuite de hash sunt. Cartografiere rezultat HashTables arată cât de uniform datele sunt distribuite. Toate funcțiile hash show distribuție bună atunci când cartografiere tabelul liniar:
Sau ca un Hilbert Hartă (XKCD este întotdeauna relevant):
Cu excepția cazului când hashing numărul de siruri de caractere ("1"
, "2"
, ..., "216553"
) (de exemplu, coduri), unde modele încep să apară în cele mai multe algoritmi hash:
SDBM:
DJB2a:
FNV-1:
Toate, cu excepția FNV-1a, care încă arată destul de aleatoare pentru mine:
În fapt, Murmur2 pare a fi chiar mai bine intamplarea cu Numere "decât" FNV-1a`:
*Când mă uit la
FNV-1a
"număr" harta, m-am *cred văd subtile modele verticale. Cu Murmur eu nu vad nici modele, la toate. Tu ce crezi?*Suplimentar *`
** în tabel denotă cât de rău intamplarea este. Cu FNV-1a
a fi cel mai bun, șiDJB2x
fiind cel mai rău:
Murmur2: .
FNV-1a: .
FNV-1: ▪
DJB2: ▪▪
DJB2a: ▪▪
SDBM: ▪▪▪
SuperFastHash: .
CRC: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
Loselose: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
▪
▪▪▪▪▪▪▪▪▪▪▪▪▪
▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
La FNV1 hash vine în variante de întoarcere 32, 64, 128, 256, 512 și 1024 bit hash-uri. De FNV-1a algoritmul:
hash = FNV_offset_basis
for each octetOfData to be hashed
hash = hash xor octetOfData
hash = hash * FNV_prime
return hash
Unde constantele FNV_offset_basis " și " FNV_prime
depinde de revenirea hash dimensiunea dorită:
Hash Size
===========
32-bit
prime: 2^24 + 2^8 + 0x93 = 16777619
offset: 2166136261
64-bit
prime: 2^40 + 2^8 + 0xb3 = 1099511628211
offset: 14695981039346656037
128-bit
prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
offset: 144066263297769815596495629667062367629
256-bit
prime: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
512-bit
prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
1024-bit
prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915
Nr. FNV-1a este tot în jurul valorii de mai bine. Există mai multe coliziuni cu FNV-1a atunci când se utilizează cuvântul englezesc corpus:
Hash Word Collisions
====== ===============
FNV-1 1
FNV-1a 4
Acum compara cu litere mici și majuscule:
Hash lowercase word Collisions UPPERCASE word collisions
====== ========================= =========================
FNV-1 1 9
FNV-1a 4 11
În acest caz FNV-1a e't "400%" mai rău decât FN-1, doar 20% mai rău. Cred ca cel mai important de reținut este că există două clase de algoritmi atunci când vine vorba de coliziuni:
Până azi am fost de gând să utilizeze FNV-1a ca de facto hash-table algoritm hash. Dar acum m-am'm de trecerea la Murmur2:
SuperFastHash
algoritmul am găsit; - l's prea proaste pentru a fi la fel de popular cum este.
Actualizare:** De la MurmurHash3 pagina pe Google: (1) - SuperFastHash foarte sărac în coliziune proprietăți, care au fost documentate în altă parte. Deci cred că's nu doar pe mine. Actualizare: mi-am dat seama de ce
Murmur
este mai rapid decât ceilalți. MurmurHash2 funcționează pe patru octeți la un moment dat. Majoritatea algoritmilor sunt octet cu octet:
for each octet in Key
AddTheOctetToTheHash
Un timp post de Raymond Chen reiterează faptul că "aleatorie" Guid-urile nu sunt menite să fie folosite pentru dezordine. Ei, sau o parte dintre ei, sunt improprii ca un hash cheie:
Chiar Versiunea 4 GUID algoritm nu este garantat de a fi imprevizibil, deoarece algoritmul nu se specifica calitatea de generatorul de numere aleatorii. Articolul Wikipedia pentru GUID conține primare de cercetare care sugerează că viitorul și anterior Guid-urile pot fi prezise pe baza cunoștințelor de generatorul de numere aleatorii stat, deoarece generatorul nu este criptografice puternice. Randomess nu este la fel ca de evitare a coliziunii; care este de ce ar fi o greșeală să încerci să inventeze propriul "hash" algoritm de a lua un subset de o "aleatorie" guid:
int HashKeyFromGuid(Guid type4uuid)
{
//A "4" is put somewhere in the GUID.
//I can't remember exactly where, but it doesn't matter for
//the illustrative purposes of this pseudocode
int guidVersion = ((type4uuid.D3 & 0x0f00) >> 8);
Assert(guidVersion == 4);
return (int)GetFirstFourBytesOfGuid(type4uuid);
}
Dacă sunteți în care doresc pentru a crea un hash map de la o neschimbătoare dicționar, ați putea dori să ia în considerare perfect hashing https://en.wikipedia.org/wiki/Perfect_hash_function - în timpul construcției de funcție hash și tabel hash, vă pot garanta, pentru un anumit set de date, că nu vor exista coliziuni.
Aici este o listă de funcții hash, dar versiunea scurtă este:
Dacă doriți doar să aibă o bună funcție hash, și nu pot să aștept,
djb2
este una dintre cele mai bune șir de funcții hash știu. Are o excelentă distribuție și de viteză pe mai multe perechi de chei diferite ș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;
}
CityHash de Google este algoritmul sunteți în căutarea pentru. Nu este bine pentru criptografie, dar este bun pentru a genera hash unic.
Citit blog pentru mai multe detalii și cod este disponibil aici.
CityHash este scris în C++. Există, de asemenea, este o simplă C port.
Toate CityHash funcții sunt reglate pentru procesoare pe 64 de biți. Asta a spus, ei vor rula (cu excepția pentru noi cei care folosesc SSE4.2) în 32-bit cod. Au câștigat't fi foarte rapid, deși. Poate doriți să utilizați Murmur sau altceva în 32-bit cod.
Am'am trasat o scurtă comparație viteză de diferite algoritmi hash când hash de fișiere.
Parcelele individuale diferă doar puțin în metoda de citire și poate fi ignorat aici, din moment ce toate fișierele au fost stocate într-un tmpfs. Prin urmare, valoarea de referință a fost nu IO-legat, dacă vă întrebați.
Algoritmi includ: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}
.
Concluzii:
CRC
instrucțiuni, care PROCESORUL meu nu are. SpookyHash a fost în cazul meu întotdeauna un pic înainte de a CityHash.Sursa folosit pentru parcele:
SHA algoritmi (inclusiv SHA-256) sunt proiectat fi rapid.
În fapt, viteza lor poate fi o problemă uneori. În special, o tehnică comună pentru stocarea o parolă derivate token este de a rula un standard de repede hash algoritm de 10.000 de ori (stocarea hash hash hash hash de ... parola).
#!/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)
știu că există lucruri cum ar fi SHA-256 și astfel, dar acești algoritmi sunt proiectat fi sigur, care înseamnă, de obicei, acestea sunt mai lente decât algoritmi care sunt mai puțin unic.
Ipoteza că funcțiile hash criptografice sunt mai unic este greșit, și, de fapt, se poate dovedi a fi de multe ori înapoi în practică. În adevărul:
Ceea ce înseamnă că un non-criptografice hash funcția poate fi mai puține coliziuni decât un criptografice unul pentru "bun" set de date—seturi de date pentru care a fost proiectat.
Putem de fapt să demonstreze acest lucru cu datele din Ian Boyd's de răspuns și un pic de matematică: de Ziua problema. Formula pentru numărul estimat de coliziune perechi dacă alegeți n
numere întregi la întâmplare, dintr-set [1, d]
este aceasta (luate de pe Wikipedia):
n - d + d * ((d - 1) / d)^n
Conectarea n
= 216,553 și " d " = 2^32 ajungem despre 5.5 așteptat coliziuni. Ian's teste cea mai mare parte a afișa rezultatele în jurul valorii de cartier, dar cu o dramatică excepție: cele mai multe dintre funcțiile fost zero coliziuni în numere consecutive teste. Probabilitatea de a alege 216,553 32-bit numere la întâmplare și obținerea zero coliziuni este de aproximativ 0.43%. Și că's doar pentru o singură funcție—aici avem cinci distincte funcție hash familii cu zero coliziuni!
Deci, ceea ce am're aici este că hash-uri care Ian testat interacționează favorabil cu numere consecutive de date—de exemplu, ei're dispersat minim de intrari diferite mai mult decât un ideal criptografice hash funcția de ar. (Notă: acest lucru înseamnă că Ian's grafică de evaluare care FNV-1a și MurmurHash2 "uite aleatorie" să-l în numerele set de date poate fi respins de la propriile sale date. Zero coliziuni pe un set de date de dimensiune, care, pentru ambele funcții hash, este izbitor regulat!)
Acest lucru nu este o surpriză, deoarece acesta este un comportament dezirabil pentru multe utilizări de funcții hash. De exemplu, tabel hash cheile sunt adesea foarte asemănătoare; Ian's răspuns menționează o problema MSN avut-o odată cu codul POSTAL hash tables. Aceasta este o utilizare în cazul în care evitare a coliziunii pe probabil intrări câștigă peste aleator, cum ar fi comportamentul.
Un alt instructiv comparație aici este contrastul în obiectivele de proiectare între CRC și funcții hash criptografice:
Deci, pentru CRC este din nou bun pentru a avea mai puține coliziuni decât aleator în minim de intrari diferite. Cu criptare hash-uri, acesta este un nu-nu!
Folosi SipHash. A multe proprietăți de dorit:
Rapid. Un optimizat punerea în aplicare durează în jur de 1 ciclu pe octet.
Secure. SipHash este un puternic PRF (pseudoaleatoare funcție). Acest lucru înseamnă că este imposibil de distins de o funcție aleatoare (dacă nu știi 128-bit cheie secretă). Prin urmare:
Nu este nevoie să vă faceți griji cu privire tabel hash sonde de a deveni liniar timp din cauza coliziunilor. Cu SipHash, te stiu pe care le va obține în medie-în caz de performanță, în medie, indiferent de intrări.
Imunitate la hash bazate pe respingerea atacurilor asupra serviciului.
Puteți utiliza SipHash (mai ales versiunea cu 128-bit output) ca un MAC (Message Authentication Code). Dacă primiți un mesaj și un SipHash tag-ul, și tag-ul este la fel ca cea de la care rulează SipHash cu cheie secretă, atunci știți că oricine a creat hash a fost, de asemenea, în posesia cheie secretă, și că nici mesaj, nici de hașiș au fost modificate de atunci.
Depinde de datele pe care le sunt de hashing. Unele hashing funcționează mai bine cu date specifice, cum ar fi text. Unii algoritmi hash-au specificaly conceput pentru a fi bun pentru date specifice.
Paul Hsieh, odată ce a făcut fast hash. El enumeră codul sursă și explicații. Dar era deja bătut. :)
Java foloseste acest simplu multiplica și se adaugă algoritm:
codul hash pentru un obiect Șir este calculat ca
s[0]31^(n-1) + s131^(n-2) + ... + s[n-1]
folosind int aritmetică, unde
s[i]
este i-lea caracter din șir,n este lungimea șirului, și
^` indică exponentiala. (Valoarea hash șir gol este zero.)
Există, probabil, mult mai bine cei de acolo, dar acest lucru este destul de răspândită și pare a fi un bun compromis între viteză și unicitatea.
Mai întâi de toate, de ce ai nevoie pentru a pune în aplicare propriile hashing? Pentru cele mai multe sarcini ar trebui să obține rezultate bune cu structuri de date de la un standard de bibliotecă, presupunând că acolo's o implementare disponibile (dacă nu're fac asta doar pentru propria educație).
În măsura în real algoritmi hash merge, preferata mea este FNV. 1
Aici's un exemplu de implementare a 32-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;
}