Re: 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);