RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Doug Lea]

On 05/26/13 07:02, Peter Levart wrote:

>>
>> I couldn't work out a TreeNode class that could be used by both HashMap and
>> LinkedHashMap, since LHM would need a TreeNode derived from
>> LinkedHashMap.Entry, not HashMap.Entry.
>>
>> So instead I used composition, where TreeNode has-a [Linked]HashMap.Entry.
>
> Hi Brent,
>
> It's unfortunate, because composition increases memory footprint. Here's my
> attempt at merging HashMap.Entry with TreeNode into same object:
>

I had a similar thought: Even if you waste space for the
before/after links in TreeNode, you come out ahead,
and don't penalize LinkedHashMap as much. I'm in the midst
of exploring this.

Another alternative that arises each time deep HashMap
surgery is contemplated is that you can almost completely ignore the
HashMap implementation inside LinkedHashMap, which is
likely to speed both up at the price of more code.

-Doug