[Python-3000] Performance Notes - new hash algorithm

[Larry Hastings]

If the Python community is just noticing the Hsieh hash, that implies 
that the Bob Jenkins hashes are probably unknown as well.  Behold:
    http://burtleburtle.net/bob/hash/doobs.html
To save you a little head-scratching, the functions you want to play 
with are hashlittle()/hashlittle2() in "lookup3.c":
    http://burtleburtle.net/bob/c/lookup3.c
hashlittle() returns a 32-bit hash; hashlittle2() returns two 32-bit 
hashes on the same input (in effect a 64-bit hash).  The "little" 
implies that the function is better on little-endian machines.  (There 
is a hashbig(); no hashbig2(), it is left as an exercise for the reader.)

In our testing (at Facebook, for memcached) hashlittle2 was faster than 
the Hsieh hash; that was done a year ago (and before I joined) so I 
don't have numbers for you.

One goal of Jenkin's hashes is uniform distribution, so these functions 
presumably lack the serendipitous "similar inputs hash to similar 
values" behavior of Python's current hash function.  But why is that a 
feature?  (Not that I doubt Tim Peters!)

Oh, and, all the Jenkins code is public domain. 

Cheers,


/larry/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/python-3000/attachments/20070908/a49272fd/attachment.htm