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.w...@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
