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)
$\begingroup$
$\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$– greybeardAug 18, 2020 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$– GlorfindelAug 18, 2020 at 5:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\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$ Aug 17, 2020 at 20:58