0
$\begingroup$

I have been reading Cormen's chapter 11 and I stumbled upon the following statement on page 260 (3rd Edition):

Let xi denote the ith element inserted into the table, for i = 1, 2 ... n, and let ki = xi.key. For keys ki and kj , we define the indicator random variable Xij = I {h(ki) = h(kj)}. Under the assumption of simple uniform hashing, we have Pr {h(ki) = h(kj)} = 1/m.

I know that the probability of a specific key being assigned to a slot is 1/m as a result of simple uniform hashing, hence Pr(h(ki)) = a = 1/m, Pr(h(kj)= a = 1/m. But I haven't been able to take the mental leap to infer from this that the probability of two keys being assigned to the same slot is 1/m. Is there any place on the internet where I can find proof of this?

$\endgroup$

1 Answer 1

1
$\begingroup$

What is the probability of both being in slot 1, both being in slot 2, …., both being in slot m? And since these events are separate, you can add up those m probabilities and get the probability that two are the same.

$\endgroup$
1
  • $\begingroup$ Pr(ki hashed to the same slot as kj) = Pr(h(ki)=0 and h(kj)=0) + Pr(h(ki)=1 and h(ki) =1) +...+Pr(h(ki)=m-1 and h(kj)=m-1). Each term is 1/m2 because the events are independent and there are m terms, m/m2 = 1/m. Thank you kind sir! $\endgroup$ Commented Sep 27, 2023 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.