Кой алгоритъм за хеширане е най-добрият за уникалност и скорост? Примерни (добри) употреби включват хеш речници.
Знам, че има неща като SHA-256 и подобни, но тези алгоритми са предназначени да бъдат сигурни, което обикновено означава, че са по-бавни от алгоритмите, които са по-малко уникални. Искам алгоритъм за хеширане, проектиран да бъде бърз, но да остане доста уникален, за да се избегнат колизии.
Тук е списък с хеш функции, но кратката версия е:
Ако просто искате да имате добра хеш функция и не можете да чакате,
djb2
е една от най-добрите функции за хеширане на низове, които познавам. Тя има отлично разпределение и скорост при много различни набори от ключове и размери на таблицата
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 (включително SHA-256) са предназначени да бъдат бързи.
Всъщност тяхната скорост понякога може да бъде проблем. По-специално, често срещана техника за съхраняване на жетон, получен от парола, е стандартният бърз алгоритъм за хеширане да се изпълнява 10 000 пъти (съхранявайки хеша на хеша на хеша на хеша на ... паролата).
#!/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
Изход:
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 използва този прост алгоритъм за умножение и добавяне:
Хеш кодът за обект String се изчислява по следния начин
s[0]31^(n-1) + s131^(n-2) + ... + s[n-1]
като се използва аритметиката int, където
s[i]
е i-тият символ на низа,n
е дължината на низа, а^
означава експоненция. (Хеш-стойността на празния низ е нула.)
Вероятно има и много по-добри, но тази е доста разпространена и изглежда е добър компромис между бързина и уникалност.