Suppose we are given an empty hash table of size $n$, where collisions are resolved by re-hashing (open addressing).

Next, $n/2$ items are randomly inserted into the table using a hash function that provides uniform distribution of hash values.

On average, how many operations are needed to randomly add additional $n/2$ items to the above table? How would I approach to such calculations?


  • $\begingroup$ Wouldn't it depend on how the re-hashing is done? To check that I understand correctly: First you add $n/2$ items, and you want to know the number of operations required if you then add another $n/2$ items? (Presumably you're looking for the expected value of that number?) $\endgroup$ – joriki Jul 3 '15 at 7:52
  • $\begingroup$ Yes, thats correct. $\endgroup$ – Boris Ablamunits Jul 3 '15 at 8:19
  • $\begingroup$ So will you tell us how the re-hashing is done? $\endgroup$ – joriki Jul 3 '15 at 8:54
  • $\begingroup$ Unfortunately it is not specified in the problem. I was thinking (although I am not sure at all) of somehow trying to base an answer on the fact that if a hashing table is of size m, and already contains k items - the expected number of operations when inserting the k+1 item is (m+1)/(m-k+1). I am not sure it is the right direction and im finding it hard to get my head around it. $\endgroup$ – Boris Ablamunits Jul 3 '15 at 9:12
  • $\begingroup$ Why isn't it $m/(m-k)$? For the $m$th item, it should be $m$, not $m+1$, no? $\endgroup$ – joriki Jul 3 '15 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.