Madeeasy TestSeries

Question

Suppose we used a hash function H(n) to hash ‘n’ distinct elements (keys) into an array T of length ‘m’. What is the expected number of colliding pairs of elements, if we used simple uniform hashing?

Comments

https://gateoverflow.in/159733/uniform-hashing

this will give a better perspective

Answer 1

Let's choose two element i.e. the pair  nC2 ways =n(n-1)/2 =k

each pair we assume as "x"

Each pair having same probability for collision that is 1/m =p(x)

ans = $\sum_{1}^{k}x p(x)$  

      =[n(n-1)/2] * 1/m
      = [n(n-1) /2m] should be the ans..

http://test.scripts.psu.edu/users/d/j/djh300/cmpsc465/notes-4985903869437/solutions-to-some-homework-exercises-as-shared-with-students/3-solutions-clrs-11.pdf
 

http://gatecse.in/w/images/7/7d/IntroductiontoAlgorithms-CormenSolution.pdf

Comments

see the given link...

---

@rahul sharma 5 probability for a key to hash to a particular location is $1/m$. similarly for the second key. so the probability of two keys hashing to the same location is $\frac{1}{m^2}$. now there are $m$ possible locations where these two keys can be placed. so probability of two keys hashing to the same location becomes $m\frac{1}{m^2} = \frac{1}{m}$

---

if it wasnt colliding PAIRS then it would be n(n-1)/2 right?