edited by
669 views
1 votes
1 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?

edited by

1 Answer

Best answer
1 votes
1 votes
There are nC2 pairs that may collide with probability each=1/m

i.e. (n2-n)/2m which is theta option C.
selected by

Related questions

0 votes
0 votes
1 answer
1
Ram Swaroop asked Jan 27, 2019
1,261 views
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search...
0 votes
0 votes
1 answer
3
0 votes
0 votes
1 answer
4