[boost] Re: [review] hash functions

From: Daniel James (daniel_at_[hidden])
Date: 2005-03-10 07:06:41

Peter Dimov wrote:
> Daniel James wrote:
>> Well, these two pages describe algorithms for hashing strings, which
>> apparently are faster with good (or better?) quality (I haven't tested
>> them yet):
>>
>> http://burtleburtle.net/bob/hash/doobs.html
>> http://www.azillionmonkeys.com/qed/hash.html
> 
> 
> These pages are good.
> 
> But as I said, benchmarking hash functions is pointless. Real programs 
> do not compute the hash value of a random 256 byte buffer five million 
> times. They usually need to do something with the hash value. This 
> something typically involves a division on a prime to obtain a modulus, 
> several pointer chasings, and at least one equality comparison (which on 
> a 256 byte buffer will have considerable impact).

Actually, that's one of the problems with them. They're designed to be 
used with hash tables that have a 2^n buckets (to avoid calculating the 
modulus), which isn't practical for a generic hash table that supports 
user supplied hash functions.

Daniel