CS70 Guide
  • This site is now deprecated
  • LaTeX Reference
  • Discrete Math
    • Overview
    • Propositional Logic
    • Proofs
    • Stable Matching
    • Graphs
    • Modular Arithmetic
    • RSA Cryptography
    • Polynomials
    • Countability
    • Computability
  • Probability
    • Overview
    • Counting
    • Discrete Probability
    • Hashing and the Union Bound
    • Expectation and Variance
    • Concentration Inequalities
    • Continuous Probability
    • Markov Chains
    • The Beta Family
    • The Gamma Family
    • Conditional Expectation and Variance
Powered by GitBook
On this page

Was this helpful?

  1. Probability

Hashing and the Union Bound

PreviousDiscrete ProbabilityNextExpectation and Variance

Last updated 2 years ago

Was this helpful?

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 (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.

http://prob140.org/textbook/content/Chapter_01/03_Collisions_in_Hashing.html
Birthday Problem