We use a simple uniform hash function to insert 300 keys into two tables of size 1000, we use chaining at one table and linear probing at the other. We are given that the keys were mapped into 290 different cells. What is the expected time of unsuccessful search in each case?

I think that the expected time will be 300/1000 at the chaining table, and $0.5(1+(1-3/10)^2)$ at the linear probing table. Is this correct? I'm not sure how the fact that the keys were mapped into 290 different cells may change the answer.

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jul 29 '17 at 11:48
  • $\begingroup$ (Incidentally, if you ask someone else to check your work, you should probably at minimum describe your reasoning and how you got that answer.) $\endgroup$ – D.W. Jul 29 '17 at 11:48

Your Answer

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