On Sat, Oct 30, 2010 at 01:01:44PM -0400, Tom Lane wrote:
> marcin mank <marcin.mank@gmail.com> writes:
> > This is what boost does:
> > http://www.systomath.com/include/Boost-1_34/doc/html/boost/hash_combine.html
>
> Hmm. I am reminded of Knuth's famous dictum: "never generate random
> numbers with a method chosen at random". Is there any actual theory
> behind that algorithm, and if so what is it? The combination of
> shifting with addition (not xor) seems more likely to lead to weird
> cancellations than any improvement in the hash behavior.
As far as I can tell the boost combiner comes from:
http://goanna.cs.rmit.edu.au/~jz/fulltext/jasist-tch.pdf
Which seems to be solving a completely different problem and I can't see
how relevant it is to the design of a hash combiner. The fact that they
get trivial details wrong like 32bit integers going up to 2^32 rather
than 2^32-1 doesn't inspire confidence.
One subtle point I noticed on the boost mailing list was that they
didn't want [[1],2] hashing to the same value as [1,2]. I'm pretty sure
that this sort of construction isn't possible to express in PG, but
thought I should mention it just in case.
-- Sam http://samason.me.uk/