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

Subject: [boost] [hash] regular behaviour of hash function for double values
From: Kai Schroeder (kaischroeder3_at_[hidden])
Date: 2012-01-31 10:10:50

Hi,

the following code:

double fStart = 31337;
double fEnd   = 65536;
double fStep  = fStart - fEnd;
fStep /= 512;
for (int i = 0; i < 512; i++)
{
      std::cout << std::hex <<  boost::hash<double>()(fStart + i *
fStep) << std::endl;
}

leads to the output of surprisingly regular hash values (see end of
mail). This seems to occur mainly if a power of two number of points
is sampled equidistantly within an interval.

Especially since some hash table implementations (e.g. intel's
threading building blocks) only use the last few bits to determine the
bucket, this can lead to very bad caching behaviour for the rather
common case of regularly sampled points (equidistant samplings of
power of 2 are e.g. common in computer graphics and numerical
algorithms).

Are you aware of this? Would you consider it a bug?

Best regards,
Kai Schroeder

Output of code using Boost 1.48 (similar behaviour can be observed for
other start and end values and other power of 2 step counts):

ff9f20000000000f
e5042f900000000f
52f13f200000000f
297ac8b00000000f
48721e400000000f
2f9b8dd00000000f
3df0b1600000000f
d19cf2f00000000f
9201c800000000f
9409aa100000000f
7cb3fba00000000f
d7a42b300000000f
b15982c00000000f
5f7900500000000f
e0ba85e00000000f
255ee5700000000f
cec119000000000f
955bd6900000000f
6a58f4200000000f
843a37b00000000f
590797400000000f
7e8db4d00000000f
1721b6600000000f
37acf9f00000000f
df5f65800000000f
88b1a5100000000f
494a0a00000000f
bb1082300000000f
1ea62bc00000000f
...