RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Doug Lea]

Back to this. (which applies to ConcurrentHashMap, under review).

On 05/24/13 07:18, Doug Lea wrote:
> On 05/23/13 16:47, Jeff Hain wrote:

>> Implementing some RB-tree I found out that
>>
>> a lot of the null checks from CLR code could be removed from balancing
>> operations.
>
> Yes and no. Some of those not logically needed prevent infinite looping in
> the case of concurrent interference.

But still, there are several that can go away without forcing
so much rare-trap handling. I updated the analogous
code in ConcurrentHashMap version to omit a few of them, and also
retained in this version an internal checkInvariants method that
can be used to further refine. (This is possibly useful to
other developers, so worth leaving in rather than pulling out
each time I update this code.) I also left asserts to it enabled
in a couple of spots to allow more testing with "-ea".  If/when I
offer an update to plain HashMap, I'll also include.


> it seemed that null checks could actually be removed for all remaining calls
> to leftOf/rightOf/setColor (not for getColor), but since I didn't figure out
> why I didn't  touch these.
>

Right. TreeMap could use some similar improvement someday. That code
was based on red-black algorithms that assume the tree is expanded such
that all null links go to dummy nodes, which I long ago
emulated with these calls in some classes I wrote that in turn
got adapted in TreeMap and elsewhere.

-Doug