1
$\begingroup$

Under assumption that the hash function is uniform, we have worst-case performance for the search operation in a separate-chaining (e.g. java.util.HashMap) hashtable $O(\log n)$. Why? I cannot really understand this. If we have a uniformly-distributed hash values it should be the case that each hash bucket contains approximately the same number of elements.

Therefore, if we have load-factor (buckets_number/elements_number) say $0.5$, we guarantee the constant-time performance for search operations $O(2)$.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I deleted the Java example from your question, since it didn't actually seem relevant to what you were asking. If you disagree, you can click the "edited [whatever time] ago link" below the question and go back to your original version. $\endgroup$
    – David Richerby
    May 17, 2016 at 16:58

1 Answer 1

Reset to default
6
$\begingroup$

The load factor denotes the average expected length of a chain, therefore it is interesting for an average case analysis, not the worst case analysis. That's why on average you expect needing constant time for search operations.

In the worst case however, all your elements hash to the same location and are part of one long chain of size n. Then, it depends on the data structure used to implement the chaining. If you choose a sorted array, you can do binary search and the worst case complexity for search is O(log n). If you choose an unsorted list, you have a worst case of O(n) for search. Depending on your choice of data structure, the performance (worst and average case) of insert, delete and search changes.

According to Coding-Geek.com, Java 7's HashMap implementation uses a linked list (unsorted), but Java 8 uses a balanced binary tree instead. Of course, insert/delete/search in a balanced tree of size n has complexity O(log n).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Note that the ordering in the search trees is according to System.identityHashCode(Object x), which returns the value that Object.hashCode() would return; if the class doesn't overwrite hashCode(), then o.hashCode() == System.identityHashCode(o), and the secondary structures degenerate to lists. Balanced trees will degenerate if we only throw in the same key over and over again -- or they will store only one key, which is worse since you lose data that way. $\endgroup$
    – G. Bach
    May 17, 2016 at 15:50
  • $\begingroup$ Balanced trees will degenerate if we only throw in the same key over and over again -- or they will store only one key, which is worse since you lose data that way. What do you mean by that? If we throw in the same key, the hashtable will keep the latest one as that's a general contract for symbol tables. Could you expand a bit? $\endgroup$
    – user3663882
    May 17, 2016 at 16:22
  • 1
    $\begingroup$ Balanced trees in pure form does not support non-unique keys. Either they have to store them (which makes balancing more involving) or store counter (if you store simple values) or support list of objects of the same key. If by contract they store only the last data, all the previous is lost. $\endgroup$
    – Evil
    May 17, 2016 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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