🚀 go-pugleaf

In article <19990716.193917.0AA80202.XVaa@pierrot.co.uk>,
Terrance Richard Boyes <tez@pierrot.co.uk> wrote:
> Jim Segrave <jes@nl.demon.net> wrote:
> 
> [snip]
> 
> > I did some experiments when this first went into ka9q and found (in
> > live testing) that using two smaller tables with two different hash
> > generators worked better than one larger table. You hash the ID two
> > different ways and only if both get a hit do you search the history
> > file. I seem to recall (though it's been a *long* time since I looked
> > at the code), that the Demon customer who added the hashing adopted my
> > suggestion.
> 
> Yep, there's a HASH1 and HASH2 value, though there seem to be
> some problems if both of those overflow (collisions). I couldn't
> find my refs to how to understand the numbers behind a hashing
> algorithm. Any good books ?

The ultimate reference:

D. E. Knuth's The Art of Computer Programming. I think it's in volume
3 - Sorting and Searching, but it might be in SemiNuerical Algorithms
(vol. 1 as I recall).

The DOS version was memory limited and the tradeoff was to search the
file if both hashes of the message ID were in the table, otherwise it
was guaranteed it was a new article. 
 
> However with a bit of experimentation I upped both the HASH values
> from ~32K to ~256K, on 32K unique msgids this has dropped the
> collisions from ~5000 to ~700.