hash algorithm for nginx cache
lists at ruby-forum.com
Wed Apr 22 03:22:52 MSD 2009
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.
Johan Bergström wrote:
> 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:
> (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