CODEWITHSUNDEEP
algorithmhash
venkysmarty
venkysmarty

Reputation: 11441

Regarding linear probing in hashing

In linear probing hashing, if clustering is not a problem, We will assume a very large table and that each probe is independent of the previous probes. These assumptions are satisfied by a random collision resolution strategy. First, we derive the expected number of probes in an unsuccessful search. This is just the expected number of probes until we find an empty cell. Since the fraction of empty cells is (1 - (N/M)), where N is number of elements and M is hash table size. the number of cells we expect to probe is 1/(1 - (N/M)). The number of probes for a successful search is equal to the number of probes required when the particular element was inserted.

My question is how do we got number of cells we expect to proble is 1/(1-(N/M)) in above text.

Thanks!

Upvotes: 2

Views: 2093

Answers (1)

Omri Barel
Omri Barel

Reputation: 9490

Probing works roughly like this: you have probability p for success, and you keep trying until you succeed. This means that you're dealing with the geometric probability distribution, so the expected number of attempts until you succeed is 1/p.

In this case, p=1-(N/M), so the expected number of attempts is 1/(1-(N/M)).

Upvotes: 3

Related Questions