I have the below problem, which I've already been given the answer to, I'm just trying to understand why the answer is the way it is. I've modified the language of the problem significantly so it shouldn't be picked up by any search engine for the actual problem (tested this in Google).

You have a hash table of size m where n elements are occupied. Each index in the table has an equal probability of being produced by the hash and rehash functions, and the nature of the hash/rehash function is not relevant to this question. Each time a hash or rehash is attempted, a comparison must take place against the index to determine if the value can be added to the hash table (meaning that if no collisions take place, 1 comparison is made). Show that the average number of comparisons needed to insert a new element is $\frac{m + 1}{m-n+1}$. You can assume that if a collision happens at a given index, rehashing will not collide with that particular index again. It’s recommended you start by counting the number of comparisons for each item as you go along.

I could be missing something stupidly obvious, but the solution states to let the table size be $m+1$ rather than $m$, and that because the number of comparisons will be $\frac{m}{m-n}$, the end result is as shown in the problem. Nothing else is given by way of explanation.

1) Why is the number of comparisons, for a given $n$, $\frac{m}{m-n}$? I simply don't see it.
For example, for $n = 4$, there are 3 items in the table. The initial hash could collide with 0, 1, 2, or all 3 of the items, resulting in 1, 2, 3, or 4 comparisons, respectively. If $m = 10$, the formula says that there would be $\frac{11}{7} = 1.57$ comparisons on average, but I don't see how the formula arrives at that. I tried calculating the weighted average of the possible comparisons but was advised by my professor not to go that route, as it wouldn't get me to the given formula.

2) What's the advantage of letting the size of the table be $m+1$ instead of $m$?

I don't have a tremendous math background, plainspoken explanations would be helpful.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.