Does anyone have some sourcecode for a 32-bit hash generator for strings? Thomas
Here is a simple hash function (i found it in sgi's stl).
HashString PROC USES esi ebx, lpString : DWORD mov esi, lpString xor eax, eax movzx ebx, BYTE PTR .WHILE ( ebx ) imul eax, 5 add eax, ebx inc esi movzx ebx, BYTE PTR .ENDW ret HashString ENDP
this is the same, but faster..
HashString PROC lpString : DWORD push esi xor eax, eax xor ecx, ecx mov esi, lpString Next: mov cl, lea eax, inc esi add eax, ecx test ecx,ecx jne Next pop esi ret HashString ENDP
Just out of interest, what is a 'Hashing' function?
Hashing functions like this are used as Key's to higher organisation of data. The Function itself simply converts the a string into a number that is unique to the information in the string. (ID if you will) The number doesn't have to be truely unique, it is possible for two different Strings will generate a same #. The hash-key id # is used in 'Hash tables' which is a table of pointers, that is directly referenced by the ID # generated by a string. This makes finding data VERY fast when you have 1000's of entries to sort through, because you dont! The key points straight to it in the hash table, and at that location has a pointer to the memory you were looking for! I mentioned earlier it is possible for 2 different strings to point to generate the same hash table offset. This means that its possible to get the Wrong data back!! To resolve this problem, progammers tipically have every valid hast table location point to a Linked List (rather than directly to your data). Once the search is narrowed down to a list of 1-5 possiblities, you simple parse though the links till you match the string your were looking for, and hence your data!! This sounds like a lot of cpu work (and coding), but it is really quite efficient when dealing with HUGE amounts of data! Like your phone book! Take a persons name and make a hask key out of it, then parse through a 1-100 links at best and you got your guy's phone #!. This beats searching 300 000 + people in one go sequentially! Anywho, thats it in a nut shell. Now that i got my Object Creator tool going good, i might build a hash-table class sometime soon, but still got a few projects going first :) Hope this helps. NaN