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

Doug Lea dl at cs.oswego.edu
Sun May 26 11:34:04 UTC 2013

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

More information about the core-libs-dev mailing list