RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Doug Lea]

On 05/31/13 10:10, Alan Bateman wrote:

> Assuming Doug and Mike are okay with this then I suggest we try to get it into
> jdk8/tl soon so that it has a few days bake time before Lana grabs the changes
> from jdk8/tl for b94. I think Mike is going to sponsor this.
>

On cross-checking with ConcurrentHashMap, all looks OK except that
it should include a fix for a problem introduced once when changing
comparison orders and not picked up until recently retesting CHM. (sorry.)
Here's a diff against webrev 0.3

*** HashMap.java~       Fri May 31 13:58:38 2013
--- HashMap.java        Sat Jun  1 12:52:11 2013
***************
*** 490,499 ****
                            (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) 
{                      // assert pk != null;
                       TreeNode r, pl, pr; // check both sides
!                     if ((pr = p.right) != null && h >= pr.entry.hash &&
                           (r = getTreeNode(h, k, pr, cc)) != null)
                           return r;
!                     else if ((pl = p.left) != null && h <= pl.entry.hash)
                           dir = -1;
                       else // nothing there
                           break;
--- 490,499 ----
                            (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) 
{                      // assert pk != null;
                       TreeNode r, pl, pr; // check both sides
!                     if ((pr = p.right) != null
                           (r = getTreeNode(h, k, pr, cc)) != null)
                           return r;
!                     else if ((pl = p.left) != null)
                           dir = -1;
                       else // nothing there
                           break;
***************
*** 534,540 ****
                   else if (cc == null || comparableClassFor(pk) != cc ||
                            (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) 
{                      TreeNode r, pr;
!                     if ((pr = p.right) != null && h >= pr.entry.hash &&
                           (r = getTreeNode(h, k, pr, cc)) != null)
                           return r;
                       else // continue left
--- 534,540 ----
                   else if (cc == null || comparableClassFor(pk) != cc ||
                            (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) 
{                      TreeNode r, pr;
!                     if ((pr = p.right) != null &&
                           (r = getTreeNode(h, k, pr, cc)) != null)
                           return r;
                       else // continue left