1. Overview
In this short article, we’ll be looking at an interesting data structure in the Apache Commons Collections library – the BidiMap.
The BidiMap adds a possibility of looking up the key using the corresponding value on top of the standard Map interface.
2. Dependencies
We need to include the following dependency in our project for us to use BidiMap and its implementations. For Maven based projects, we have to add the following dependency to our pom.xml:
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
<version>4.1</version>
</dependency>
For Gradle-based projects, we have to add the same artifact to our build.gradle file:
compile 'org.apache.commons:commons-collections4:4.1'
The latest version of this dependency can be found on Maven Central.
3. Implementations and Instantiation
BidiMap itself is just an interface that defines behaviors unique to a bi-directional map – and there are of course multiple implementations available.
It’s important to understand that implementations of BidiMap do not allow key and value duplicates. When a BidiMap gets inverted, any duplicate values will be converted to duplicate keys and will violate the map contract. A map must always have unique keys.
Let’s look at different concrete implementations of this interface:
- DualHashBidiMap: This implementation uses two HashMap instances to implement the BidiMap internally*.* It provides fast lookup of entries using either an entry’s key or value. However, two instances of HashMap have to be maintained
- DualLinkedHashBidiMap: This implementation uses two LinkedHashMap instances and consequently maintains the insertion order of map entries. If we don’t need the insert order of the map entries to be maintained, we can just use the less expensive DualHashBidiMap
- TreeBidiMap: This implementation is efficient and is realized by a Red-Black tree implementation. The keys and values of TreeBidiMap are guaranteed to be sorted in ascending order using the natural ordering of the keys and values
- There is also DualTreeBidiMap that uses two instances of TreeMap to achieve the same thing as TreeBidiMap. DualTreeBidiMap is obviously more expensive than TreeBidiMap
The BidiMap interface extends the java.util.Map interface and so can serve as a drop-in replacement for it. We can use the no-arg constructor of the concrete implementations to instantiate a concrete object instance*.*
4. Unique BidiMap Methods
Now that we’ve explored the different implementations let’s look at methods that are unique to the interface.
The put() inserts a new key-value entry into the map. Note that if the value of the new entry matches the value of any existing entry, the existing entry will be removed in favor of the new entry.
The method returns the removed old entry or null if there’s none:
BidiMap<String, String> map = new DualHashBidiMap<>();
map.put("key1", "value1");
map.put("key2", "value2");
assertEquals(map.size(), 2);
The inverseBidiMap() reverses the key-value pair of a BidiMap. This method returns a new BidiMap where the keys have become the values and vice-versa. This operation can be very useful in translation and dictionary applications:
BidiMap<String, String> rMap = map.inverseBidiMap();
assertTrue(rMap.containsKey("value1") && rMap.containsKey("value2"));
The removeValue() is used to remove a map entry by specifying a value, instead of a key. This is an addition to Map implementations found in the java.util package:
map.removeValue("value2");
assertFalse(map.containsKey("key2"));
We can get the key mapped to a particular value in BidiMap with the getKey(). The method returns null if no key is mapped onto the specified value:
assertEquals(map.getKey("value1"), "key1");
5. Conclusion
This quick tutorial provided a look into the Apache Commons Collections library – specifically at BidiMap, its implementations and idiosyncratic methods.
The most exciting and distinguishing feature of BidiMap is its ability to look up and manipulate entries via keys as well as values.
As always, code snippets are available over on GitHub.