Welcome, guest | Sign In | My Account | Store | Cart

Hash collision probability / Birthday problem (Python recipe) by Sander Evers
ActiveState Code (http://code.activestate.com/recipes/578387/)

Calculates the probability that, when making k random selections out of n possibilities, at least two of the selections are the same. See: http://en.wikipedia.org/wiki/Birthday_problem

What is the probability that (at least) two people in a class of 30 share their birthday?

>>> collide(30,365)
0.7063162427192688

What is the probability that ORA_HASH generates the same hash when hashing 25000 values?

>>> collide(25000,int(4.3e9))
0.07009388771353198
Python, 15 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import itertools

def alldifferent(k,n):
    '''The probability that k random selections from n possibilities
    are all different.'''
    assert(k<=n)
    nums = xrange(n,n-k,-1)
    dens = itertools.repeat(n)
    fracs = itertools.imap(lambda x,y: float(x)/y, nums,dens)
    return reduce(float.__mul__, fracs)

def collide(k,n):
    '''The probability that, in k random selections from n possibilities,
    at least two selections collide.'''
    return 1 - alldifferent(k,n)
Tags: birthday, collision, hash