Skip to content

Instantly share code, notes, and snippets.

@miestasmia
Created March 27, 2019 12:28
Show Gist options
  • Save miestasmia/ecfe674bbd6c3c271ad3c0cca787aa16 to your computer and use it in GitHub Desktop.
Save miestasmia/ecfe674bbd6c3c271ad3c0cca787aa16 to your computer and use it in GitHub Desktop.
Determines the probability of a hash collision occuring and compares it to the probability of being killed by a shark or a meteor
#!/usr/bin/env node
/* https://preshing.com/20110504/hash-collision-probabilities/
*
* Question: "Given k randomly generated values, where each value is a
* non-negative integer less than N, what is the probability that at least two
* of them are equal?"
*
* In other words, what's the probability of a hash collision?
*
* -k(k - 1)
* Answer: p = 1 - e^---------
* 2N
*
*/
const _k = process.argv[2];
const k = eval(_k);
console.log(`k = ${_k} = ${k.toPrecision(3)} (number of hashes)`)
const _N = process.argv[3];
const N = eval(_N);
console.log(`N = ${_N} = ${N.toPrecision(3)} (hash size + 1)`);
console.log(); // newline
const p = 1 - Math.exp( (-k*(k - 1)) / ( 2*N ));
let probHuman = p.toPrecision(3);
const relativeShark = p / (1 / (300 * 10**6));
const relativeSharkHuman = relativeShark.toPrecision(3);
const relativeMeteor = p / (1 / (182 * 10**9));
const relativeMeteorHuman = relativeMeteor.toPrecision(3);
console.log(`The probability of a collision is: ${probHuman}`)
console.log(`That's ${relativeSharkHuman} the probability of dying in a shark attack.`);
console.log(`That's ${relativeMeteorHuman} the probability of your house getting hit by a meteor.`);
@miestasmia
Copy link
Author

Example usage:
./hashcollision.js 10**6 2**(8*5)

For the probability of a hash collision with 10^6 hashes of 5 bytes each.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment