# Counting hash collisions with the birthday paradox

DevFeed: [Counting hash collisions with the birthday paradox](<https://devfeed.tech/articles/counting-hash-collisions-with-the-birthday-paradox-35234.md>)

Original publisher: [Read original article](<http://matt.might.net/articles/counting-hash-collisions/>)

Published: 2015-07-17T03:33:41Z

Content type: tutorial

Language: en

Sources: [Matt Might](<https://devfeed.tech/sources/matt-might.md>)

Topics: [hash](<https://devfeed.tech/topics/hash.md>), [hashing](<https://devfeed.tech/topics/hashing.md>), [function](<https://devfeed.tech/topics/function.md>), [Network](<https://devfeed.tech/topics/network.md>)

Tags: [hash](<https://devfeed.tech/tags/hash.md>), [hashing](<https://devfeed.tech/tags/hashing.md>), [sequence](<https://devfeed.tech/tags/sequence.md>), [technical](<https://devfeed.tech/tags/technical.md>)

## AI overview

This technical note derives a closed-form formula for the expected number of hash collisions among n values when a uniform hash function has a range of D possible outputs. It explains the connection to the birthday paradox and clarifies that the formula counts sequential matching events rather than unique hits or collision pairings.

## Source excerpt

The birthday paradox observes that in a room of 23 people, the odds that at least two people share a birthday is 50% The same logic that drives matching birthdays also drives the probability that one can find collisions with a hash function. In other words, if you have a uniform hashing function that outputs a value between 1 and 365 for any input, the probability that two hashes would collide in a set of 23 values is also 50% Another useful calculation is the expected number of collisions for a sequence of \(n\) values when the range of the hash function contains \(D\) hashes. The closed form solution is: \[ n - D + D \left( \frac{D-1}{D} \right)^n \] There are a few places online that have this (or an equivalent) closed form solution listed, but I couldn't find anywhere that included the derivation of this form, so I've rederived it and posted it here as a technical note. (My present interest in this calculation comes from the number of matches that will happen in a patient-matching network that attempts to match patients having the same disease, assuming the are \(D\) total diseases possible and \(n\) patients in the network.) Read below for the derivation in terms of generalized birthdays. Click here to read the rest of the article