bday

README

bday

Performs estimates related to hashing collisions and probabilities.

For estimating the probability of collision for a given number of elements being inserted into an array with x^y elements, the birthday paradox is used.

Only the -x flag is required.

Calculations

If neither -n nor -p are specified, or if n <= 1; the probability of two elements colliding will be calculated; i.e. n == 2.

Probability of collision for n elements.

-n estimates the probability of at least two elements colliding, p(n;d), when inserting n elements into an array, d.

$ bday -n 10 -x 365
$ The probability of at least two elements colliding when hashing 10 elements into a 365 element array is 11.614024%.

Number of elements for a given probability of collision.

-p estimates the number of elements, n, that need to be drawn from a set, d (x^y), for a collision to occur given a probability, p.

$ bday -p 11.6 -x 365
$ 10 elements are needed to have a of 11.6000% chance of 2 elements colliding when hashing into a 365 element array.

Number of collisions when inserting n elements.

Use the -c flag in conjunction with the -n flag to calculate the expected number of collisions when hashing n elements into d slots. This uses the Theorem 6.15 from https://math.dartmouth.edu/archive/m19w03/public_html/Section6-5.pdf.

$ bday -n 100 -x 10 -y3 -c
$ The estimated number of collisions when hashing 100 elements into 256 slots is 17.08581506804407.

Flag notes

The -n and -p flags are mutually exclusive as the calculations produce one of those values, depending on which flag is present.

If the base, -x, is to be used as the size of the array, don't use the exponent flag, -y.

Install

$ go install github.com/mohae/bday

// check that it runs; get the flags.
$ bday -h