On Sat, Oct 30, 2010 at 01:01:44PM -0400, Tom Lane wrote:
> marcin mank <marcin(dot)mank(at)gmail(dot)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/

In response to

• Re: Hash support for arrays at 2010-10-30 17:01:44 from Tom Lane

pgsql-hackers by date

Next:	From: Robert Haas	Date: 2010-11-02 21:28:01
	Subject: Re: Hash support for arrays
Previous:	From: Kenneth Marshall	Date: 2010-11-02 20:46:18
	Subject: Re: Hash support for arrays