Quale algoritmo di hashing è il migliore per l'unicità e la velocità? Esempi (buoni) di utilizzo includono i dizionari di hash.
So che ci sono cose come SHA-256 e simili, ma questi algoritmi sono progettati per essere sicuri, il che di solito significa che sono più lenti di algoritmi che sono meno unici. Voglio un algoritmo di hash progettato per essere veloce, ma rimanere abbastanza unico per evitare collisioni.
Qui è una lista di funzioni hash, ma la versione breve è:
Se vuoi solo avere una buona funzione hash e non puoi aspettare, djb2
è una delle migliori funzioni hash di stringa che conosco. Ha un'eccellente distribuzione e velocità su molti insiemi diversi di chiavi e dimensioni della 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;
}
Gli algoritmi SHA (compreso SHA-256) sono progettati per essere veloci.
Infatti, la loro velocità può essere un problema a volte. In particolare, una tecnica comune per memorizzare un token derivato da una password è quella di eseguire un algoritmo di hash veloce standard 10.000 volte (memorizzando l'hash dell'hash dell'hash dell'hash 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
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)
Java usa questo un semplice algoritmo di moltiplicazione e aggiunta: Il codice hash per un oggetto String è calcolato come s[0]31^(n-1) + s131^(n-1); s[0]31^(n-1) + s131^(n-2) + ... + s[n-1]
usando l'aritmetica int, dove
s[i]
è il i-esimo carattere della stringa,n
è la lunghezza della stringa, e^
indica l'esponenziazione. (Il valore di 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à.