I'm trying to test if a hash function mantains a even distribution of values. My plan is to generate a set X of hashes and a integer Y symbolizing "slots" to see how many of the hashes maps to the slots given the mapping function x mod Y for every x in X. This is similar as how a hash table data structure works.

If every slot has a number y of mapped hashes, then I plan to calculate the standard deviation of these values respecting the expected value count(X) / Y. If repeat this test N times, I will end with N standar deviation values. Can I calculate then an arithmetic (maybe geometric?) mean to obtain a final value of how "evenly" distributed these hash function can be?

Sorry for bad english and/or bad statistics xD


Adding the variances of your measurements to get an average variance would make more sense, this is because if $A$ and $B$ are random variables then Var(A+B) = Var(A)+Var(B) but the same is not true for standard deviations StDev(A+B) ≠ StDev(A)+StDev(B).

| cite | improve this answer | |
  • $\begingroup$ Oh, I was not aware of that rule. Now using the variance instead of stdev makes more sense indeed :D $\endgroup$ – fabiux Apr 1 '16 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.