Hashing

Question

If h is any hashing function and is used to hash n keys into a table of size m, here n<=m, the expected number of collisions involving a particular key x is

a) Less than 1
b) Less than n
c) Less than m
d) Less than n/2

Comments

Option A??

---

yes, explain plz!

---

According to me, Because load factor <=1

Correct me if I am wrong!

---

is there any relation between load factor and collision???

Answer 1

Ans. Option A - less than 1.

This is a theorem in Universal Hashing -

"If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n<=m, the expected number of collisions involving a particular key x is less than 1."

Reference: You can check the "Universal Hashing" section of the following link (for details):
http://www.cs.nmsu.edu/~ipivkina/Spring08cs372/Cormen/chapter12HashTables.htm

And a simiar question has been asked earlier too. 

Please refer Cormen on Algorithm for further reading. Yeah!!!

Refer d link below as well:

https://gateoverflow.in/45237/hashing

I hope d explanation helps u. :)