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

Peter Levart peter.levart at gmail.com
Sun May 26 12:08:12 UTC 2013

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

More information about the core-libs-dev mailing list