RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Peter Levart]

On 05/26/2013 01:34 PM, Doug Lea wrote:
> 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.

Hi Doug,

Clever idea. So your common TreeNode would extend LinkedHashMap.Entry.


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

That would certainly be the fastest and most optimal approach, but the 
price?


Regards, Peter