As many of you know already, Java 9 brought us a set of immutable data structures – this was not a redesign of the Collections API but a set of new implementations with their own quirks.
Immutable Collections Since Java 9
For those of you that have not been paying attention, JDK9 featured JEP269: Convenience Factory Methods for Collections.
Which means that now we can create Set, List, Map instances using dedicated static factory methods like:
- List.of(1, 2, 3)
- Set.of(1, 2, 3)
- Map.of(“key”, “val”)
If you did not make it through the above proposal, you might be asking yourself what implementations do actually get returned, and what does convenience have to do with immutability?
It turns out that new collection factory methods are supposed to return immutable implementations of basic collection types, and those are completely new:
- List12
- ListN
- Map1
- MapN
- Set12
- SetN
However, they remain encapsulated and hidden, there’s no documented way of instantiating them directly.
Implementation Notes
All above-introduced types implement good old java.util.Collection interface, which means that just like with unmodifiable collection wrappers (Collections.unmodifiableList/Set/*), all mutating operations, unfortunately, throw new instances of UnsupportedOperationException.
However, immutability opens up another can of worms possible optimizations.
For example, an implementation of a collection containing a single element can be drastically simplified by… storing that single element in a field.
And this is exactly what’s happening internally with the new set of collections. For example. Lists containing max two elements are represented using the following class:
static final class List12<E> extends AbstractImmutableList<E>
implements Serializable {
@Stable
private final E e0;
@Stable
private final E e1;
// ...
@Override
public int size() {
return e1 != null ? 2 : 1;
}
@Override
public E get(int index) {
if (index == 0) {
return e0;
} else if (index == 1 && e1 != null) {
return e1;
}
throw outOfBounds(index);
}
// ...
}It gets a bit more old-school when representing collections containing more elements – for example, the internal implementation of ListN resembles a classical ArrayList.
Map1’s implementation is not surprising as well – if we know that the map instance will always contain only a single key-value pair, then we can just store it directly using two fields:
static final class Map1<K,V> extends AbstractImmutableMap<K,V> {
@Stable
private final K k0;
@Stable
private final V v0;
@Override
public boolean containsKey(Object o) {
return o.equals(k0); // implicit nullcheck of o
}
@Override
public boolean containsValue(Object o) {
return o.equals(v0); // implicit nullcheck of o
}
}And now, it gets really interesting if we have a closer look at MapN implementation, this one internally… stores all pairs in a single Object[] with interleaved keys and values:
static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
// ...
@Stable
final Object[] table; // pairs of key, value
@Stable
final int size; // number of pairs
// ...
}Limitations
By any means, below are not bugs, but consciously applied design choices – but it doesn’t change the fact that we should be aware of them – that could potentially save us hours of debugging and/or at least a few extra points while trying to win a sneaky coding competition.
Immutable Collections vs Null
It turns out that all collections created using factory methods, don’t support null values.
assertThatThrownBy(() -> List.of(1, null)) .isInstanceOf(NullPointerException.class); assertThatThrownBy(() -> Set.of(1, null)) .isInstanceOf(NullPointerException.class);
They even throw exceptions when you provide null as argument for the contains()/indexOf() methods (!!!):
assertThatThrownBy(() -> Set.of(42).contains(null)) .isInstanceOf(NullPointerException.class); assertThatThrownBy(() -> List.of(42).contains(null)) .isInstanceOf(NullPointerException.class); assertThatThrownBy(() -> List.of(42).indexOf(null)) .isInstanceOf(NullPointerException.class);
The same applies to Map for both keys and values:
assertThatThrownBy(() -> Map.of(1, null)) .isInstanceOf(NullPointerException.class); assertThatThrownBy(() -> Map.of(null, "foo")) .isInstanceOf(NullPointerException.class);
Implementation hints can be found in MapN’s Javadocs:
An array-based Map implementation.
There is a single array “table” that contains keys and values interleaved: table[0] is kA, table[1] is vA, table[2] is kB, table[3] is vB, etc. The table size must be even.
It must also be strictly larger than the size (the number of key-value pairs contained in the map) so that at least one null key is always present.
As we can see, nulls are used internally to represent absence of values and there’s no easy way to distuinguish them from values that are meant to be null.
// returns index at which the probe key is present; or if absent,
// (-i - 1) where i is location where element should be inserted.
// Callers are relying on this method to perform an implicit nullcheck
// of pk.
private int probe(Object pk) {
int idx = Math.floorMod(pk.hashCode(), table.length >> 1) << 1;
while (true) {
@SuppressWarnings("unchecked")
K ek = (K)table[idx];
if (ek == null) {
return -idx - 1;
} else if (pk.equals(ek)) {
return idx;
} else if ((idx += 2) == table.length) {
idx = 0;
}
}
}@Override
@SuppressWarnings("unchecked")
public V get(Object o) {
if (size == 0) {
Objects.requireNonNull(o);
return null;
}
int i = probe(o);
if (i >= 0) {
return (V)table[i+1];
} else {
return null;
}
}Immutable Sets vs Uniqueness
The main value proposition of sets is the uniqueness of stored elements:
var set = new HashSet<Integer>(); set.add(42); set.add(42); System.out.println(set); // [42]
Having said that, what would you expect to happen if we did the same just using a factory method?
Let’s see by ourselves:
var set = Set.of(42, 42); // IllegalArgumentException!
So, as you can see, these can be used only when providing unique elements. Which is a bit unfortunate because these methods can be used with arrays of arbitrary values which might end up with nasty runtime issues so better be aware of it:
var set = Set.of(input); // IllegalArgumentException!
Key Takeaways
- Nowadays, Java features a set of immutable collections, all of them accessible only through static factory methods of() that can be found in corresponding classes.
- All JDK9 immutable collections don’t support null values.
- Calling the contains()/indexOf() methods with a null ends up in a NullPointerException being thrown
- Creating a Set instance using a non-unique set of elements ends up in an IllegalArgumentException being thrown.
