WoW:USERAPI StringHash: Difference between revisions
Jump to navigation
Jump to search
StringHash - by Template:User -
(→Code: W/ the 2.0 changes, lua 5.1 renamed math.mod to math.fmod) |
No edit summary |
||
| Line 5: | Line 5: | ||
Return a fair-quality 32-bit hash of a string | Return a fair-quality 32-bit hash of a string | ||
hashVal = | hashVal = StringHash("string") | ||
== Example == | == Example == | ||
> print( | > print(StringHash("")) | ||
1 | 1 | ||
> print( | > print(StringHash("ab")) | ||
3458343178 | 3458343178 | ||
> print( | > print(StringHash("ba")) | ||
3466747145 | 3466747145 | ||
> print( | > print(StringHash("AB")) | ||
2653593770 | 2653593770 | ||
> print( | > print(StringHash("BA")) | ||
2661997737 | 2661997737 | ||
> print( | > print(StringHash("The quick brown fox jumps over the lazy dog")) | ||
3402772626 | 3402772626 | ||
| Line 31: | Line 31: | ||
==Code== | ==Code== | ||
function | local function StringHash(text) | ||
local counter = 1 | local counter = 1 | ||
local len = string.len(text) | local len = string.len(text) | ||
for i = 1, len, 3 do | for i = 1, len, 3 do | ||
counter = math.fmod(counter*8161, 4294967279) + -- 2^32 - 17: Prime! | counter = math.fmod(counter*8161, 4294967279) + -- 2^32 - 17: Prime! | ||
(string.byte(text,i)*16776193) + | (string.byte(text,i)*16776193) + | ||
((string.byte(text,i+1) or (len-i+256))*8372226) + | ((string.byte(text,i+1) or (len-i+256))*8372226) + | ||
((string.byte(text,i+2) or (len-i+256))*3932164) | ((string.byte(text,i+2) or (len-i+256))*3932164) | ||
end | end | ||
return math.fmod(counter, 4294967291) | return math.fmod(counter, 4294967291) -- 2^32 - 5: Prime (and different from the prime in the loop) | ||
end | end | ||
Revision as of 10:41, 13 February 2007
This page documents a user-defined function that you can copy and paste into your addon. Replace PREFIX with your addon or lib prefix to avoid conflicts between different versions of these functions.
Return a fair-quality 32-bit hash of a string
hashVal = StringHash("string")
Example
> print(StringHash(""))
1
> print(StringHash("ab"))
3458343178
> print(StringHash("ba"))
3466747145
> print(StringHash("AB"))
2653593770
> print(StringHash("BA"))
2661997737
> print(StringHash("The quick brown fox jumps over the lazy dog"))
3402772626
Details
- This algorithm is ~30% faster than a Lua implementation of the Java String.hashCode library call
- The bit transmutation patterns and resulting collision rates are MUCH better than the results from the Java hash
Code
local function StringHash(text)
local counter = 1
local len = string.len(text)
for i = 1, len, 3 do
counter = math.fmod(counter*8161, 4294967279) + -- 2^32 - 17: Prime!
(string.byte(text,i)*16776193) +
((string.byte(text,i+1) or (len-i+256))*8372226) +
((string.byte(text,i+2) or (len-i+256))*3932164)
end
return math.fmod(counter, 4294967291) -- 2^32 - 5: Prime (and different from the prime in the loop)
end