Re: Hash support for arrays

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