marcin mank <marcin.m...@gmail.com> writes: > On Sat, Oct 30, 2010 at 6:21 PM, Tom Lane <t...@sss.pgh.pa.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
