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

Popular posts from this blog

google chrome - Developer tools - How to inspect the elements which are added momentarily (by JQuery)? -

angularjs - Showing an empty as first option in select tag -

php - Cloud9 cloud IDE and CakePHP -