Welk hashing-algoritme is het beste voor uniciteit en snelheid? Voorbeeldige (goede) toepassingen zijn hashwoordenboeken.
Ik weet dat er dingen zijn als SHA-256 en dergelijke, maar deze algoritmen zijn ontworpen om veilig te zijn, wat meestal betekent dat ze langzamer zijn dan algoritmen die minder uniek zijn. Ik wil een hash-algoritme dat ontworpen is om snel te zijn, maar toch redelijk uniek te blijven om botsingen te vermijden.
Hier is een lijst van hash functies, maar de korte versie is:
Als je gewoon een goede hash-functie wilt hebben, en niet kunt wachten,
djb2
is een van de beste string hash-functies die ik ken. Het heeft een uitstekende distributie en snelheid op veel verschillende sets van sleutels en tabelgroottes
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;
}
De SHA-algoritmen (waaronder SHA-256) zijn ontworpen om snel te zijn.
In feite kan hun snelheid soms een probleem zijn. In het bijzonder is een veelgebruikte techniek voor het opslaan van een wachtwoord-afgeleid token het 10.000 keer uitvoeren van een standaard snel hash-algoritme (waarbij de hash van de hash van de hash van de hash van het ... wachtwoord wordt opgeslagen).
#!/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
Uitvoer:
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 gebruikt dit eenvoudig vermenigvuldigings-en-toevoeg algoritme:
De hash code voor een String object wordt berekend als
s[0]31^(n-1) + s131^(n-2) + ... + s[n-1]
met behulp van int aritmetiek, waarbij
s[i]
het i-ste karakter van de string is,n
de lengte van de string is, en^
exponentiëring aangeeft. (De hash waarde van de lege string is nul).
Er zijn waarschijnlijk veel betere, maar dit is redelijk wijdverbreid en lijkt een goede afweging te zijn tussen snelheid en uniciteit.