About the explanation of testing and measurement of hash functions at Wikipedia I'm studying about hash functions with Wikipedia and here is the explanation of testing and measurement of a hash function's uniformity:

The formula is: $$\frac{\sum_{j=0}^{m-1}b_j(b_j+1)/2}{(n/2m)\,(n+2m-1)}$$
where: $n$ is the number of keys, $m$ is the number of buckets, $b_j$ is the number of items in bucket $j.$
A ratio within one confidence interval (0.95 - 1.05) is indicative that the hash function evaluated has an expected uniform distribution.

The chi-squared test is mentioned in the description, but I do not understand how this formula relates to the chi-squared test and how it was derived.
What is the relationship between this formula and the chi-squared test?
 A: The formula is incorrect.  It is inferior to the standard chi-squared test.  Because of its problems, I haven't been able to reverse-engineer it.  But I can shed some light on it and analyze its statistical characteristics.
A correct formula uses the definition of the chi-squared statistic:

*

*The expected count in bin $j$ is $e_j=n/m.$


*The residual in bin $j$ is the amount by which the actual count differs from the expectation, $r_j = b_j-e_j = b_j - n/m.$


*Chi-squared is the sum (over all bins) of the squared residual divided by the expectation, $$\chi^2 = \sum_{j} \frac{r_j^2}{e_j} = \sum_{j} \frac{(b_j-n/m)^2}{n/m} = \frac{m}{n}\sum_{j} \left(b_j - \frac{n}{m}\right)^2 = \frac{m}{n}\left[\sum_j b_j^2\right] - n.$$


*When hashing is truly uniform and independent, the expectation of $\chi^2$ is $m-1$ and its variance is $2(m-1).$
In light of this, let's consider the quoted formula.  I'll refer to it as $W.$
First, interpreting the ambiguous "$n/2m$" term as $(n/2)m,$ as required by rules of operator precedence, will give obviously incorrect values (approaching zero as $m$ grows large).  So let's interpret it as $n/(2m).$
Second, the formula simplifies so much (there are cancellation of some terms and the $b_j$ sum to $n$) that one must suspect a typographical error somewhere:
$$\begin{aligned}
W = \frac{1}{n/(2m)(n+2m-1)} \sum_j b_j(b_j+1)/2 &= \frac{1}{n+2m-1}\left(\frac{m}{n}\left[\sum_j b_j^2\right] + m\right) \\
&= \frac{1}{n+2m-1}\left(\chi^2 + n + m\right).
\end{aligned}$$
However, its expectation indeed is
$$E[W] = E\left[\frac{1}{n+2m-1}\left(\chi^2 + n + m\right)\right] = \frac{1}{n+2m-1}\left((m-1) + n + m\right) = 1,$$
as advertised.  What is of greatest interest is its variance, because that determines how wide a reasonable confidence interval should be:
$$\operatorname{Var}(W) = \frac{ \operatorname{Var}(\chi^2)}{(n+2m-1)^2} = \frac{m-1}{(n+2m-1)^2},$$
which means its standard deviation is
$$\operatorname{SD}(W) = \sqrt{\operatorname{Var}(W)} = \frac{\sqrt{m-1}}{n+2m-1}.$$
Reasonable confidence limits for $W$ should be a small multiple of this SD away from the expected value of $1.$
For hashing, $m$ is the number of buckets: on the order of hundreds or greater. For testing, you will generate huge values of $n$ -- billions or greater, often.  In such cases the SD becomes truly tiny.  This means $W$ is likely to be far closer to its expected value of $1.0$ than suggested by the 0.95 - 1.05 "confidence interval."  But, at the same time, a large value of $n/m$ guarantees the usual chi-squared test will work just fine.
As an example of why the quotation is so wrong, I conducted a test of a bad hashing mechanism.  It gave half of $m=211$ buckets a 50% greater chance of being a hash value than the other half.  Testing with only about a quarter million keys, $W$ turned out to be $1.0364:$ well within the Wikipedia "confidence interval."  The chance of a uniform hash being this bad, though, is astronomically small: only one part in $10^{135}$ (according to the standard chi-squared test).
Here's the R code:
chi2.wikipedia <- function(b, m) {
  n <- sum(b)
  if (missing(m)) m <- length((b))
  sum(b*(b+1)/2) / (n/(2*m) * (n+2*m-1))
}
set.seed(17)
b <- c(rpois(105, 100), rpois(106, 150))       # 150:100 probability ratio
chi2.wikipedia(b)                              # Around 1.0364
pchisq(chi2(b), length(b)-1, lower.tail=FALSE) # Chi-squared test

The SD of $W$ in this example is a mere $0.00054.$  Thus, if this testing should turn up values more than two or three SDs away from $1,$ you would conclude the hash function is not uniform.
I will admit that you might not need to be terribly fussy: it's probably okay for a hash function not to be quite uniform.  However, if you thought your implementation was uniform and there's evidence it is not, beware: that flags a potentially deeper problem and possible bugs down the line.

The moral is that when a simple, standard statistical analysis will do the job, don't use an ad hoc substitute.

