# Probability of collision with a hashing function

I have a data set with N = 80,000 supposedly unique individuals. Individuals are coded by a 9 digit hexadecimal "hashed" version of their 9 digit decimal US SSN. I have no idea what the "hashing" function is, but there appears to be collisions. I am interested in knowing what the expected number of collisions is with a general purpose 36 bit hashing function and 80,000 entries.

The goal of a hashing algorithm is, in the context of this discussion, to create a uniform distribution of the domain to the range. This will allow for the fewest hash collisions. The probability of a collision, assuming this is working correctly, given hashing n items into k locations is $n-k+k(1-1/k)^n$, which in your case is $80000-2^{36}+2^{36}(1-1/2^{36})^{80000}$, which is 4.6%.