How good is the hash function in your language of choice, particularly for strings? Chances are, not very. I applied the classical statistical tests popularized by Knuth and I was very surprised to see how bad OCaml's hash function on strings is.
I applied the chi-square test on the distribution of hashes over /usr/share/dict/words, for almost 235.000 words. I binned the integers from the most significant bit down, taking successively more and more bits into account, and tested the resulting distribution against a uniform distribution. Here are the results:
|Bins (ν)||X²||Pr[χ² ≤ X²]|
The first column indicates how many bins were used, which is the degrees of freedom in the probability distribution (ν). The second column shows the computed statistic. The third column shows the probability with which a χ² deviate with ν degrees of freedom would be at least this value. Highlighted in red are the failed entries according to Knuth's criterion (probability in first or last percentile) and in yellow the suspect entries (probability in first five or last five percentiles).
Pretty dismal, isn't it? The Kolmogorov-Smirnov test is equally appalling: the probability that entries are this higher than a uniform deviate is p+ = 0.0016593, the probability that entries are this lower than a uniform deviate is p- = 1.0000000 both of which are extreme.
Postprocessing the hashes with a simple mixing function helps matter considerably. I use the Murmur hash specialized to a single 32-bit value:
let murmur_hash_32 k h = let m = 0x5bd1e995l in let k = Int32.mul k m in let k = Int32.logxor k (Int32.shift_right_logical k 24) in let k = Int32.mul k m in let h = Int32.mul h m in let h = Int32.logxor h k in let h = Int32.logxor h (Int32.shift_right_logical h 13) in let h = Int32.mul h m in let h = Int32.logxor h (Int32.shift_right_logical h 15) in h let universal_hash i h = let r = murmur_hash_32 (Int32.of_int h) (Int32.of_int (succ i)) in Int32.to_int (Int32.logand r 0x3fffffffl)
Since Murmur hash achieves full 32-bit avalanche, I can use it to construct a universal hash function. The results of applying this mixing function to
Hashtbl.hash are much more encouraging:
|bins (ν)||X²||Pr[χ² ≤ X²]|
Much better, except maybe for the distribution on 1024 bins (the 10 most significant bits). The Kolmogorov-Smirnov test shows that the probability that entries are this higher than a uniform deviate is p+ = 0.7688490, the probability that entries are this lower than a uniform deviate is p- = 0.4623243 which are much more balanced.
Know your hash function. It should be random.