-1
$\begingroup$

Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the hashtable)

$\endgroup$
2
  • $\begingroup$ Just delete your post if&when you want it deleted. With a question, consider if others found it useful (gave upvotes) and whether there are well-regarded answers. $\endgroup$ – greybeard Aug 18 '20 at 0:30
  • $\begingroup$ Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 4.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work? $\endgroup$ – Glorfindel Aug 18 '20 at 5:48
1
$\begingroup$

Assume you have strings that you hash to a 64 bit hashcode. Since the number of possible strings is unlimited, it is guaranteed possible to have n strings that all have the same hashcode. Think about what your hashtable will do in that case.

$\endgroup$
1
  • $\begingroup$ You said it: If n items all have the same hash code, then in order to find one of these items, you may have to visit all the items with the same hash code, that is Theta(n). $\endgroup$ – gnasher729 Aug 17 '20 at 20:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.