hash algorithm for nginx cache
is at rambler-co.ru
Wed Apr 22 15:07:48 MSD 2009
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.
> 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/.
More information about the nginx