Suppose we have a table of size M and we want to map N elements using a hashing function. This question had a lot of sub parts - The first one was that find the expected number of collisions which I was able to find out as n(n-1)/2m

Now it asks to find the probability that the hashing function is perfect, the probability that none of the functions used are perfect and what is the number of hash functions we need to find before we get high probability

I'm stuck at this part. I tried using permutations and combinations but how can one calculate the total number of cases of hashing which would in turn find out the probability.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.