RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

Brent Christian brent.christian at oracle.com
Mon May 13 16:48:03 UTC 2013


Please review my changes for 8005698 : Handle Frequent HashMap 
Collisions with Balanced Trees.

For HashMap and LinkedHashMap, we would like to duplicate the technique 
(and some of the code) that the latest ConcurrentHashMap[1] uses for 
handling hash collisions: use of balanced trees to store map entries in 
hash bins containing many collisions.

Webrev is here:

Some high-level details copied from the JEP[2]:

Earlier work in this area in JDK 8, namely the alternative 
string-hashing implementation[3], improved collision performance for 
string-valued keys only, and it did so at the cost of adding a new 
(private) field to every String instance.

The changes proposed here will improve collision performance for any key 
type that implements Comparable. The alternative string-hashing 
mechanism, including the private hash32 field added to the String class, 
can then be removed.

The principal idea is that once the number of items in a hash bucket 
grows beyond a certain threshold, that bucket will switch from using a 
linked list of entries to a balanced tree.

We will not implement this for the Hashtable class - some legacy code 
that uses it is known to depend upon iteration order. Instead, Hashtable 
will be reverted to its state prior to the introduction of the 
alternative string-hashing implementation, and will maintain its 
historical iteration order.

We also will not implement this technique in WeakHashMap. An attempt was 
made, but the complexity of having to account for weak keys resulted in 
an unacceptable drop in microbenchmark performance. WeakHashMap will 
also be reverted to its prior state.


2. http://openjdk.java.net/jeps/180
3. http://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/43bd5ee0205e

More information about the core-libs-dev mailing list