🚀 go-pugleaf

In article <19990714.205259.0AA80202.Tuaa@pierrot.co.uk>,
Terrance Richard Boyes <tez@pierrot.co.uk> wrote:
> Nikki Locke <nikki@trmphrst.demon.co.uk> wrote:
> > The efficiency of the hash table depends heavily on the suitability of 
> > the initial hashing algorithm - if the ID's all hash to different 
> > numbers, it is very fast. If they all hash to the same number, it is as 
> > slow as a linear search.
> 
> One problem with message-ids is how to hash them uniquely, they
> tend to be relatively large, so any prime-multiplication
> type method would result in huge numbers. I did a few experiments
> last night with simple things like adding up all the ASCII values
> (and a variant splitting the message-id into <lhs@rhs>) and
> there is a lot of overflow.

I'd recommend algorithms designed to randomise. CRC's are good ones
(in another post here I suggested two smaller hash tables rather than
one big one), so simply choosing two different CRC polynomials is
effective. If you've got more compute power, then an MD5 digest is a
potent way of spreading Id's across a range. In either the CRC or MD5
case, simply take as many bits as you want from either the front or
the back of the result.