Old Map Tutorial

The Javimmutable library provides a JImmutableMap interface that is very similar to java.util.Map. Like other immutable interfaces all of the methods that modify the map return a new map as their result. The old and new maps share almost all of their structure in common to minimize memory and CPU overhead. Two implementations are provided. Nulls are not permitted as keys but can be used as values. Javimmutable uses assign() instead of put() and delete() instead of remove() so that when converting code from java.util.Map to JImmutableMap the compiler will find all of the places that you need to replace a simple method call with an assignment.

JImmutables.map() uses a hash mapped integer trie to store its values. This provides O(log32(n)) performance for all operations. (see Comparative Performance) Values within the map are stored in an ordering based on the hash codes of the keys so no guarantee is made about what order an Iterator or Stream will return entries. (see Hash Keys for advice on selecting keys for maps)

JImmutables.sortedMap() uses a balanced binary tree with a Comparator object to store its values. This provides O(log2(n)) performance for all operations. Values within the map are stored in sorted order based on the Comparator used by the tree. Usually you will use objects which implement the Comparable interface as keys and when you do so the keys will be stored in their natural ordering. When you need to use keys that do not implement Comparable or if you need to use a different ordering you can create the tree with your own Comparable class. (Care must be taken to write robust and correct implementations of Comparable to ensure the tree operates as expected.)

JImmutableMap<Integer, Integer> hmap = JImmutables.map();
hmap = hmap.assign(10, 11).assign(20, 21).assign(30, 31).assign(20, 19);

JImmutableMap<Integer, Integer> hmap2 = hmap.delete(20).assign(18, 19);

assertEquals(11, hmap.get(10));
assertEquals(19, hmap.get(20));
assertEquals(31, hmap.get(30));

assertEquals(11, hmap2.get(10));
assertEquals(19, hmap2.get(18));
assertEquals(null, hmap2.get(20));
assertEquals(31, hmap2.get(30));

The get() method operates in the same manner as java.util.Map.get(). If the map does not contain a value for the specified key null is returned. Since JImmutableMaps allow nulls as values the get() method's result can be ambiguous. JImmutableMap provides a find() method which is similar to get() but always returns a non-null Holder object that can be used to determine unambiguously whether or not a value was found matching the key.

hmap2 = hmap2.assign(80, null);
assertEquals(null, hmap2.get(20));
assertEquals(true, hmap2.find(20).isEmpty());
// hmap2.find(20).getValue() would throw since the Holder is empty

assertEquals(null, hmap2.get(80));
assertEquals(false, hmap2.find(80).isEmpty());
assertEquals(null, hmap2.find(80).getValue());

JImmutableMap includes a getMap() method that returns an object implementing java.util.Map. The returned Map is immutable (set, remove, etc throw UnsupportedOperationException) and uses the original JImmutableMap to access values. getMap() has very low overhead since contents of the JImmutableMap are not copied when creating the Map. Use this method when you want to share the JImmutableMap's contents with code that only understands java.util.Map.

Sorted maps work exactly the same way as hash maps but their iterators provide access to entries in sorted order based on their keys. In the example below the keySet() and values() methods provide their contents sorted based on the order of the corresponding keys in the map.

JImmutableMap<Integer, Integer> smap = JImmutables.sortedMap();
smap = smap.assign(10, 80).assign(20, 21).assign(30, 31).assign(20, 19);
assertEquals(Arrays.asList(10, 20, 30), new ArrayList<Integer>(smap.getMap().keySet()));
assertEquals(Arrays.asList(80, 19, 31), new ArrayList<Integer>(smap.getMap().values()));