Cormen 2nd edition Exercise 11.2-1

Question

Suppose we use a hash function h to hash n distinct keys into an array T of length m. Assuming simple uniform hashing, what is the expected number of collisions?

Answer 1

Probability of a hash to a given slot $=\frac{1}{m}$ since hashing is uniform. (Also whatever be the probing, all elements are stored in the array only)

Expected number of collisions (assuming $n \leq m)$

$=1\times \text{Probability of collision in first insertion}\\
+1\times \text{Probability of collision in second insertion}\\
\ldots\\
+1\times \text{Probability of collision in $n^{th}$ insertion}\\
= 1*0 + 1*\frac{1}{m} + 1* \frac{2}{m} + 1* \frac{3}{m} + \ldots + 1* \frac{n-1}{m}\\
= \frac{n^2-n}{2m}$

Comments

@ Arjun sir   why we are multiplying by 1  what does that mean in the expression …..

and why we are not doing like that ….E(x) as number of occurance of x * probabilty of occurence of x 

so expected number of collision is …...0 collision * prob of 0 collision +1 collision * probabilty of 1 collision + 2 collisions *probabilty  of  two collisions……………………………..and so on….

0*0/m   +  1* 1/m  +  2*2/m  +……………...and so on

 

---

@eyeamgj I have the same doubt.

Question is missing this: Once a collision occurs, we cannot add more keys.

So that’s why we are multiplying by 1 in each case.

---

bro if got it now ,please explain

Answer 2

Nice question @Pranjal.

Since there are m slots the probability of inserting a key into a specific slot is 1/m

Probability to place two keys in a particular slot is 1/m* 1/m

As there are m slots probability of colliding two keys is m*1/m*1/m =1/m

Just now we solve for only 2 keys. There are n keys.

First key can be collided with n-1 keys

Second key can be collided with n-2 keys..

total number of combinations = n(n-1)/2

Expected number of collisions = n(n-1)/2m

Comments

when we insert first key. hash table is empty. So how can it be colllided with $n-1$ keys ?

---

Actually, the First key will  be collied with 0

The second key will be collied with 1

The third key will be collied with 2

.

.

The n'th(last) key will be collied with (n-1) keys....

so total is 0+1+2+3+4+........+(n-1)=n(n-1)/2

Expected no. of collision is n(n-1)/2*1/m

---

Why we always using 1/m,
If we are calculating for 2 collisions the probability of collision should be 2/m for the 3rd element>

---

But somewhere expected number of collisions written as

 

n-k + k . (1-(1/k))^n

 

???