Re: Pseudo-random numbers and hash code (Was: Using a lot of Maps)

From:

Tom Anderson <twic@urchin.earth.li>

Newsgroups:

comp.lang.java.programmer

Date:

Wed, 24 Nov 2010 21:18:47 +0000

Message-ID:

<alpine.DEB.1.10.1011242058240.15425@urchin.earth.li>

On Wed, 24 Nov 2010, Arne Vajh?j wrote:

On 24-11-2010 00:30, Lew wrote:

markspace wrote:

31, 33, 35, 51, 53, 55, etc. all work pretty much the same, and
generate slightly different hash codes, meaning the chance of
collision is reduced if you use different constants once in a while.

Thus I conclude that your advice is sound, though by preference I will
use a prime coefficient, and that will be 31 for 32-bit hashes at least
until I've done the research again.

It is not obvious to me that coefficients that gives long cycles for
LCG's also give good distribution for hashes.

The whole discussion seems of academic interest to me (which is certainly
not to say it is of no interest!) - there are a number of hashes which are
faster and better-distributed than any multiply-and-add hash. Read these:

http://www.strchr.com/hash_functions
http://www.team5150.com/~andrew/noncryptohashzoo/

Implement this:

http://code.google.com/p/smhasher/wiki/MurmurHash3

tom

--
Verbing weirds language.