2
$\begingroup$

Say I am given two hash functions f1 and f2 is there anyway that I can prove one hash function will produce fewer collisions than another one? That is say for some domain assuming all values in the domain are equally likely to be chosen can I show that f1 will on average perform better than f2?

Looking up how to determine if one hash is better than the other lead me to some interesting articles of how to compare cannabis but I couldn't find much else.

$\endgroup$
1
$\begingroup$

One measure to compare two hash function is the expected value of collision in the hash function. Now, based on the expected value, if a hash function has a lower collision in the expected sense could be a better hash function here. This expectation can be estimated by a random sample with a proper size from the specified domain.

Moreover, hash functions are compared base on their time complexity too, which is not your case here.

$\endgroup$
  • $\begingroup$ "This expectation can be computed by a random sample with a proper size from the specified domain." -- I think a better verb in this sentence is "estimated". $\endgroup$ – Raphael Nov 27 '18 at 7:59

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.