stochastic programsprobabilityand statistics hashing and collisions in section we pointed out that by using larger hash table one could reduce the incidence of collisionsand thus reduce the expected time to retrieve value we now have the intellectual tools needed to examine that tradeoff more precisely firstlet' get precise formulation of the problem assumea the range of the hash function is to nb the number of insertions is kand the hash function produces perfectly uniform distribution of the keys used in insertionsi for all keyskeyand for integersiin the range to nthe probability that hash(keyis is / what is the probability that at least one collision occursthe question is exactly equivalent to asking "given randomly generated integers in the range to nwhat is the probability that at least two of them are equal if >nthe probability is clearly but what about when nas is often the caseit is easiest to start by answering the inverse question"given randomly generated integers in the range to nwhat is the probability that none of them are equal?when we insert the first elementthe probability of not having collision is clearly how about the second insertionsince there are - hash results left that are not equal to the result of the first hashn- out of choices will not yield collision sothe probability of not getting collision on the second insertion is !!and the probability of not getting collision on either of the first two insertions is !!we can multiply these probabilities because for each insertion the value produced by the hash function is independent of anything that has preceded it the probability of not having collision after three insertions is !!!!after insertions it is !!!!!!!and to get the probability of having at least one collisionwe subtract this value from the probability is -!- !- !!- given the size of the hash table and the number of expected insertionswe can use this formula to calculate the probability of at least one collision if were reasonably largesay , it would be bit tedious to compute the probability with pencil and paper that leaves two choicesmathematics and programming mathematicians have used some fairly advanced techniques to find way to approximate the value of this series but unless is very largeit is easier to run some code to compute the exact value of the series