I wrote a hash function for my case-sensitive dictionary using a
standard algorithm lifted from Sedgewick's "Algorithms in C++". Here is
a version of it.
Function Hash(s as String) as Integer
#pragma DisableBackgroundTasks
Static HashBlock as new MemoryBlock(256)
If HashBlock.Size < LenB(s) then
HashBlock.Size = 2*HashBlock.Size
End if
HashBlock.StringValue(0, LenB(s)) = s
dim N as Integer = LenB(s) - 1
dim theHash as Integer
For i as Integer = 0 to N
theHash = theHash*256 + me.hashBlock.Byte(i)
Next
Return theHash
End Function
Assuming that you use a hash table whose size is prime (see Sedgewick
for a table of sizes), it works pretty well. Obviously a C
implementation could be much faster.
Charles Yeomans
On Nov 30, 2005, at 4:42 PM, Roph wrote:
I virtually never use the RB dictionary. The Einhugur ObjectDictionary
class offers an excellent, high-performance solution for needs of this
sort.
What I find almost amusing is that as far as I can tell, there no
available
fast, case-sensitive hash function for building your own
Dictionary-type
structure available from RB, Einhugur, MBS, or anyone else that I've
discovered yet. Bjorn has noted that the ObjectDictionary class
clearly has
an internal implementation of such an algorithm and suggested that he
might
make it accessible in its as-is form ... which would be great.
It is less likely that you can get collisons with Base64, but the
Base64 encoding still depends on case-sensitivity. If you want to
use the standard REALbasic Dictionary, then you are going to need to
either Base32 the string or Hex it.
_______________________________________________
Unsubscribe or switch delivery mode:
<http://www.realsoftware.com/support/listmanager/>
Search the archives of this list here:
<http://support.realsoftware.com/listarchives/lists.html>
|