Ho testato diversi algoritmi, misurando la velocità e il numero di collisioni .

Ho utilizzato tre diversi set di chiavi:

• Un elenco di 216.553 parole inglesi ^{🕗  archivio} (in minuscolo)
• I numeri "1" a "216553" (pensa ai codici postali e come un hash scadente ha eliminato msn.com ^{🕗  archivio} )
• 216,553 ” random “(ie type 4 uuid ) GUID

Per ogni corpus, il numero di collisioni e il tempo medio impiegato per lhashing è stato registrato.

Ho testato:

• DJB2
• DJB2a (variante che utilizza xor anziché +)
• FNV-1 (32 bit)
• FNV-1a (32 bit)
• SDBM
• CRC32
• Murmur2 (32 bit)
• SuperFastHash

Risultati

Ogni risultato contiene il tempo hash medio e il numero di collisioni

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 :

• Il Lalgoritmo LoseLose (dove hash = hash + character) è veramente orribile . Tutto collide negli stessi 1.375 bucket
• SuperFastHash è veloce, con le cose che sembrano piuttosto sparse; per mio Dio le numero collisioni. Spero che il tizio che ha eseguito il port abbia sbagliato qualcosa; è piuttosto brutto
• CRC32 è abbastanza buono . Più lento e una tabella di ricerca di 1k

Le collisioni si verificano effettivamente?

Sì. Ho iniziato a scrivere il mio programma di test per vedere se le collisioni di hash effettivamente si verificano – e non sono solo un costrutto teorico.In effetti accadono:

Collisioni FNV-1

• creamwove collide con quists

FNV -1a collisioni

• costarring collide con liquid
• declinate si scontra con macallums
• altarage collide con zinke
• altarages collide con zinkes

Collisioni Murmur2

• cataract collide con periti
• roquette collide con skivie
• shawl entra in conflitto con stormbound
• dowlases entra in conflitto con tramontane
• cricketings collide con twanger
• longans con whigs

collisioni DJB2

• hetairas entra in collisione con mentioner
• heliotropes collide con neurospora
• depravement collide con serafins
• stylist entra in conflitto con subgenera
• joyful collide con synaphea
• redescribed collide con urites
• dram si scontra con vivency

DJB2a collisioni

• haggadot collide con loathsomenesses
• adorablenesses collide con rentability
• playwright collide con snush
• playwrighting collide con snushing
• treponematoses collide con waterbeds

collisioni CRC32

• codding entra in collisione con gnu
• exhibiters collide con schlager

collisioni SuperFastHash

• dahabiah si scontra con drapability
• encharm collide con enclave
• grahams collide con gramary
• … snip 79 collisioni …
• night collide con vigil
• collide con vigils
• finks collide con vinic

Randomnessification

Laltra misura soggettiva è la distribuzione casuale degli hash. La mappatura degli HashTables risultanti mostra la distribuzione uniforme dei dati. Tutte le funzioni hash mostrano una buona distribuzione durante la mappatura lineare della tabella:

O come Hilbert Map ( XKCD è sempre pertinente ):

Tranne quando si esegue lhashing di stringhe numeriche ("1", "2", …, "216553") (ad esempio, codici postali ), dove iniziano i pattern per emergere nella maggior parte degli algoritmi di hashing:

SDBM :

DJB2a :

FNV-1 :

Tutti tranne

Se desideri creare una mappa hash da un dizionario immutabile, potresti prendere in considerazione lhashing perfetto https://en.wikipedia.org/wiki/Perfect_hash_function – durante la costruzione della funzione hash e della tabella hash, puoi garantire, per un dato set di dati, che non ci saranno collisioni.

Commenti

• Qui ‘ ulteriori informazioni sullhashing perfetto (minimo) burtleburtle.net/bob/hash/perfect.html inclusi i dati sulle prestazioni, sebbene ‘ non utilizzi il processore più recente, ecc.
• È ‘ abbastanza ovvio, ma vale la pena sottolineare che per garantire lassenza di collisioni, le chiavi dovrebbero avere le stesse dimensioni dei valori, a meno che Ci sono vincoli sui valori su cui lalgoritmo può capitalizzare.
• @ devios1 La tua affermazione non ha senso. Innanzitutto, i valori in una tabella hash, perfetti o meno, sono indipendenti dalle chiavi. In secondo luogo, una tabella hash perfetta è solo una matrice lineare di valori, indicizzata dal risultato della funzione che è stata creata in modo che tutti gli indici siano unici.
• @MarcusJ Lhashing perfetto viene solitamente utilizzato con meno di 100 chiavi, ma dai unocchiata a cmph.sourceforge.net … ancora molto al di sotto della tua portata.
• @DavidCary Niente a portata di mano link supporta la tua richiesta. Forse hai confuso O (1) con ” nessuna collisione “, ma non sono ‘ t affatto la stessa cosa. Ovviamente, lhashing perfetto garantisce lassenza di collisioni, ma richiede che tutte le chiavi siano note in anticipo e che ce ne siano relativamente poche. (Ma vedi il link a cmph sopra.)

Ecco un elenco di funzioni hash, ma la versione breve è:

Se vuoi solo avere una buona funzione hash e non vedo lora, djb2 è una delle migliori funzioni di hash delle stringhe che conosco. Ha uneccellente distribuzione e velocità su molti diversi set di chiavi e dimensioni di tabella

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

Commenti

• In realtà djb2 è zero sensitive, come la maggior parte di queste semplici funzioni hash, quindi puoi facilmente rompere tali hash.Ha un cattivo bias, troppe collisioni e una cattiva distribuzione, si interrompe nella maggior parte dei test di qualità più sofisticati: vedi github.com/rurban/smhasher/blob/master/doc/bernstein Il suo database cdb lo usa, ma ‘ non lo userei con accesso pubblico.
• DJB è piuttosto scadente dal punto di vista delle prestazioni e della distribuzione. ‘ non lo userei oggi.
• @ConradMeyer I ‘ scommetterei, DJB può essere accelerato da un fattore tre proprio come in questa mia domanda e poi ‘ probabilmente supererebbe la maggior parte degli algoritmi utilizzabili. Per quanto riguarda la distribuzione, sono daccordo. Un hash che produce collisioni anche per due stringhe di lettere può ‘ essere veramente buono.
• Ragazzi, ho dei dubbi. Stai dicendo che djb2 è negativo, ma i risultati del test della risposta accettata mostrano che è buono.
• Potresti almeno usare un numero primo ragionevole che produca meno collisioni invece di 33. stackoverflow.com/a/2816747/21499

CityHash di Google è lalgoritmo che stai cercando. Non è adatto per la crittografia ma è utile per generare hash univoci.

Leggi il blog per maggiori dettagli e il è disponibile qui .

CityHash è scritto in C ++. Esiste anche una semplice porta C .

Informazioni sul supporto a 32 bit:

Tutte le funzioni CityHash sono ottimizzate per processori a 64 bit. Detto questo, verranno eseguiti (ad eccezione di quelli nuovi che utilizzano SSE4.2) in codice a 32 bit. Tuttavia, non saranno molto veloci. Potresti utilizzare Murmur o qualcosaltro nel codice a 32 bit.

Commenti

• CityHash pronunciato in modo simile a ” City Sushi? ”
• Avere un guarda anche SipHash, è destinato a sostituire MurmurHash / CityHash / ecc.: 131002.net/siphash
• Vedi anche FarmHash, un successore di CitHash. code.google.com/p/farmhash
• xxHash afferma di essere 5 volte più veloce di CityHash.
• plain C port il link non funziona

Ho “tracciato un breve confronto di velocità di diversi algoritmi di hashing durante lhashing dei file.

I singoli grafici differiscono solo leggermente nel metodo di lettura e possono essere ignorati qui, poiché tutti i file sono stati memorizzati in un tmpfs. Pertanto il benchmark non era vincolato allIO, se ve lo state chiedendo.

• Scala lineare
• Scala logaritmica

Gli algoritmi includono: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Conclusioni:

• Le funzioni hash non crittografiche come Murmur3, Cityhash e Spooky sono abbastanza vicine tra loro. Si dovrebbe notare che Cityhash potrebbe essere più veloce su CPU con istruzioni SSE 4.2 CRC, che la mia CPU non ha. SpookyHash nel mio caso era sempre un po prima di CityHash.
• MD5 sembra essere un buon compromesso quando si utilizzano le funzioni hash crittografiche, sebbene SHA256 possa essere più sicuro per vulnerabilità di collisione di MD5 e SHA1.
• La complessità di tutti gli algoritmi è lineare, il che non sorprende poiché funzionano a blocchi. (Volevo vedere se il metodo di lettura fa la differenza, in modo da poter confrontare solo i valori più a destra).
• SHA256 era più lento di SHA512.
• Non ho studiato la casualità di le funzioni hash. Tuttavia, qui è un buon confronto delle funzioni hash mancanti nella Ian Boyds answer . Ciò indica che CityHash ha alcuni problemi nei casi dangolo.

La fonte utilizzata per i grafici:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (scusa per il brutto codice)

Commenti

• Il grafico a scala lineare taglia letichetta dellasse y che dice quale quantità sta tracciando. Immagino che probabilmente sarebbe ” tempo in secondi “, uguale alla scala logaritmica. ‘ vale la pena aggiustarlo.

So che esistono cose come SHA-256 e simili, ma questi algoritmi sono progettati essere sicuro , il che di solito significa che sono più lenti degli algoritmi meno unici .

Lipotesi che le funzioni hash crittografiche siano più uniche è sbagliata, e in effetti si può dimostrare che nella pratica è spesso allindietro. In verità:

1. Le funzioni hash crittografiche idealmente dovrebbero essere indistinguibili da quelle casuali ;
2. Ma con le funzioni hash non crittografiche, è auspicabile che interagiscano favorevolmente con i probabili input .

Il che significa che una funzione hash non crittografica potrebbe avere meno collisioni di una crittografica per un set di dati “buono”: i set di dati per i quali è stato progettato.

Possiamo effettivamente dimostrarlo con i dati nella risposta di Ian Boyd e un po di matematica: il Problema di compleanno . La formula per il numero previsto di coppie in collisione se scegli n numeri interi a caso dallinsieme [1, d] è questa (presa da Wikipedia):

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

Collegamento di n = 216,553 e d = 2 ^ 32 otteniamo circa 5,5 collisioni previste . I test di Ian mostrano per lo più risultati intorno a quel quartiere, ma con una notevole eccezione: la maggior parte delle funzioni ha ottenuto zero collisioni nel test di numeri consecutivi. La probabilità di scegliere a caso 216.553 numeri a 32 bit e di ottenere zero collisioni è di circa lo 0,43%. E questo è solo per una funzione: qui abbiamo cinque famiglie di funzioni hash distinte con zero collisioni!

Quindi quello che stiamo vedendo qui è che gli hash testati da Ian interagiscono favorevolmente con il set di dati dei numeri consecutivi, ovvero si stanno disperdendo in minima parte input più ampiamente di quanto farebbe una funzione hash crittografica ideale. (Nota a margine: questo significa che la valutazione grafica di Ian secondo cui FNV-1a e MurmurHash2 gli “sembrano casuali” nel set di dati numerici può essere confutata dai suoi stessi dati. Zero collisioni su un set di dati di quella dimensione, per entrambe le funzioni hash, sono sorprendentemente non casuali!)

Questa non è una sorpresa perché questo è un comportamento desiderabile per molti usi delle funzioni hash Ad esempio, le chiavi delle tabelle hash sono spesso molto simili; La risposta di Ian menziona un problema che MSN aveva una volta con le tabelle hash del codice postale . Questo è un uso in cui levitamento delle collisioni su probabili input vince su comportamenti casuali.

Un altro confronto istruttivo qui è il contrasto negli obiettivi di progettazione tra CRC e funzioni hash crittografiche:

• CRC è progettato per rilevare errori derivanti da canali di comunicazione rumorosi , che potrebbero essere un numero ridotto di bit capovolge;
• Gli hash crittografici sono progettati per rilevare modifiche apportate da aggressori dannosi , a cui sono assegnate risorse di calcolo limitate ma arbitrariamente molta intelligenza.

Quindi per CRC è ancora buono avere meno collisioni che casuali in input minimamente diversi. Con gli hash crittografici, questo è un no!

Gli algoritmi SHA (incluso SHA-256) sono progettato per essere veloce .

In effetti, la loro velocità a volte può essere un problema. In particolare, una tecnica comune per memorizzare un token derivato da password consiste nelleseguire un algoritmo di hash veloce standard 10.000 volte (memorizzando lhash dellhash dellhash dellhash della … password).

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

Risultato:

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

Commenti

• ‘ è relativamente veloce, sicuro, per un algoritmo di hashing crittografico . Ma lOP vuole solo memorizzare i valori in una tabella hash, e non ‘ penso che una funzione hash crittografica sia veramente appropriata per questo.
• La domanda sollevata (tangenzialmente, ora appare) il soggetto delle funzioni hash crittografiche. Questo ‘ è il punto a cui sto rispondendo.
• Solo per scoraggiare le persone dallidea di ” In particolare , una tecnica comune per memorizzare un token derivato da password consiste nelleseguire un algoritmo di hash veloce standard 10.000 volte “, sebbene comune, che ‘ è semplicemente stupido. Esistono algoritmi progettati per questi scenari, ad esempio bcrypt. Utilizza gli strumenti giusti.
• Gli hash crittografici sono progettati per avere un throughput elevato, ma questo spesso significa che hanno costi elevati di configurazione, smontaggio, .rodata e / o di stato .Quando si desidera un algoritmo per una tabella hash, di solito si hanno chiavi molto brevi e molte di esse, ma non sono necessarie le garanzie aggiuntive di un hash crittografico. Io stesso uso personalmente un Jenkins ottimizzato.
• @ChrisMorgan: invece di usare un hash crittograficamente sicuro, HashTable DoS può essere risolto in modo molto più efficiente usando la randomizzazione hash, in modo che ogni esecuzione di i programmi o anche su ogni tabella hash, quindi i dati non ‘ vengono raggruppati nello stesso bucket ogni volta.

Utilizza SipHash . Ha molte proprietà desiderabili:

• Veloce. Unimplementazione ottimizzata richiede circa 1 ciclo per byte.

• Sicuro. SipHash è una potente PRF (funzione pseudocasuale). Ciò significa che non è distinguibile da una funzione casuale (a meno che non si conosca la chiave segreta a 128 bit). Quindi:

  • Non cè bisogno di preoccuparsi che le sonde della tabella hash diventino tempo lineare a causa delle collisioni. Con SipHash, sai che otterrai in media prestazioni del case nella media, indipendentemente dagli input.

  • Immunità agli attacchi denial of service basati su hash.

  • Puoi usare SipHash (specialmente la versione con output a 128 bit) come MAC (Codice di autenticazione del messaggio). Se ricevi un messaggio e un tag SipHash, e il tag è lo stesso dellesecuzione di SipHash con la tua chiave segreta, allora sai che chi ha creato lhash era anche in possesso della tua chiave segreta e che né il messaggio né il lhash è stato modificato da allora.

Commenti

• Isn ‘ t SipHash overkill a meno che tu non abbia bisogno di sicurezza? Richiede una chiave a 128 bit che è solo un seme hash glorificato. Per non parlare di MurmurHash3 ha unuscita a 128 bit e SipHash ha solo unuscita a 64 bit. Ovviamente il digest più grande ha una minore possibilità di collisione.
• @bryc La differenza è che SipHash continuerà a comportarsi bene, anche su input dannoso. Una tabella hash basata su SipHash può essere utilizzata per i dati provenienti da fonti potenzialmente ostili e può utilizzare un algoritmo come il sondaggio lineare che è molto sensibile ai dettagli della funzione hash.
• Siphash (e relativo prng più recente funzioni di stile) è la mia scelta predefinita per la sicurezza. Per le prestazioni, xxhash è difficile da battere. Ci sono un sacco di cattivi consigli sullhashing su Internet, anche nelle discussioni qui. Una buona prestazione su input casuali o semi casuali non ha senso. Qual è la prestazione peggiore, con input del mondo reale? Qual è il risultato con input dannosi? La tua tabella hash alla fine diventerà un vettore di attacco.

Dipende dai dati che stai sottoponendo a hashing. Alcuni hashing funzionano meglio con dati specifici come il testo. Alcuni algoritmi di hashing sono stati progettati specificatamente per essere utili per dati specifici.

Paul Hsieh una volta ha realizzato hash veloce . Elenca il codice sorgente e le spiegazioni. Ma era già stato battuto. 🙂

Java utilizza questa semplice moltiplicazione -e-aggiungi algoritmo:

Il codice hash per un oggetto String viene calcolato come

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

utilizzando int arithmetic, dove s[i] è il i ​ -esimo carattere della stringa, n è la lunghezza della stringa e ^ indica lelevamento a potenza. (Il valore hash della stringa vuota è zero.)

Probabilmente ce ne sono di molto migliori là fuori, ma questo è abbastanza diffuso e sembra essere un buon compromesso tra velocità e unicità.

Commenti

• Non ‘ utilizzerei esattamente lo stesso uno usato qui, poiché ‘ è ancora relativamente facile produrre collisioni con questo. ‘ decisamente non è terribile, ma ce ne sono di migliori là fuori. E se ‘ non ci sono ragioni significative per essere compatibile con Java, non dovrebbe essere scelto.
• Se scegli ancora questo per qualche motivo, potresti almeno usare un numero primo migliore come 92821 come moltiplicatore. Questo riduce molto le collisioni. stackoverflow.com/a/2816747/21499
• Potresti anche utilizzare FNV1a. ‘ è anche un semplice hash basato sulla moltiplicazione, ma utilizza un moltiplicatore più grande, che disperde lhash meglio.
• Non ‘ Non voglio s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Evita loperatore esperto (^) e fallo in questo modo: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Sì, nel codice è (e dovrebbe essere) fatto in modo iterativo, era semplicemente più facile da capire in una formula chiusa.

Prima di tutto, perché hai bisogno di implementare il tuo hashing? Per la maggior parte delle attività dovresti ottenere buoni risultati con strutture dati da una libreria standard, assumendo che sia disponibile unimplementazione (a meno che tu non lo stia facendo solo per la tua educazione).

Per quanto riguarda gli algoritmi di hashing effettivi, il mio preferito è FNV. 1

Ecco un esempio di implementazione della versione a 32 bit in 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; } 

Commenti

• La variante FNV-1a è leggermente migliore con la casualità. Scambia lordine dei * e ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619