algorithm - Why the probability of an empty slot preceded by i full slots getting filled next is (i + 1)/m in context of Primary clustering in Hashing? -
why probability of empty slot preceded full slots getting filled next (i + 1)/m in context of primary clustering in hashing open addressing collision resolution technique , linear probing? excerpt introduction algorithms clrs "long runs of occupied slots build up, increasing average search time. clusters arise because empty slot preceded full slots gets filled next probability (i + 1)/m. long runs of occupied slots tend longer,and average search time increases." please help.
i think got answer it.
for empty slot (say j) preceded full slots filled next element should hash of slots or slot j. book says:
we shall assume given element equally hash of m slots, independently of other element has hashed to.
i.e. probability element hashes slot k 1/m.
so, required probability
( 1/m + 1/m + ... times ) + 1/m {for slot j} = (i+1)/m
Comments
Post a Comment