This would probably have a little better distribution characteristics,
especially for short strings and run at a comparable speed to what I
proposed. I like the LittleEndian tweak for cross-platform compatibility,
and I was unaware that Bitwise offered a ShiftLeft method -- nice to know.
I don't see that using "prime numbers" here as opposed to just "moderate
size numbers" really gains you anything of consequence, but combining that
with the Mod 65521 gets you the better distribution for small strings.
So, yeah. I could live with this just fine if coded in C.
On 11/30/05 8:38 PM, "Phil M" <phil at mobleybros dot com> wrote:
> On Nov 30, 2005, at 4:54 PM, Roph wrote:
>
>> 1) I realized there's a bug in this since MidB returns a character,
>> not an
>> integer. The line showing:
>
> I don't know how good this is speed wise or with collisions, but I
> would do something like the function below (but I am no hash
> expert). It seems rather fast in my tests except when you get into
> long strings... I am not sure where the break-point is, but running
> MD5 on a long string first (and then hashing the hash) seems to work
> almost as fast as short strings.
I really don't know what MD5 does internally, but based on the interface
spec for it, I'd find that very surprising if true.
>
> I think I am using REALbasic 2005 only features with the MemoryBlock,
> or at least 5.5.4 is required. Yes, you pass in any string to this
> function and the string gets automatically converted to the MemoryBlock.
>
I've used RB-written hashes like these for years. Now I'm working on an app
however where I want sheer absolute speed wherever I can get it -- and a
C-coded hash function is high on my wish list.
> Protected Function StringHash(s As MemoryBlock) As Integer
>
> Dim a, b, k, kMax As Integer
>
> kMax = Ceil(s.Size / 2) * 2 // Round up to nearest 2-byte block
> a = 42487 // start with a decent prime number
> b = 11953 // start with a decent prime number
>
> s.LittleEndian = False // make hash cross-platform
> compatible
> s.Size = kMax // make MemoryBlock 2-byte friendly
>
> #pragma DisableBackgroundTasks
> While k < kMax
> a = (a + s.UShort(k)) Mod 65521
> b = (b + a) Mod 65521
> k = k + 2
> Wend
>
> Return Bitwise.BitOr(Bitwise.ShiftLeft(b, 16), a)
>
> End Function
>
> _______________________________________________
> 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>
_______________________________________________
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>
|