please review draft JEP: Convenience Factory Methods for Collections

[Stuart Marks]

On 7/18/14 4:41 PM, David M. Lloyd wrote:
> On 07/18/2014 06:36 PM, Stuart Marks wrote:
>>      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.

... now being analyzed in the cold, harsh light of a Monday morning. Er, 
afternoon. :-)

The main difficulty here is if the type returned by add() is a Map, it has to 
obey all the requirements of the Map contract. That means that somebody has to 
enforce the uniqueness constraint of the keys. This will affect things like 
iterating over the map or asking for its size, and so forth. Either the extra 
work is done at addition time or later when certain results require respecting 
uniqueness.

If add() returns something other than a Map, such as a temporary data structure 
later used to construct a Map, then pushing the items onto a linked list is 
quite a sensible idea. (Maybe a linked list of arrays, to reduce per-element 
overhead.) We don't care if the keys are unique when they're being added, since 
that'll be taken care of later at map construction time. But this is essentially 
a builder, not incremental additions to a Map.

s'marks