> For the complete documentation index, see [llms.txt](https://cs70.bencuan.me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs70.bencuan.me/probability/hashing-and-the-union-bound.md).

# Hashing and the Union Bound

A hash function assigns a value to each member in a set. It's often useful to determine the probability of collisions: where two different items are assigned the same hash value.

<http://prob140.org/textbook/content/Chapter_01/03_Collisions_in_Hashing.html>

An interesting result is explored by the [Birthday Problem](http://prob140.org/textbook/content/Chapter_01/04_Birthday_Problem.html) (sometimes known as the Birthday Paradox, despite not actually being paradoxical), in which the probability of at least two people sharing the same birthday is much higher than expected.