please review draft JEP: Convenience Factory Methods for Collections

[David M. Lloyd]

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 <weijun.wang at oracle.com> 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.

-- 
- DML