RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Doug Lea]

On 05/27/13 04:57, Alan Bateman wrote:

> Any objection if we move ahead with what Brent has now, at least as first step?
> There are are other follow-on changes, the removal of String hash32 field/method
> particular, that we are anxious to get in.
>

Yes, please do.

In which case, here's a problem that needs fixing in the current
version:

The splitTreeBin method can only handle doubling of tables.
But it is possible from current HashMap.putAll to skip a doubling
step. This almost never happens in practice, but must be
avoided by replacing (HashMap.java, approx line 700):

         if (numKeysToBeAdded > threshold) {
             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
             if (targetCapacity > MAXIMUM_CAPACITY)
                 targetCapacity = MAXIMUM_CAPACITY;
             int newCapacity = table.length;
             while (newCapacity < targetCapacity)
                 newCapacity <<= 1;
             if (newCapacity > table.length)
                 resize(newCapacity);
             }
with:

          if (numKeysToBeAdded > threshold && table.length < MAXIMUM_CAPACITY)
              resize(table.length * 2);