hash algorithm for nginx cache

[Igor Sysoev]

On Wed, Apr 22, 2009 at 01:22:52AM +0200, Joe Bofh wrote:

> 
> FWIW, I got a follow up reply from Austin (the chap that created 
> murmurhash). He sez:
> 
> "MurmurHash2, MD5, Lookup3, and any cryptographic hash all have 
> statistically-correct collision behaviour - the average number of 
> collisions they create on a given keyset is the same as if the hash 
> function returned a totally random number. For comparison, FNV mixes 
> very poorly and tends to produce massively more collisions than expected 
> on "sparse" keys with only a few bits set, and SuperFastHash will tend 
> to produce a higher than expected number of collisions on keysets where 
> keys differ in only 2-3 bits - see 
> http://murmurhash.googlepages.com/statistics and the associated pages 
> for more info."
> 
> So it looks like collision-wise, it's comparable.

I'm not expert in cryptography, but it seems to me that 128-bit MD5
should have though not 2^64 times less collisions, but at least 10^9 times
less than any 64-bit hash.

> --J
> 
> 
> Johan Bergstr??m wrote:
> > Hey,
> > 
> > On Apr 21, 2009, at 17:46 , Joe Bofh wrote:
> > 
> >>
> >> I guess if you put in an option to specify the hash, that would work
> >> too. FNV and Murmur have been adopted on various open source  
> >> projects as
> >> optional hashs because of the hashing performance.
> > 
> > For reference; libmemcached - another high performing project -
> > nowadays include most current hashing algorithms. Fnv1a and murmur are
> > two of them. See: 
> > http://hg.tangent.org/libmemcached/file/048b32d9d1ae/docs/memcached_behavior.pod
> >   (sorry for bad linkage, the site docs/manpage hasn't been updated
> > for a while)
> > 
> > Two my knowledge, murmur/murmur2 is the best pick for a high
> > performance/low (but not zero) collision tradeoff.
> 
> -- 
> Posted via http://www.ruby-forum.com/.

-- 
Igor Sysoev
http://sysoev.ru/en/