improving java 8's implement to hash map using avl tree Java 8 got a new implement to hashmap (using a tree). I have understand that in the worst case, it may be O(n) for lookup.

Will changing this implement to an avl tree change this O(n) case to something better (without changing the other complexities)?

here are some notes on it:


  This map usually acts as a binned (bucketed) hash table, but
    when bins get too large, they are transformed into bins of
    TreeNodes, each structured similarly to those in
    java.util.TreeMap. Most methods try to use normal bins, but
    relay to TreeNode methods when applicable (simply by checking
    instanceof a node).  Bins of TreeNodes may be traversed and
    used like any others, but additionally support faster lookup
    when overpopulated. However, since the vast majority of bins in
    normal use are not overpopulated, checking for existence of
    tree bins may be delayed in the course of table methods.
  
  Tree bins (i.e., bins whose elements are all TreeNodes) are
    ordered primarily by hashCode, but in the case of ties, if two
    elements are of the same "class C implements Comparable",
    type then their compareTo method is used for ordering. (We
    conservatively check generic types via reflection to validate
    this -- see method comparableClassFor).  The added complexity
    of tree bins is worthwhile in providing worst-case O(log n)
    operations when keys either have distinct hashes or are
    orderable, Thus, performance degrades gracefully under
    accidental or malicious usages in which hashCode() methods
    return values that are poorly distributed, as well as those in
    which many keys share a hashCode, so long as they are also
    Comparable. (If neither of these apply, we may waste about a
    factor of two in time and space compared to taking no
    precautions. But the only known cases stem from poor user
    programming practices that are already so slow that this makes
    little difference.)
This page on Oracle's website says:


  The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins containing a large number of colliding keys improve performance by storing their entries in a balanced tree instead of a linked list. This JDK 8 change applies only to HashMap, LinkedHashMap, and ConcurrentHashMap.


"Balanced tree" typically means either an AVL tree or a red-black tree. I would expect red-black tree, since TreeMap is already implemented as a red-black tree, and this Stack Overflow answer agrees. In that case, using an AVL tree wouldn't change much because AVL trees and red-black trees have basically the same complexity characteristics: search, insertion, and deletion are all worst case $O(\log n)$.

If the worst case for lookup in Java 8 HashMaps is $O(n)$, I'm not seeing how it could be the tree's fault. The motive behind this change is that HashMap buckets normally use linked lists, but linked lists are worst case $O(n)$ for lookup. Ordinary binary search trees have pathological cases where they become $O(n)$, but red black trees are specifically designed to prevent these cases. In a HashMap with linked lists, if you have a really really awful hash function, you could end up with all the items hashing to the same bucket and get $O(n)$ lookup, but it seems like with this red-black tree scheme, even if all the items hashed into the same bucket, you should get $O(\log n)$ lookup.