Boost logo

Boost :

Subject: Re: [boost] [functional/hash] integer hash function
From: Peter Dimov (pdimov_at_[hidden])
Date: 2011-10-05 06:32:53

Christopher Jefferson wrote:

> A default hash function certainly can shuffle bits, to create a better
> distribution.

What does "better distribution" mean?

> It might still be worth documenting this weakness however.

This is not a weakness. The definition of a hash function is that equal
inputs produce the same output and different inputs should produce different
outputs. This is exactly what this function does. If an algorithm doesn't
work well with this hash function, this is a sign that the algorithm itself
has a weakness, because it doesn't work well with functions that satisfy the
requirements for a hash function. In other words, the algorithm places
additional requirements on its hash function, requirements that a hash
function author has no way of knowing.

Now, to be honest, I know what the perceived defect is, that the default
hash function is not cryptographic enough. In particular, that a single bit
change in the input results in a predictable single bit change in the
output, whereas one would like it to result in random bit changes all over
the size_t. But, again, if your algorithm requires this property, it is not
generic and will not necessarily work with a hash function written by
someone who is not aware of this requirement. If you require the output bits
to be properly shuffled, do that yourself, this is something that all hash
functions may potentially need.

Which is basically what you said. :-)

> I would say not, as it is simple to add once a shuffle/distribution
> function, which can be applied to the hash, if the user wants one.

Boost list run by bdawes at, gregod at, cpdaniel at, john at