CS70 Guide

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.
An interesting result is explored by the Birthday Problem (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.