please review draft JEP: Convenience Factory Methods for Collections

David M. Lloyd david.lloyd at
Fri Jul 18 23:41:14 UTC 2014

On 07/18/2014 06:36 PM, Stuart Marks wrote:
> On 7/18/14 2:17 AM, Michael Kay wrote:
>> On 18 Jul 2014, at 10:09, Wang Weijun < at> wrote:
>>> A .with(k, v) to create a new immutable map with an extra pair.
>> Yes, that's the same as my A.add(k,v) -> A proposal.
>> Works whether A is mutable or immutable.
> I don't think we want to have a Map.add(k,v) instance method (or default
> method) for immutable maps or for constructing them.
> For a fast, compact, immutable map implementation, the only way to
> implement Map.add() would be to copy the entire contents plus the
> additional pair into a new map. For creating maps with small numbers of
> entries, this isn't really a big deal, but if you have something like
>      Map.of()
>         .add(k0, v0)
>         .add(k1, v1)
>           ...
>         .add(kN, vN);
> this would result in O(N^2) performance and space allocation, though
> most of the allocated space is garbage.

Adding another alternative, instead of producing intermediate maps which 
are copied at each step for the sake of maintaining O(1) lookup, this 
approach could instead create a linked-list-of-pairs which would be O(n) 
for lookups, but also O(n) for space - you could then efficiently feed 
that to a "real" map constructor, especially if each "map" also 
implemented Map.Entry, which would make an iterator particularly 
lightweight, making the overall cost for, say, a HashMap be O(n).

Not sure it's the "right" approach, just throwing it out there as a 
random Friday thought.


More information about the core-libs-dev mailing list