WoW:USERAPI StringHash - Revision history

Move page script: Move page script moved page USERAPI StringHash to WoW:USERAPI StringHash without leaving a redirect

2023-08-15T04:49:14Z

Move page script moved page USERAPI StringHash to USERAPI StringHash without leaving a redirect

← Older revision

Revision as of 04:49, 15 August 2023

WoWWiki>Charibot: catfix

2008-07-09T00:44:05Z

catfix

← Older revision		Revision as of 00:44, 9 July 2008
Line 45:		Line 45:

	__NOTOC__		__NOTOC__
	[[Category:User ~~Defined Functions~~]]		[[Category:User defined functions]]

WoWWiki>Tekkub at 10:41, 13 February 2007

2007-02-13T10:41:24Z

← Older revision		Revision as of 10:41, 13 February 2007
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 = ~~''<PREFIX>''_StringHash~~("string")		hashVal = StringHash("string")


	== Example ==		== Example ==
	> print(~~PREFIX_StringHash~~(""))		> print(StringHash(""))
	1		1
	> print(~~<PREFIX>_StringHash~~("ab"))		> print(StringHash("ab"))
	3458343178		3458343178
	> print(~~<PREFIX>_StringHash~~("ba"))		> print(StringHash("ba"))
	3466747145		3466747145
	> print(~~<PREFIX>_StringHash~~("AB"))		> print(StringHash("AB"))
	2653593770		2653593770
	> print(~~<PREFIX>_StringHash~~("BA"))		> print(StringHash("BA"))
	2661997737		2661997737
	> print(~~<PREFIX>_StringHash~~("The quick brown fox jumps over the lazy dog"))		> print(StringHash("The quick brown fox jumps over the lazy dog"))
	3402772626		3402772626

Line 31:		Line 31:

	==Code==		==Code==
	function ~~''<PREFIX>''_StringHash~~(text)		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); -- 2^32 - 5: Prime (and different from the prime in the loop)		return math.fmod(counter, 4294967291) -- 2^32 - 5: Prime (and different from the prime in the loop)
	end		end

WoWWiki>Shazear: /* Code */ W/ the 2.0 changes, lua 5.1 renamed math.mod to math.fmod

2007-01-12T21:41:50Z

Code: W/ the 2.0 changes, lua 5.1 renamed math.mod to math.fmod

← Older revision		Revision as of 21:41, 12 January 2007
Line 35:		Line 35:
	local len = string.len(text);		local len = string.len(text);
	for i = 1, len, 3 do		for i = 1, len, 3 do
	counter = math.~~mod~~(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.~~mod~~(counter, 4294967291); -- 2^32 - 5: Prime (and different from the prime in the loop)		return math.fmod(counter, 4294967291); -- 2^32 - 5: Prime (and different from the prime in the loop)
	end		end

WoWWiki>Mikk: /* Code */ "mod" -> "math.mod" so it works outside of wow

2006-08-24T17:57:12Z

Code: "mod" -> "math.mod" so it works outside of wow

New page

{{userfunc}} 
<center>'''StringHash''' ''- by {{user|Mikk}} -''</center>

Return a fair-quality 32-bit hash of a string

hashVal = ''<PREFIX>''_StringHash("string")

== Example ==
> print(PREFIX_StringHash(""))
1
> print(<PREFIX>_StringHash("ab"))
3458343178
> print(<PREFIX>_StringHash("ba"))
3466747145
> print(<PREFIX>_StringHash("AB"))
2653593770
> print(<PREFIX>_StringHash("BA"))
2661997737
> print(<PREFIX>_StringHash("The quick brown fox jumps over the lazy dog"))
3402772626

==Details==

* This algorithm is ~30% faster than a Lua implementation of the Java [http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html#hashCode() String.hashCode] library call

* The bit transmutation patterns and resulting collision rates are MUCH better than the results from the Java hash

* See [[StringHash/Analysis]]

==Code==
function ''<PREFIX>''_StringHash(text)
local counter = 1;
local len = string.len(text);
for i = 1, len, 3 do
counter = math.mod(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.mod(counter, 4294967291); -- 2^32 - 5: Prime (and different from the prime in the loop)
end

__NOTOC__
[[Category:User Defined Functions]]