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

Re: Hash support for arrays

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: marcin mank <marcin(dot)mank(at)gmail(dot)com>
Cc: pgsql-hackers(at)postgresql(dot)org
Subject: Re: Hash support for arrays
Date: 2010-10-30 17:01:44
Message-ID: 6367.1288458104@sss.pgh.pa.us (view raw or flat)
Thread:
Lists: pgsql-hackers
marcin mank <marcin(dot)mank(at)gmail(dot)com> writes:
> On Sat, Oct 30, 2010 at 6:21 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> 3. To hash, apply the element type's hash function to each array
>> element. Combine these values by rotating the accumulator left
>> one bit at each step and xor'ing in the next element's hash value.
>> 
>> Thoughts? In particular, is anyone aware of a better method
>> for combining the element hash values?

> This would make the hash the same for arrays with elements 32 apart swapped.

Well, there are *always* going to be cases where you get the same hash
value for two different inputs; it's unavoidable given that you have to
combine N 32-bit hash values into only one 32-bit output.

> 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.

			regards, tom lane

In response to

Responses

pgsql-hackers by date

Next:From: Greg StarkDate: 2010-10-30 19:14:44
Subject: Re: Hash support for arrays
Previous:From: marcin mankDate: 2010-10-30 16:45:57
Subject: Re: Hash support for arrays

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