use better hash function (FNV-1a)

git-svn-id: file:///svnroot/lcore/trunk@143 b1de8a11-f9be-4011-bde0-cc7ace90066a

diff --git a/bsearchtree.pas b/bsearchtree.pas
index 9dc355e08a1b389575789363052d607393df5519..9ec804c750edae6740653c11364ba1a17c04dd7e 100644 (file)
--- a/bsearchtree.pas
+++ b/bsearchtree.pas
@@ -37,18 +37,21 @@ procedure cleartree(t:phashtable);
 \r
 implementation\r
 \r
 \r
 implementation\r
 \r

+//FNV-1a hash function\r

 function makehash(s:ansistring):integer;\r
 const\r
   shifter=6;\r
 var\r
   a,b:integer;\r
 function makehash(s:ansistring):integer;\r
 const\r
   shifter=6;\r
 var\r
   a,b:integer;\r

+  h:longword;\r

 begin\r
   result := 0;\r
   b := length(s);\r
 begin\r
   result := 0;\r
   b := length(s);\r

+  h := 216613626;\r

   for a := 1 to b do begin\r
   for a := 1 to b do begin\r

-    result := (result shl shifter) xor byte(s[a]);\r
+    h := (h xor byte(s[a])) * 16777619;\r

   end;\r
   end;\r

-  result := (result xor result shr 16) and (hashtable_size-1);\r
+  result := h and (hashtable_size-1);\r

 end;\r
 \r
 procedure addtree(t:phashtable;s:ansistring;item:pointer);\r
 end;\r
 \r
 procedure addtree(t:phashtable;s:ansistring;item:pointer);\r