2
$\begingroup$

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.

$\endgroup$

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.