Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.c
Subject: Re: Hash??? What ARE the latest hot-shot methods?
Message-ID: <6429:Dec500:37:2890@kramden.acf.nyu.edu>
Date: 5 Dec 90 00:37:28 GMT
References: <9012031446.AA24102@bisco.kodak.COM> <22533:Dec321:54:4390@kramden.acf.nyu.edu> <1990Dec4.142017.12806@batcomputer.tn.cornell.edu>
Organization: IR
Lines: 16

In article <1990Dec4.142017.12806@batcomputer.tn.cornell.edu> lynch@batcomputer.tn.cornell.edu (Tim Lynch) writes:
> Thanks for the reference.  Can someone recommend a book that does go into
> all the latest "hot-shot" methods?

Have there been any fundamentally new hashing methods in the last twenty
years? The only one I know of is Pearson's.

What are you really looking for? There are lots of string functions that
are both fast and, in practice, better than random hashing. These days I
start from h = 5381, and set h = h << 5 + h + c mod any power of 2 for
each new character c. Apparently Chris Torek prefers a multiplier of 31:
h << 5 - h + c. These are reliable and extremely fast. You can make them
even faster if you want to hash an entire string at once: just
precompute powers of 31 or 33, etc.

---Dan


Brought to you by Super Global Mega Corp .com