Skip site navigation (1) Skip section navigation (2)

Re: Hash support for arrays

From: Sam Mason <sam(at)samason(dot)me(dot)uk>
To: pgsql-hackers(at)postgresql(dot)org
Subject: Re: Hash support for arrays
Date: 2010-11-02 21:26:22
Message-ID: 20101102212622.GE6225@samason.me.uk (view raw or flat)
Thread:
Lists: pgsql-hackers
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

pgsql-hackers by date

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

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group