On Sat, Oct 30, 2010 at 01:01:44PM -0400, Tom Lane wrote: > marcin mank <marcin.m...@gmail.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/ -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
