improving java 8's implement to hash map using avl tree

Question

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

Answer 1

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.