Do two files hash into the same bucket?

Question

A hash function spreads keys across 16 buckets, and you may assume each key is equally likely to land in any bucket, independently. You hash two different files. What is the probability that the two files land in the same bucket (a collision)?

Accepted Answer

Send the first file through the hash function; it ends up in some bucket. That bucket is now the target. The second file is equally likely to land in any of the 16 buckets, and only one of them (the first file's bucket) is a collision. So P(	ext{collision}) = \frac{1}{16} = 0.0625, which is 6.25\%. Which bucket the first file chose is irrelevant. Once it is placed, the second file collides with probability 1/16. Takeaway. A single pair of keys collides with probability 1/d, where d is the number of buckets. With 16 buckets that is 1/16 = 6.25\%.

Do two files hash into the same bucket?

Your answer

Discussion

Learn the concepts

Related questions