please review draft JEP: Convenience Factory Methods for Collections
David M. Lloyd
david.lloyd at redhat.com
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 <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
> .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