|
From: Neal R. <ne...@ri...> - 2003-02-01 00:27:12
|
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 |