Editing WoW:StringHash/Analysis (section)

= Reference code =
<div style="margin-left: 3%;">

== Java hash ==
<div style="margin-left: 3%;">

   for i = 1, len do 
     counter = (counter*31) + string.byte(text, i)
     counter = mod(counter, 4294967296);	-- 2^32
   end; 
   return mod(counter, 4294967296);  -- 2^32

This is the function implemented in the Java [http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html#hashCode() String.hashCode] library call.

The multiplication by 31 basically translates to "new = old&lt;&lt;5 - old", i.e. you never completely lose data from earlier bytes as you would by only shifting data up.
The relation to Bernstein's original "33" function is pretty clear; it simply uses 33 instead of 31.

The mod() is necessary in Lua, otherwise the value turns floating-point and you lose precision after ~10 characters; Lua, at least under x86, uses 64-bit ("double-precision") IEEE 764 floats, which have a mantissa of 52 bits.

This function would be slightly better with a prime modulus, but 2^32 is chosen as a modulus to emulate 32-bit integer math as used in the Java SDK.


</div>
== StringHash ==
<div style="margin-left: 3%;">

   for i = 1, len, 3 do 
     counter = 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 mod(counter, 4294967291); -- 2^32 - 5: Prime (and different from the prime in the loop)

This string hash is ~30% faster than the Java hash due to working with 3 characters at a time; the modulus call is fairly expensive compared to the other operations.


The multiplications are all chosen to affect 3 areas of the accumulator at a time:
      8161 =     8192 -     32 + 1  : 2&lt;&lt;13,  2&lt;&lt; 5,  2&lt;&lt;0
  16776193 = 16777216 -   1024 + 1  : 2&lt;&lt;24,  2&lt;&lt;10,  2&lt;&lt;0
   8372226 =  8388608 -  16384 + 2  : 2&lt;&lt;23,  2&lt;&lt;14,  2&lt;&lt;5
   3932164 =  4194304 - 262144 + 4  : 2&lt;&lt;22,  2&lt;&lt;18,  2&lt;&lt;10

It is tempting to make the first multiplication much larger, but beware that the result of (4294967279+(256*29080583))*8161 must fit in a 52-bit mantissa without losing precision. The result is currently a 48-bit number so meets that contraint.


</div>
</div>