Re: hashing

[antonio_duran@hotmail.com (Antonio Duran)]

"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.
> 
> I'm searching for a function just now, so this isn't laziness just wanted to
> utilise another resource (your brains) in case nothing turns up.  After the
> assignment submission in a few weeks, I'll tidy up the sources for all the
> useful adts I've written this term and GMGPL them (lists (singly, doubly),
> hash tables, and whatever else comes up) if ppl express an interest (all
> adts are generic so far).
> 
> 
> 
> Thanks,
> Chris
> 
> p.s. does anyone have any uses for circular lists?  Tom Swans Tp5.5 book
> mentions them, what are they used for?  Just curious...
> 
> 
> p.p.s. should performance/complexity information be included?  I seem to
> recall a conversation on this a while back, but can't remember if ppl
> thought it was a good idea.

I've found the hash function:

with Interfaces;

function    Hash(
               What        : in     String)
   return   Interfaces.Unsigned_32
is
   Hash_Code      : Interfaces.Unsigned_32 := 0;
begin
   for I in What'Range loop
      Hash_Code := (31 * Hash_Code) + 
                   Interfaces.Unsigned_32(Character'Pos(What(I)));
   end loop;

   return Hash_Code;
end Hash;

The returned value must be mod'ed by the number of buckets in your
hash table (that number should be a prime number).