Re: Hash specifics

> 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]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.