Re: [boost] [hash] regular behaviour of hash function for double values

Subject: Re: [boost] [hash] regular behaviour of hash function for double values
From: Topher Cooper (topher_at_[hidden])
Date: 2012-01-31 19:44:57

On 1/31/2012 1:55 PM, Daniel James wrote:
> The requirements for the hash function are:
>
> For two different values
> t1 and t2, the probability that h(t1) and h(t2) compare
> equal should be very small, approaching 1.0 / numeric_
> limits<size_t>::max().
>
> There's no requirement about how h(t1) and h(t2) are distributed so it
> must be the container's responsibility, since the container must work
> well with any hash function that meets these requirements. How else
> can you interpret it?
>    
As what it says.

It does not say anything about the distribution from which the two 
different values are drawn so the implication is that for /any /two 
values the probability must approach 1/max-value.  Technically, of 
course, this is impossible -- you can always choose the values from a 
distribution based on inverting the hash (that this might be extremely 
costly or even infeasible is irrelevant).  A reasonable view, however, 
is that if the values are chosen using any reasonable method that is not 
too specific to the particular hash method then the probability of a 
collision is as stated.  Any simple pattern in the input that results in 
a pattern in the output -- a restriction over the possible range of 
output values for meaningful subsets of all possible values -- will 
produce collision probabilities much higher than that.

If we do not read it that way -- if we take "two different values" to 
mean "two values uniformly selected from all possible input values" -- 
then the requirement is trivial.  For any kind of value that is 
represented in log-2(numeric_limits<size_t>::max()) bits or less, just 
use the identity function, for anything larger, just use the first 
bits-per-size_t-value bits and throw out the rest.  That is all it takes 
to conform to the standard by that reading.

But even if this was not the case and this hash function can be taken to 
conform to the standard --

There is no explicit requirement for quality anywhere in the standards 
to the best of my knowledge.  For example, a linear asymptotic 
performance requirement does not /specify/ that the there isn't a two 
minute overhead independent of N for each operation -- avoiding that in 
an implementation is about /quality/ rather than /conformance/.  You can 
consider it to be an accurate implementation of the standard but you 
can't consider it a good one.

There are specialized applications where a poorly distributed hash (at 
least poorly distributed in just the right way) is not only acceptable 
but required.  Sometimes you want to ignore some specific differences so 
that values that differ only by those characteristics still hash to the 
same value (obvious example -- case-insensitive string hashes).  When 
hashing is used to locate similar objects the hash function must 
transform values that differ in small ways -- that are similar -- to 
hash values close to each other.  The classic Gorin spelling correction 
algorithm hashed each word from a document by its length and first two 
letters allowing any word with a single letter insertion, deletion or 
replacement or a two letter transposition to be easily found, and there 
are lots of geometric algorithms that reduce dimensionality or range in 
a desirable way so that "close" points are still close, or at least 
likely to be.

But there are a number of characteristics that are routinely considered 
the characteristics of a /general purpose/ hash function of at least 
moderate quality and the avoidance of this kind of regularity is one of 
them.

The suggestion that the output could be fixed by adding a "bit mixing 
function" is not really relevant, and neither is the statement that 
because the standard does not specify a good quality hash that it is the 
container's responsibility to "fix it".  The only way for the container 
to do that is to rehash the hash value -- which is essentially what the 
bit-mixing function does (such a function would be a not-terrible hash 
function for fixed width values for many purposes -- as long as input 
and output having the same number of 1-bits is not a problem.  Note, 
however, that the specific example that demonstrated the problem 
produced lots of bits the same, which would still reduce the number of 
possible values for structured inputs however much the bits were 
shuffled around).

To specify that a hash-based algorithm should  be written to be proof 
against poorly distributed inputs essentially means that the expectation 
is that the input hash value should be rehashed.  Of course, its 
standard for have hash tables to have prime-like lengths (generally 
taken to mean to avoid lengths with small -- especially powers of 2 -- 
divisors) but that has to do with the quality of the necessary range 
reduction (a.k.a., value folding).  This is generally considered good 
enough precaution to allow "raw integer values" to be used directly for 
many applications, but for less casual use, this is not acceptable 
(values that differ by the table size end up in the same bin, and values 
that differ by a small amount end up in nearby bins -- which can cause 
excess collisions for data with some corelational structure).

Lets turn one of the arguments made on its head.  Why should someone who 
finds it convenient to use a reasonable quality hash on their data type 
pay the overhead of using a container that compensates for the 
possibility of a poor one?  Is it a more reasonable expectation that 
someone who wishes a different balance of quality vs performance then 
the default should rewrite the standard hash or rewrite the standard 
unordered_map?

Sorry for the length -- I had a lot to say, I guess.

Topher Cooper