Path: utzoo!attcan!uunet!snorkelwacker.mit.edu!mintaka!spdcc!iecc!compilers-sender
From: chased@Eng.Sun.COM (David Chase)
Newsgroups: comp.compilers
Subject: Re: Hash specifics
Keywords: design
Message-ID: <9012112133.AA00452@rbbb.Eng.Sun.COM>
Date: 11 Dec 90 21:33:07 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: chased@Eng.Sun.COM (David Chase)
Organization: Compilers Central
Lines: 32
Approved: compilers@iecc.cambridge.ma.us

> If someone has a breakthrough in perfect hashing to report, I'd love to
> hear about it.

CACM 33:6 (June 1990) "Fast Hashing of Variable Length Strings"
by Peter K. Pearson.

He discusses use of hash functions of the form:

  h = 0;
  n = length(string);

  for i = 1 through n do
    h = Table [ h XOR string [i]];
  enddo;

  return h;

where Table is a 256-byte array.  Each character in the string hashed
costs an XOR operation and an indexed read from memory (above the costs
of reading the character).  This function can "sometimes be modified to
produce a minimal perfect hashing function over a modest list of
words."

It's worth a look; I found it to be pleasant reading.

David Chase
Sun Microsystems
[It's a cute hack.  I note that he references the 1977 and 1980 articles
listed in my previous article, nothing else since then. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.