Uniform Hashing

Question

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

Comments

Another way of saying this

https://gateoverflow.in/96893/tifr2016-a-4

Answer 1

# of slots = m

# of keys = n

so Expected number of colliding pairs  // uniform hashing

We will consider all cases like a child(simplest way to calculate expected value) to know expectation

We know in uniform hashing the probability for any particular key to get any particular slot = 1/m

now to collide another element must have to allocate same slot , and we know P_{that slot} =1/m

So let suppose your Key =K₁  so now total n-1 keys can make pair with it and collide so possible outcomes of this case = n-1 and P=1/m

Now when Key=K₂ now possible keys that can collide are n-2

so in that way when key=K_n-1 the possible keys that cna collide =1 so 1 outcome of this case

so expected value = (n-1)*1/m + (n-2)*1/m + (n-3)*1/m +....2*1/m + 1*1/m

so it's     n*(n-1)/2m

You can know the proper process here , they just calculated final output of summation wrong , that's n-1 not n+1

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/exams/final_sol.pdf

the approach i followed to calculate expected value

https://www.wikihow.com/Calculate-an-Expected-Value

Comments

ans given O(n²/m)

chk your 1st link, There is nothing about hashing

---

O(n*(n-1)/2m) = O(n²/m)

in my first link , they mentioned simple uniform hashing...exactly same as your question asked..