2 votes 2 votes 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? Rock asked Nov 20, 2016 Rock 1.3k views answer comment Share Follow See 1 comment See all 1 1 comment reply TUSHAR_BHATT commented Sep 1, 2018 reply Follow Share https://gateoverflow.in/159733/uniform-hashing this will give a better perspective 0 votes 0 votes Please log in or register to add a comment.
Best answer 8 votes 8 votes 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 papesh answered Nov 20, 2016 selected Jan 1, 2017 by pC papesh comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments papesh commented Dec 19, 2016 reply Follow Share see the given link... 0 votes 0 votes air1 commented Dec 31, 2016 reply Follow Share @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}$ 1 votes 1 votes A_i_$_h commented Aug 19, 2017 reply Follow Share if it wasnt colliding PAIRS then it would be n(n-1)/2 right? 0 votes 0 votes Please log in or register to add a comment.