please review draft JEP: Convenience Factory Methods for Collections (original) (raw)

Michael Kay mike at saxonica.com
Sat Jul 19 08:27:31 UTC 2014

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. this would result in O(N^2) performance and space allocation, though most of the allocated space is garbage.

Only with a very naive implementation of immutable maps! With a HashTrie, or RedBlack tree, of Finger tree, adding a new entry can be O(log(N)) in both time and space.

Of course, one could avoid the copying overhead by making the immutable maps persistent (i.e., sharing their unmodified portions) but that is an entirely different discussion.

Well, I think immutable maps are a different discussion anyway, but surely any worthwhile implementation of immutable maps should make it easy and fast to create a new immutable map by adding an entry?

I kind of think you're after the ability to chain the method calls.

Yes.

This is certainly convenient and has no arbitrary restrictions on the number of elements. To do something like this we'd put the chainable methods on a builder instead:

Map.builder() .add(k0, v0) .add(k1, v1) ... .add(kN, vN) .build();

Seems an unnecessary complication to me...

For a mutable map it's just: add(k,v) {put(k,v); return this}.

For an immutable map using something like a HashTrie, creating a small map using say 5 add() operations is not going to take significantly longer than the builder approach; you can always provide the builder as well for those who want ultimate performance.

Michael Kay Saxonica

More information about the core-libs-dev mailing list