Editing WoW:StringHash/Analysis (section)

== 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>