RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Peter Levart]

On 05/23/2013 09:02 PM, Brent Christian wrote:
> On 5/23/13 5:20 AM, Doug Lea wrote:
>> * Given that balanced trees are not used in WeakHashMap
>> or Hashtable, I wonder why the TreeNode etc classes are
>> not just nested inside HashMap (usable from subclass LinkedHashMap).
>> And if so, it would be simpler, faster, and less code-intensive
>> to declare TreeNode as a subclass of the internal Entry class.
>> Plus some further gymnastics to overcome the unfortunate
>> decision to make LinkedHashMap a subclass of HashMap.
>> Had you considered this?
>
> I definitely did.  I wanted a cleaner class hierarchy for 
> Entry/TreeNode, but LinkedHashMap makes it difficult, since its 
> Entries need extra before/after references.
>
> 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:

http://cr.openjdk.java.net/~plevart/jdk8-tl/HM.balancedTrees/merge_TreeNode_and_HashMap_Entry_into_same_object.patch

...this is a patch against your webrev.

Diamond inheritance is solved by making LinkedHashMap.Entry an interface 
and exposing get/set[Before,After] methods instead of before/after 
fields. The hierarchy is as follows:

class HashMap.Entry implements Map.Entry
class TreeNode extends HashMap.Entry
interface LinkedHashMap.Entry extends Map.Entry
class LinkedHashMap.EntryImpl implements LinkedHashMap.Entry
class LinkedHashMap.LinkedTreeNode extends TreeNode implements 
LinkedHashMap.Entry

I also added two factory methods to HashMap which are overriden in 
LinkedHashMap for constructing TreeNode/LinkedHashMap.LinkedTreeNode 
objects.

The TreeNode still contains the final 'entry' field, which is 
initialized to 'this' because there are a lot of references to it. These 
would have to be replaced in code, but would make the patch much larger 
and more difficult to grasp, so I left this exercise for later.

So what do you think? I know that with this patch, the access to 
before/after links in LinkedHashMap.Entry is not direct field access any 
more and goes through invokeinterface and can therefore be slower, 
because there are two implementing classes (LHM.EntryImpl and 
LHM.LinkedTreeNode). But on the other hand, the space savings can be 
noticeable if lots of buckets are transformed into TreeBins...

Regards, Peter