Map Tutorial

Map Tutorial

The Javimmutable library provides an IMap 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. Three implementations are provided.

Nulls are not permitted as keys but can be used as values. IMap uses assign() instead of put() and delete() instead of remove() so that when converting code from java.util.Map to IMap the compiler will find all of the places that you need to replace a simple method call with an assignment.

IMaps.hashed() 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)

IMaps.sorted() 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 Comparator class. (Care must be taken to write robust and correct implementations of Comparator to ensure the tree operates as expected.)

IMap<Integer, Integer> hmap = IMaps.hashed();
hmap = hmap.assign(10, 11).assign(20, 21).assign(30, 31).assign(20, 19);

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

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

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

get and find

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 IMaps allow nulls as values the get() method's result can be ambiguous. IMap provides a find() method which is similar to get() but always returns a non-null Maybe 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());
// since the Maybe is empty we get the default value
assertEquals(Integer.valueOf(-1), hmap2.find(20).get(-1));

assertEquals(null, hmap2.get(80));
assertEquals(false, hmap2.find(80).isEmpty());
// the Maybe is full and value is null
assertEquals(null, hmap2.find(80).get(-1));

IMap 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 IMap to access values. getMap() has very low overhead since contents of the IMap are not copied when creating the Map. Use this method when you need to share the IMap's contents with code that only understands java.util.Map.

Sorted Maps

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.

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

Ordered Maps

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

IMap<Integer, Integer> omap = IMaps.ordered();
omap = omap.assign(30, 31).assign(20, 21).assign(10, 80).assign(20, 19);
assertEquals(Arrays.asList(30, 20, 10), new ArrayList<>(omap.getMap().keySet()));
assertEquals(Arrays.asList(31, 19, 80), new ArrayList<>(omap.getMap().values()));