Re: hashing

[Jeffrey Carter <jrcarter@acm.org>]

Antonio Duran wrote:
> 
> "chris.danx" <chris.danx@ntlworld.com> wrote in message news:<1b2t8.507$na.19833@news8-gui.server.ntli.net>...
> > Hi,
> >
> > Does anyone have a good hash function for strings (length is arbitary,
> > number of buckets is determined when package is instantiated and collisions
> > are handled with chaining)?  I'm new to writing hash tables and functions
> > (used them in libs, but this has to be all my own work!), and have chosen
> > this technique to implement in an assignment -- had enough linked lists, and
> > want to expand my horizons.

You might want to look at P. K. Pearson, "Fast Hashing of
Variable-Length Text Strings," Comm. ACM, 1990 Jun. It's a fast "hashing
function specifically tailored to variable-length text strings."
"Similar strings are not likely to collide." It produces an unsigned
8-bit value for the hash.

An implementation is available as part of the PragmAda Reusable
Components, available from

http://home.earthlink.net/~jrcarter010/pragmarc.htm

and the mirror at www.adapower.com. Look for
PragmARC.Hash_Fast_Variable_Length.

-- 
Jeff Carter
"You empty-headed animal-food-trough wiper."
Monty Python & the Holy Grail