Hvilken hashingalgoritme er best for entydighet og hastighet? Eksempler på (gode) bruksområder inkluderer hash-ordbøker.
Jeg vet at det finnes ting som SHA-256 og slikt, men disse algoritmene er designet for å være sikre, noe som vanligvis betyr at de er tregere enn algoritmer som er mindre unike. Jeg vil ha en hash-algoritme designet for å være rask, men likevel være ganske unik for å unngå kollisjoner.
Her er en liste over hashfunksjoner, men kortversjonen er:
Hvis du bare vil ha en god hash-funksjon, og ikke kan vente, er
djb2
en av de beste streng-hash-funksjonene jeg kjenner. Den har utmerket distribusjon og hastighet på mange forskjellige sett med nøkler og tabellstø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;
}
SHA-algoritmene (inkludert SHA-256) er designet for å være raske.
Faktisk kan hastigheten deres noen ganger være et problem. Spesielt er en vanlig teknikk for lagring av et passordavledet token å kjøre en standard rask hash-algoritme 10 000 ganger (lagring av hash av hash av hash av hash av ... passord).
#!/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 bruker denne enkle multipliser-og-adder-algoritmen:
Hash-koden for et String-objekt beregnes slik
s[0] 31^(n-1) + s1 31^(n-2) + ... + s[n-1]
ved hjelp av int-aritmetikk, der
s[i]
er det i-te tegnet i strengen,n
er lengden på strengen, og^
angir eksponentiering. (Hashverdien til den tomme strengen er null).
Det finnes sannsynligvis mye bedre der ute, men dette er ganske utbredt og ser ut til å være en god avveining mellom hastighet og entydighet.