A certain hash table uses external chaining, and is resized each time its load factor exceeds 3. Also, if an addition does not cause the load factor to exceed 3, but does cause some bucket to exceed 6 elements, the table is given a new hashing function and the elements of the table are redistributed in accordance with this new function. Suppose that (somehow) this new hashing function always happens to distribute the existing keys evenly (≤ 3 per bucket) as long as the addition did not exceed the load factor. If the table intially has B buckets and 2B values, how long in the worst case does it take to add an additional B values? Assume that comparisons and the hash functions all take constant time.

I am not sure how to approach this problem

  • $\begingroup$ Where did you encounter this task? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Dec 16, 2021 at 4:54
  • $\begingroup$ We're not looking for posts that are just the statement of an exercise-style task. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. I notice that I've given you similar feedback before: cs.stackexchange.com/questions/145770/… $\endgroup$
    – D.W.
    Dec 16, 2021 at 4:55


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.