4

I dont find any info about % of collisions for xxhash64.

I'm going to use it for cache system (to generate hash keys which need to be unique, about a hundreds millions). Now i use md5, but i don't need cryptographic property.

So i need some info, to decide does is it a good decision for my task. In best case - comparison of the number of collisions between md5 and xxHash64.

1
  • xxhash64, fast algoritm ? what is it ? 64 bit hash? Aug 21, 2017 at 7:50

1 Answer 1

9

You can calculate yourself by using the birthday problem.

In general the mathematical expression that gives you the probability of hash function is :

p(k) = 1 - exp(-k(k-1)/2N, k (number of hashes) randomly generated values, where each value is a non-negative integer less than N (number of possible hashes):

N = 2^(number of bit), example for md5 it is 2^128, or 2^32 for 32 bit-hash

If you use md5

will produce a 128-bit hash value, by applying this formula you get this 'S' graph. This graph explains, for example, in order to get a collison probability of 50% (0.5), you need at least 21 000 000 trillion of hashes or 21 quintillion of hashes!!!! If you we use less than, for instance 1 billion of hashes, the probability of collision is negligible.

enter image description here

If you are using hundred millions of hashed keys, the probability of collision is 0% using md5.

If you use xxhash64,

Assuming that xxhash64 produce a 64-bit hash. You will get this graph. enter image description here

According to this picture, you can see that if the collision percentage is 50%, you need at least 5 billion of hashes. Two of the 5 billion of hashes can have an odd of 1/2 to have the same hashes!!! If you have around 12 billion of hashes there is 100% of chance that the hashes collide.

If you are using hundred millions of hashed keys, the probability of collision is 0.033% using xxhash64.

This link explains why md5 or fast hash method are not secure.

2
  • 1
    Thanks - nice graphs! But it looks like you lost a zero there. Don't you mean 21 quintillion == 21,000,000 trillion hashes for MD5?
    – nealmcb
    May 2, 2022 at 21:15
  • 1
    Ya i lost a zero... yes... edited according to your suggestion. May 8, 2022 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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