[htdig-dev] Questions about Dictionary::hashCode

[Neal R. <ne...@ri...>]

On Tue Feb 12 06:17:45 2002 Geoff committed a patch from Jamie Anstice
(SLI Systems).

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/htdig/htdig/htlib/Dictionary.cc

Jamie/Geoff:

  Could you give me a little background on this change?

  I'm wondering if we couldn't add a String to the Dictionary class and
use that instead of doing a malloc/strcpy everytime.. this function is
called jillions of times.

  I'm also curious as to why not use  Knuth's golden ratio hash function,
it's a well studied and known-good hash.

  I can make the change and test it.. I'm just curious about the rational
for both the origional hash function and the change.

Thanks!


/* Knuth's golden ratio hash function. key=word to hash on, kfl=length of
 * the word, bkts is number of buckets in hash table */
#define LONGMASK (~(1L << ((sizeof(long) * 8) - 1)))

// ----- vhhash1 ---------------------------------------------------------
static long
vhhash1(char *key, int kfl, long bkts)
{
    char *kptr;
    long lkey = 0L;
    double frac;

    kptr = key;
    while(kfl--) {
        lkey = ((lkey<<7)&~0x7fL) ^ ((lkey>>25)&0x7f) ^ ((long)*kptr++);
    }
    lkey &= LONGMASK;
    frac = 0.6180339887 * lkey;
    lkey = (long)frac;

    return((long) ((frac-lkey) * bkts));
}




Neal Richter
Knowledgebase Developer
RightNow Technologies, Inc.
Customer Service for Every Web Site
Office: 406-522-1485