Introduction
The Apache Commons Collections has utilities, new interfaces, and implementations for working with collections. In this post, we will explore one such utility, i.e., Apache Commons BidiMap. BidiMap stands for a bidirectional map. It is an interface using which we can perform a lookup on a map in either direction, i.e., key to value (the usual way) or value to key.
Apache Commons Collections
The Apache Commons Collections package has types that extend and augment the Java Collections Framework. To import the Apache Commons Collections library into your application or project to use the BidiMap interface and the implementing classes, for a Maven project, you can import it as:
<!-- https://mvnrepository.com/artifact/org.apache.commons/commons-collections4 -->
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
<version>4.4</version>
</dependency>
You can replace 4.4 with the latest version available.
For a Gradle project, you can import Apache Commons Collections as:
implementation 'org.apache.commons:commons-collections4:4.4'
Bidirectional map in Java
Sometimes, we have a need to lookup into a Java map in the reverse, i.e., given a value, we want to know the key mapped to that value. Since a normal map doesn’t provide an API to achieve this, we would have to resort to search the entire map whose time complexity is O(n). One way to do this is,
public Optional<String> findKey(Map<String, String> map, String targetValue) {
return map.entrySet()
.stream()
.filter(e -> e.getValue().equals(targetValue))
.map(Map.Entry::getKey)
.findFirst();
}
Similarly, if we also want to remove an entry with a given key, we have to implement a Bidirectional map ourselves. It quickly gets out of hand (with respect to complexity) as we also have to make sure to maintain the contents of both map in-sync, i.e., the normal map and the reverse map.
public class MyBidirectionalMap<K, V> {
private Map<K, V> mainMap;
private Map<K, V> reverseMap;
// put, remove methods should operate on (and maintain) both maps
}
We have to implement not only the usual get, put, putAll and remove methods, but have to make sure both maps’ entries are maintained when entries are removed via keySet and entrySet as well.
Bidirectional Map in Apache Commons Collections
Using the BidiMap interface in the Apache Commons Collections (org.apache.commons.collections4 namespace) will save us a lot of trouble. The BidiMap interface defines a map that allows to do bidirectional lookup between key and values. In other words, the BidiMap provides an inverse map view which enables access to both directions of the BidiMap.
The best thing is that it extends the java.util.Map interface, so we can use the BidiMap wherever we need a Java map.
NOTE: The only restriction is that there should be a 1:1 relation between keys and values and hence multiple keys cannot map to the same value. This is because when we invert a map of type Map<K, V>, we have to end up with a map of type Map<V, K>. If we have multiple keys mapped to the same value, this won’t be possible (on inversion, it will give us Map<V, List<K>>).
BidiMap interface in Apache Commons Collections
Let us now look at the BidiMap interface.
BidiMap interface hierarch
The BidiMap has five superinterfaces viz., Get<K,V>, IterableGet<K,V>, IterableMap<K,V>, Map<K,V>, and Put<K,V>. Shown below is the hierarchy among the interfaces.
The BidiMap extends an interface called IterableMap. An IterableMap extends the Java Map (java.util) and two other interfaces, Put and IterableGet.
The Put interface is part of Apache Collections, which has the “write” subset of methods from a Java map (clear(), put() and putAll()). The IterableGet interface extends an interface called Get which is the “read” subset of the Java map methods like get(), containsKey(), containsValue(), size() etc.,
The IterableGet has a method called mapIterator().
MapIterator<K, V> mapIterator();
A MapIterator extends Iterator<K> and acts as an iterator over a map. In certain cases, it can be more efficient (and convenient) to use this rather than an entrySet() to iterate over the map entries. This is because the implementation can provide an efficient implementation to iterate over the map entries (keys and values) without creating Map.Entry objects.
Since it implements an Iterator<K>, calling hasNext() tells if there are more entries (keys) in the map remaining to be iterated on and next() returns the next key.
To get the key or the value, it has getKey() and getValue() methods. We can call these only after calling next(). Like in a normal Iterator, calling next(), will move the iterator to the next entry and returns the key of the next entry. Then we can call getKey() and getValue() any number of times to get the key and value of the current entry pointed to by the iterator.
It also supports remove() to remove the last returned key from the underlying map and setValue to set a new value associated with the current key. These operations must be supported by the underlying map.
There are two interfaces which extend the BidiMap interface (i.e., subinterfaces) viz., SortedBidiMap and OrderedBidiMap which we I’ll cover later in this post. The BidiMap interface has four implementations which we will explore in this post:
- DualHashBidiMap - uses two HashMaps to implement BidiMap.
- DualLinkedHashBidiMap - uses two LinkedHashMaps to implement BidiMap.
- DualTreeBidiMap - uses two TreeMaps to implement SortedBidiMap.
- TreeBidiMap - red-black tree implementation of OrderedBidiMap.
The methods on a BidiMap
Since a BidiMap extends a Map, we have all the methods available on a Java map in BidiMap as well. To support mapping in both directions, it provides some additional methods.
K getKey(Object value)- It takes a value and returns the key associated (mapped) to that value. If the map doesn’t have any entry with that value, it returns a null.K removeValue(Object value)- It takes the value to be removed and removes the mapping (key-value pair) associated with this value. It returns the key of the entry it removed (null if there was no removal, i.e., map didn’t have an entry with the passed value).Set<K> values()- This is similar to the values() method on a Map, but since the map has 1:1 relation between keys and values, this method returns the set of values (a Set). This set is backed by the map.BidiMap<V,K> inverseBidiMap()- This is the most important method offered by the BidiMap. The inverseBidiMap() method returns an inverse view of the map, i.e., the keys and values are reversed. This map is backed up by the original map and hence changes to one map will be visible in the other and vice versa.
DualHashBidiMap
Let us now look at the simplest implementation of a BidiMap - DualHashBidiMap. A DualHashBidiMap uses two Java HashMap instances to provide a bidirectional implementation of a Map. It provides a fast lookup in both directions at the expense of more space.
Creating a DualHashBidiMap
We can call the no-argument constructor of a DualHashBidiMap to create an empty DualHashBidiMap. It also offers a constructor to which we can pass an existing map and it constructs a BidiMap from the entries in the passed map.
Inserting values into a DualHashBidiMap
Let us now create an empty DualHashBidiMap and insert some values.
BidiMap<String, Integer> dualHashBidiMap = new DualHashBidiMap<>();
dualHashBidiMap.put("A", 1);
dualHashBidiMap.put("B", 2);
dualHashBidiMap.put("C", 3);
In the code above, we have created a DualHashBidiMap and inserted two key-value pairs into it. Let us now print the map and the inverse map using the inverseBidiMap() method.
System.out.println(dualHashBidiMap);
System.out.println(dualHashBidiMap.inverseBidiMap());
The above will print,
{A=1, B=2, C=3}
{1=A, 2=B, 3=C}
As we can see, the first line printed the map contents and the second line printed the inverse map, which maps the values to keys.
Querying the BidiMap by key and value
We will now query the map by key and value. Calling the get() method and passing the key will return the value mapped to it (the usual thing we do on a map). If there is no mapping for the passed key, it returns a null.
System.out.println(dualHashBidiMap.get("A")); //1
System.out.println(dualHashBidiMap.get("D")); //null
To get the key of a given value, we use the getKey() method. If there is no entry in the map with the passed value, it will return a null.
System.out.println(dualHashBidiMap.getKey(2)); //B
System.out.println(dualHashBidiMap.getKey(22)); //null
Get BidiMap values as a Set
To get the all the values in the bidirectional map as a Set, we use the values() method as shown below.
System.out.println(dualHashBidiMap.values()); //[1, 2, 3]
Removing BidiMap entries by key and value
Let us now remove some of the entries by key and value. In our example, the BidiMap map has five entries, as shown below.
BidiMap<String, Integer> dualHashBidiMap = new DualHashBidiMap<>();
dualHashBidiMap.put("A", 1);
dualHashBidiMap.put("B", 2);
dualHashBidiMap.put("C", 3);
dualHashBidiMap.put("D", 4);
dualHashBidiMap.put("E", 5);
There are two remove() methods on a Java map.
The first one takes both a key and a value and removes the entry for the specified key if it is currently mapped to the specified value. It returns true if the removal took place.
The second one just takes the key and removes the entry with the specified key. It returns the value mapped to the key of the removed entry.
Usage of these are shown below.
System.out.println(dualHashBidiMap.remove("D", 4)); //true
System.out.println(dualHashBidiMap.remove("E")); //5
Now, the contents of the BidiMap are as follows.
System.out.println(dualHashBidiMap); //{A=1, B=2, C=3}
System.out.println(dualHashBidiMap.inverseBidiMap()); //{1=A, 2=B, 3=C}
We will now use the removeValue() method to remove an entry by passing the value. Removing the entry with value 3 would remove the entry {C=3} and return the key (C). The map contents are printed as well.
System.out.println(dualHashBidiMap.removeValue(3)); //C
System.out.println(dualHashBidiMap); //{A=1, B=2}
System.out.println(dualHashBidiMap.inverseBidiMap());//{1=A, 2=B}
Removal of entries during insertion
As we’ve seen, the entries of a BidiMap must have a 1:1 relation between keys and values. Let us now see what happens when we insert an entry into a BidiMap whose key or value already exists in the map.
Overwriting on a key
In the code below, we insert an entry {A=1} into the BidiMap. Remember that Map#put returns the previously mapped value to the key inserted. Since there was no mapping for the key A, it returns a null.
BidiMap<String, Integer> dualHashBidiMap = new DualHashBidiMap<>();
System.out.println(dualHashBidiMap.put("A", 1)); //null
System.out.println(dualHashBidiMap); //{A=1}
System.out.println(dualHashBidiMap.inverseBidiMap()); //{1=A}
Let us now insert a new entry {A=2}. The result of the put() now will return the value 1 which was the previously mapped value to key A.
Since the BidiMap already has a mapping for key A, it now replaces it with the value 2. The important thing to note here is that it automatically updates the reverse or inverse map as well. As shown below, the inverse map has only the entry {2=A} and it has removed the entry {1=A} as the original entry {A=1} no longer exists.
System.out.println(dualHashBidiMap.put("A", 2)); //1
System.out.println(dualHashBidiMap); //{A=2}
System.out.println(dualHashBidiMap.inverseBidiMap()); //{2=A}
Overwriting on a value
Let us now start over with one entry as before and insert an entry with a new key but an existing value.
BidiMap<String, Integer> dualHashBidiMap = new DualHashBidiMap<>();
System.out.println(dualHashBidiMap.put("A", 1)); //null
System.out.println(dualHashBidiMap); //{A=1}
System.out.println(dualHashBidiMap.inverseBidiMap()); //{1=A}
System.out.println(dualHashBidiMap.put("B", 1)); //null
System.out.println(dualHashBidiMap); //{B=1}
System.out.println(dualHashBidiMap.inverseBidiMap()); //{1=B}
When we insert a new entry {B=1}, it is a new key and hence the put call returns null. But the BidiMap’s inverse map already has a mapping for the key 1 (which is {1=A}). It now gets replaced with {1=B}. Thus, this leads to removal of entry {A=1} in the main map.
In other words, since the mapping between key to value and value to key is 1:1, it cannot hold two mappings {A=1} and {B=1}. The second write overwrites the previous mapping in the inverse map and the BidiMap updated the main map contents appropriately.
Constructing a DualHashBidiMap from an existing map
As said earlier, we can also build a DualHashBidiMap by passing an existing map to its constructor.
We have a HashMap, as shown below.
Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("pear", 4);
map.put("grape", 5);
map.put("orange", 6);
Let us build a (DualHash)BidiMap from this.
DualHashBidiMap<String, Integer> dualHashBidiMapFromHashMap = new DualHashBidiMap<>(map);
System.out.println(dualHashBidiMapFromHashMap); //{orange=6, pear=4, grape=5}
System.out.println(dualHashBidiMapFromHashMap.inverseBidiMap()); //{4=pear, 5=grape, 6=orange}
When we insert the entry {grape=5}, it will remove the entry {apple=5} because both have the same value, i.e., as seen earlier, the apple entry gets overwritten in the inverse map and the original map is updated.
DualLinkedHashBidiMap
This implementation of BidiMap, called DualLinkedHashBidiMap, uses two LinkedHashMap objects. Since the DualHashBidiMap used two HashMaps, the BidiMap did not guarantee the order of entries within the map. But DualLinkedHashBidiMap provides a guarantee to maintain the entries as per the insertion order.
Here, we create a DualLinkedHashBidiMap and add three entries into it.
BidiMap<String, Integer> dualLinkedHashBidiMap = new DualLinkedHashBidiMap<>();
dualLinkedHashBidiMap.put("apple", 5);
dualLinkedHashBidiMap.put("pear", 4);
dualLinkedHashBidiMap.put("orange", 6);
System.out.println(dualLinkedHashBidiMap); //{apple=5, pear=4, orange=6}
System.out.println(dualLinkedHashBidiMap.inverseBidiMap()); //{5=apple, 4=pear, 6=orange}
From the printed map content, we can see that the map maintains the entries in the order in which they were inserted.
Since the other methods we’ve seen earlier work the same way, I’ll avoid repeating them here.
Let us create a DualLinkedHashBidiMap from an existing map.
Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("pear", 4);
map.put("grape", 5);
map.put("orange", 6);
System.out.println(map); //{orange=6, apple=5, pear=4, grape=5}
BidiMap<String, Integer> dualLinkedHashBidiMapFromHashMap = new DualLinkedHashBidiMap<>(map);
System.out.println(dualLinkedHashBidiMapFromHashMap); //{orange=6, pear=4, grape=5}
System.out.println(dualLinkedHashBidiMapFromHashMap.inverseBidiMap()); //{6=orange, 5=grape, 4=pear}
This is the same example used earlier. Since there is a value conflict when we insert the entry {grape=5}, it will remove the entry {apple=5}. But the main map still maintains the insertion order (orange → pear → grape). We have to consider the insertion order as the order in which we get the entries when iterating over the HashMap.
Note that the inverse map has a different order. That is because of how LinkedHashMap works. The insertion order is not affected when we re-insert a key into the map. In this example, as far the inverse map is concerned, it already had an entry {5=apple} at position 2 (following {6=orange}). When it sees the entry {5=grape}, it will replace the value ‘apple’ with ‘grape’. This doesn’t change the ordering internally in the inverse map.
OrderedBidiMap and SortedBidiMap
We will now see two subinterfaces of BidiMap viz., OrderedBidiMap and SortedBidiMap. They both represent a map that allows bidirectional lookup between keys and values while providing an ordering. The SortedBidiMap ensures that the map entries are sorted by keys and values.
OrderedBidiMap and SortedBidiMap hierarchy
The entire class and interface hierarchy of OrderedBidiMap and SortedBidiMap is shown below.
A SortedBidiMap extends the OrderedBidiMap interface and the Java SortedMap interface. The OrderedBidiMap is a BidiMap and an OrderedMap.
The OrderedMap interface extends the IterableMap interface (which we’ve seen earlier) and has the following methods: mapIterator(), firstKey(), lastKey(), nextKey() and previousKey(). The mapIterator method here is the overwritten version from the IterableGet interface. The mapIterator method returns an OrderedMapIterator which is a subinterface of the MapIterator we saw before. It has hasPrevious() and previous() methods.
We will learn now learn about the DualTreeBidiMap class (which implements the SortedBidiMap interface) and TreeBidiMap class (which implements the OrderedBidiMap interface).
DualTreeBidiMap
The DualTreeBidiMap is a BidiMap which provides a bidirectional ordered map using two TreeMap instances. It thus orders the entries by the keys in the map (both in the main map and also in the inverse map).
DualTreeBidiMap<String, Integer> dualTreeBidiMap = new DualTreeBidiMap<>();
dualTreeBidiMap.put("B", 2);
dualTreeBidiMap.put("A", 1);
System.out.println(dualTreeBidiMap); //{A=1, B=2}
System.out.println(dualTreeBidiMap.inverseBidiMap()); //{1=A, 2=B}
It orders the map by the natural ordering of the keys (String) and the inverse map by the natural ordering of the values (Integer).
Another example is shown below.
DualTreeBidiMap<String, Integer>dualTreeBidiMap = new DualTreeBidiMap<>();
dualTreeBidiMap.put("apple", 5);
dualTreeBidiMap.put("pear", 4);
dualTreeBidiMap.put("orange", 6);
System.out.println(dualTreeBidiMap); //{apple=5, orange=6, pear=4}
System.out.println(dualTreeBidiMap.inverseBidiMap()); //{4=pear, 5=apple, 6=orange}
Building a DualTreeBidiMap from a HashMap
There is another constructor to which we can pass an existing Map and construct a DualTreeBidiMap from it.
Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("pear", 4);
map.put("grape", 5);
map.put("orange", 6);
System.out.println(map); //{orange=6, apple=5, pear=4, grape=5}
DualTreeBidiMap<String, Integer> dualTreeBidiMap = new DualTreeBidiMap<>(map);
System.out.println(dualTreeBidiMap); //{grape=5, orange=6, pear=4}
System.out.println(dualTreeBidiMap.inverseBidiMap()); //{4=pear, 5=grape, 6=orange}
As seen before, pay attention to the order of elements in the HashMap (not the order in which we insert into it). It iterates over the HashMap entries and inserts them into the DualTreeBidiMap (with the entry {grape=5} removing the entry {apple=5}).
Using a custom comparator to order the elements
We can also pass two comparators to determine the order in which to sort the keys and values. Shown below, we sort the keys by its length and values in reverse order.
DualTreeBidiMap<String, Integer> dualTreeBidiMap = new DualTreeBidiMap<>(
Comparator.comparing(String::length),
Comparator.reverseOrder());
dualTreeBidiMap.put("apple", 5);
dualTreeBidiMap.put("pear", 4);
dualTreeBidiMap.put("orange", 6);
System.out.println(dualTreeBidiMap); //{pear=4, apple=5, orange=6}
System.out.println(dualTreeBidiMap.inverseBidiMap()); //{6=orange, 5=apple, 4=pear}
Iterating using the OrderedMapIterator
From the class/interface hierarchy, a SortedBidiMap is a OrderedMapIterator. Let us now use the mapIterator to traverse the map entries.
Using the above built dualTreeBidiMap, we can do a forward iteration, as shown below. We use hasNext() to check if the iterator has more entries and calling the next() on the iterator moves the iterator forward. The next() returns the next entry’s key. We can get the value using the getValue() method. Unlike the next() method, we can call getValue() any number of times without affecting the iterator’s internal state. Note: We can get the key using getKey() as well.
OrderedMapIterator<String, Integer> orderedMapIterator = dualTreeBidiMap.mapIterator();
while (orderedMapIterator.hasNext()) {
System.out.println(orderedMapIterator.next() + " - " + orderedMapIterator.getValue());
}
Running this, we get,
pear - 4
apple - 5
orange - 6
Since we have reached the end of the iteration, we can now iterate backwards using the same Iterator because it is an OrderedMapIterator. We do this by using the hasPrevious() and previous() methods.
while (orderedMapIterator.hasPrevious()) {
System.out.println(orderedMapIterator.previous() + " - " + orderedMapIterator.getValue());
}
Prints,
orange - 6
apple - 5
pear - 4
Similarly, we can iterate forward and in reverse on the inverse map as well. Remember that we have defined the natural ordering as reversed for the values. Hence, on forward iteration, we will get the values in descending order.
OrderedMapIterator<Integer, String> inverseMapIterator = dualTreeBidiMap.inverseBidiMap().mapIterator();
while (inverseMapIterator.hasNext()) {
System.out.println(inverseMapIterator.next() + " - " + inverseMapIterator.getValue());
}
System.out.println();
while (inverseMapIterator.hasPrevious()) {
System.out.println(inverseMapIterator.previous() + " - " + inverseMapIterator.getValue());
}
Prints,
6 - orange
5 - apple
4 - pear
4 - pear
5 - apple
6 - orange
TreeBidiMap
A TreeBidiMap is a custom red-black tree implementation of BidiMap. The keys and values must be Comparable i.e., they should implement the Comparable interface.
TreeBidiMap<K extends Comparable<K>, V extends Comparable<V>>
implements OrderedBidiMap<K, V>, Serializable {...}
Unlike the DualTreeBidiMap, this doesn’t use two TreeMaps. Instead, it is a custom implementation of red-black tree (same underlying implementation of a TreeMap). Functionally, it is the same as the DualTreeBidiMap, but it doesn’t maintain two map instances and hence provides a more optimized bidirectional map implementation which sorts the keys and values by storing the data only once.
This class guarantees that the map will be in both ascending key order and ascending value order, sorted according to the natural order of the keys and values.
Internally, in a TreeMap, a node will have left and right child pointers. Here, they have changed the implementation, so each node has left and right for keys and values separately.
Let us start with a simple example.
TreeBidiMap<String, Integer> treeBidiMap = new TreeBidiMap<>();
treeBidiMap.put("A", 1);
treeBidiMap.put("B", 2);
System.out.println(treeBidiMap); //{A=1, B=2}
System.out.println(treeBidiMap.inverseBidiMap()); //{1=A, 2=B}
TreeBidiMap<String, Integer> treeBidiMap = new TreeBidiMap<>();
treeBidiMap.put("apple", 5);
treeBidiMap.put("pear", 4);
treeBidiMap.put("orange", 6);
System.out.println(treeBidiMap); //{apple=5, orange=6, pear=4}
System.out.println(treeBidiMap.inverseBidiMap()); //{4=pear, 5=apple, 6=orange}
In both the examples, the behaviour and the output are the same as in the DualTreeBidiMap. But it achieves the same by optimizing the storage.
If we imagine the tree node for the above three entries with the node or entry {apple=5} at the root, its left key child will be null and its left value child will be the entry {pear=4}. This is because in the sorted order of keys, there is nothing before the string ‘apple’, but in the inverse map, the entry {5=apple} is after the entry {4=pear}.
Similarly, the right key child is the entry {pear=4} and the right value child will be {orange=6}. The right key child here might be confusing as ‘pear’ doesn’t immediately follow ‘apple’ in the order. If you look at the tree shown below, it will be clearer.
As we can see in the key order of entries, the entry {orange=6} is the left child of {pear=4}. Hence, during the main map traversal (binary search tree in-order traversal), we get the order as apple → orange → pear. In the tree map ordering as per value, we get the order as pear → apple → orange.
Internally, the node’s left and right are an array of Node of size 2 (Node[]) where each node points to its left key (leftNode[0]) and left value (leftNode[1]) and right key (rightNode[0]) and right value (rightNode[1]).
Conclusion
In this post, we learnt about the bidirectional map interface, Apache Commons Collections BidiMap in detail. We learnt about the operations supported by the BidiMap interface and looked in detail about its four implementations.
You can learn more about other utilities from the apache-commons library here.