Editing WoW:StringHash/Analysis (section)

== Collision frequency test ==
<div style="margin-left: 3%;">

This test takes the result of 20000 random strings consisting of ASCII characters 0-255, and selects 15 bits for testing. The resulting value becomes 0--32767, which, for anything other than a [[wikipedia:perfect hash|perfect hash]], will result in a fair amount of collisions. We expect the frequency of collisions to match a [[wikipedia:Poisson distribution|Poisson distribution]] and compare the test results to it.


=== Long random string 32-127 bits 1-15 ===
<div style="margin-left:3%;">
      Java   SH     Expected
   1: 10940  10981  10863
   2:  6552   6554   6630
   3:  2043   1998   2023
   4:   388    396    411
   5:    65     65     62
   6:    12      6      7


</div>
=== Long random string 0-255 bits 1-15 ===
<div style="margin-left:3%;">
      Java   SH     Expected
   1: 10717  10728  10863
   2:  6796   6724   6630
   3:  1995   2073   2023
   4:   376    420    411
   5:   110     55     62
   6:     6             7


</div>
=== Long random string 0-255 bits 6-20 ===
<div style="margin-left:3%;">
      Java   SH     Expected
   1: 10788  10875  10863
   2:  6768   6628   6630
   3:  1989   1971   2023
   4:   400    460    411
   5:    55     60     62
   6:            6      7


</div>
=== Long random string 0-255 bits 12-26 ===
<div style="margin-left:3%;">
      Java   SH     Expected
   1: 10917  10791  10863
   2:  6630   6612   6630
   3:  1881   2049   2023
   4:   492    452    411
   5:    80     90     62
   6:            6      7


</div>
=== Long random string 0-255 bits 18-32 ===
<div style="margin-left:3%;">
      Java   SH     Expected
   1: 10828  10795  10863
   2:  6590   6860   6630
   3:  2127   1932   2023
   4:   380    360    411
   5:    75     35     62
   6:           18      7


</div>

=== Result analysis ===
<div style="margin-left:3%;">

Both hashes perform roughly as expected without showing too great variations over different bits; there are one or two aberrations in the higher collision counts, but that may just be the result of a too-small sample size. I will not investigate further as this test is only a rough indication of performance.

A more complete analysis would include testing smaller modulii, and certainly ones that are not a power of 2. A modulus constructed around series involving 31 and 32 will most likely produce "interesting" results for the Java hash, but that is an expected side effect of its construction.

</div>
</div>