Re: Hash support for arrays

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Nov 2, 2010, at 1:42 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> 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).

> It seems undesirable to me to have a situation where transposing two array elements doesn't change the hash value. But I just work here.

[ shrug... ] There are always going to be collisions, and you're
overstating the importance of this one (only some transpositions will
result in a duplicate hash, not any transposition).

What's actually *important*, for our purposes, is that all bits of the
final hash value depend in a reasonably uniform way on all bits of the
input hash values. If we don't have that property, then bucket numbers
(which we form by taking the low-order N bits of the final hash, where
N isn't known in advance) won't be as well distributed as we'd like.

It's possible that the multiply-by-31 method is as good as the
rotate-and-xor method by that measure, or even better; but it's far from
obvious that it's better. And I'm not convinced that the multiply
method has a pedigree that should encourage me to take it on faith.

regards, tom lane