Some Useful Probability Facts for Systems Programming
Birthday paradox is way too important to omit from this list!<p>For example if you're uploading stuff to a bucket, you can compute its hash first to figure out if a duplicate already exists and if so, skip the upload.<p>Why can you do this? What if it was just a hash collision? Shouldn't you still compare the contents to <i>really</i> make sure they are the same?<p>Turns out if your hash function is N bits you will need to have 2^(N/2) items before you see two hashed to the same thing by chance. If you choose a 256 bit cryptographic hash function like SHA256, that's 2^128. This probability is so low you have a higher chance of encountering a cosmic ray bit flip!<p><a href="https://en.wikipedia.org/wiki/Content-addressable_storage" rel="nofollow">https://en.wikipedia.org/wiki/Content-addressable_storage</a><p><a href="https://en.wikipedia.org/wiki/Birthday_problem" rel="nofollow">https://en.wikipedia.org/wiki/Birthday_problem</a>