On Tue, Nov 02, 2010 at 04:42:19PM -0400, Tom Lane wrote: > Robert Haas <robertmh...@gmail.com> writes: > > On Tue, Nov 2, 2010 at 11:21 AM, Tom Lane <t...@sss.pgh.pa.us> wrote: > >> Really? ?I think "I don't understand when this fails" isn't obviously > >> better than being able to predict when it fails ... > > > Isn't that the whole point of hash functions? Collisions are > > inevitable, but you want them to be unpredictable. If you want a hash > > function with predictable collision behavior, just has the first > > element. It'll be highly predictable AND wicked fast. > > That seems like a rather poor straw man, since it suffers from exactly > the defect I'm complaining about, namely failing to consider all the > input values equally. > > >> I'd be happier about this approach if there were some actual theory > >> behind it ... maybe there's some analysis out there, but the one link > >> that was given was just about entirely unconvincing. > > > I think it's from Knuth, though unfortunately I don't have a copy to > > check. There are probably better algorithms out there, but this one's > > pretty simple. > > I don't see anything in Knuth suggesting a multiplier of 31. His > recommendation for a multiplier, if you're going to use multiplicative > hashing, is wordsize/phi (phi being the golden ratio) ... and he also > wants you to keep the high order not the low order bits of the product. > > However, this is largely beside the point, because that theory, as well > as the Java code you're arguing from, has to do with the initial hashing > of a raw sequence of input items. Not with combining some existing hash > values. The rotate-and-xor method I suggested for that is borrowed > exactly from section 6.4 of Knuth (page 512, in the first edition of > volume 3). > > regards, tom lane >
Given that our hash implimentation mixes the input data well (It does. I tested it.) then a simple rotate-and-xor method is all that should be needed to maintain all of the needed information. The original hash function has done the heavy lifting in this case. Regards, Ken -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
