RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees (original) (raw)

Doug Lea dl at cs.oswego.edu
Mon May 27 11:41:35 UTC 2013

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

More information about the core-libs-dev mailing list