Re: [boost] Re: [review] hash functions

From: Dave Harris (brangdon_at_[hidden])
Date: 2005-03-15 11:20:14

In-Reply-To: <018201c52567$1b710ca0$6601a8c0_at_pdimov>
pdimov_at_[hidden] (Peter Dimov) wrote (abridged):
> 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).

I'd add that my own application caches the results of the hash at highish 
level, so it doesn't actually matter that much if it is slow.

The equality comparison is only needed if the hashes are equal. If you are 
doing something like adding values to a set, and all the values are in 
fact different, then hopefully the hashes will be different and the 
equality tests never needed.

In my own code I use a mixture of hashing and interning. This means that 
if objects are equal they probably have the same address. If they are 
different they probably have different (cached) hashes. Full byte-by-byte 
compares of all the data are rarely needed.

-- Dave Harris, Nottingham, UK