Expected number of slots being empty while hashing.

3Comments
shivani @shivani1234
20 Aug 2017 10:33 am
  • Probability that first slots is empty = (1-1/k)n //this will happen when no key hashes to slot1
  • Expected no. of slots that ends up not being empty = no. of slots * P(slot that ends up not being empty)
    P(slot that ends up not being empty) = 1-P(slot that ends up  being empty)
    =1-k(1-1/k)n 
    Expected no. of slots that ends up not being empty=k * [1-k(1-1/k)n]
set2018 @setgate
20 Aug 2017 11:29 am

Shivani pls give any example for this :(

shivani @shivani1234
20 Aug 2017 07:45 pm
i h(i)
0  
1 11,321,41
2 22,02
3 83
4 94, 54

wher, h(i)= i mod 5