# Understanding hashtable performance in the worst-case

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)$.

• 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. May 17 '16 at 16:58

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).
• 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. May 17 '16 at 15:50