I have just started to learn about the topic of hashing. I understand how it works and the difference between closed address and open address, but do not know how to calculate the probability of a possible collision

1) Table uses closed address hashing and has $m$ addresses with $n$ records already in it. Two independent keys are inserted into it what is the probability of a collision?

I did some research and reading and a few things seemed important, I came across the birthday problem, pigeonhole principle and a formula of Hash collision Probability $= 2^{-n} = \frac{1}{2^n}$ but not sure how to piece things together, especially since definite numbers are not involved in the question and a hash function was not stated.

2) Table uses open address hashing that contains $m$ addresses ($m>4$).Three keys are already in the table. What is the probability that the fourth key will need four probes to save data?

Only thing I really get with this concept is that collisions are avoided by implementing a linked list? So that multiple keys could be assigned a block in the table. Again we don't know how big the table is, but we now it is greater than $4$, how do you go about solving this with the little information given.

Would really appreciate some insight on these problems as I honestly do not know how to tackle them.


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.