Editing Hash function (section)

=== Testing and measurement ===
When testing a hash function, the uniformity of the distribution of hash values can be evaluated by the [[chi-squared test]].   This test is a goodness-of-fit measure: it is the actual distribution of items in buckets versus the expected (or uniform) distribution of items. The formula is

<math>\frac{\sum_{j=0}^{m-1}(b_j)(b_j+1)/2}{(n/2m)(n+2m-1)},</math>
 
where {{Mvar|n}} is the number of keys, {{Mvar|m}} is the number of buckets, and {{Math|''b''<sub>''j''</sub>}} is the number of items in bucket {{Mvar|j}}.

A ratio within one confidence interval (such as 0.95 to 1.05) is indicative that the hash function evaluated has an expected uniform distribution.

Hash functions can have some technical properties that make it more likely that they will have a uniform distribution when applied.  One is the [[strict avalanche criterion]]: whenever a single input bit is complemented, each of the output bits changes with a 50% probability.  The reason for this property is that selected subsets of the keyspace may have low variability.  For the output to be uniformly distributed, a low amount of variability, even one bit, should translate into a high amount of variability (i.e. distribution over the tablespace) in the output.  Each bit should change with a probability of 50% because, if some bits are reluctant to change, then the keys become clustered around those values.  If the bits want to change too readily, then the mapping is approaching a fixed XOR function of a single bit.  Standard tests for this property have been described in the literature.<ref>{{cite journal |first1=Julio Cesar Hernandez |last1=Castro |first2=José María |last2=Sierra |first3=Andre |last3=Seznec |first4=Antonio |last4=Izquierdo |first5=Arturo |last5=Ribagorda |display-authors=1 |date=3 February 2005 |title=The strict avalanche criterion randomness test |journal=Mathematics and Computers in Simulation |volume=68 |issue=1 |pages=1–7 |publisher=[[Elsevier]] |doi=10.1016/j.matcom.2004.09.001|s2cid=18086276 }}</ref>  The relevance of the criterion to a multiplicative hash function is assessed here.<ref name="fibonacci-hashing">{{cite web |first=Malte |last=Sharupke |title=Fibonacci Hashing: The Optimization that the World Forgot |url=https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ |website=Probably Dance |date=16 June 2018}}</ref>