stochastic programsprobabilityand statistics def collisionprob(nk)prob for in range( )prob prob (( )/float( )return prob if we try collisionprob( we get probability of about of there being at least one collision if we consider insertionsthe probability of collision is nearly one does that seem bit high to youlet' write simulationfigure to estimate the probability of at least one collisionand see if we get similar results def siminsertions(numindicesnuminsertions)"""assumes numindices and numinsertions are positive ints returns if there is collision otherwise""choices range(numindices#list of possible indices used [for in range(numinsertions)hashval random choice(choicesif hashval in used#there is collision return elseused append(hashvalreturn def findprob(numindicesnuminsertionsnumtrials)collisions for in range(numtrials)collisions +siminsertions(numindicesnuminsertionsreturn collisions/numtrials figure simulating hash table if we run the code print 'actual probability of collision ='collisionprob( print 'est probability of collision ='findprob( print 'actual probability of collision ='collisionprob( print 'est probability of collision ='findprob( it prints actual probability of collision est probability of collision actual probability of collision est probability of collision the simulation results are comfortingly similar to what we derived analytically should the high probability of collision make us think that hash tables have to be enormous to be usefulno the probability of there being at least one collision tells us little about the expected lookup time the expected time to look up value depends upon the average length of the lists implementing the buckets that hold the values that collided this is simply the number of insertions divided by the number of buckets