Introduction
A BiMap is a bidirectional map. We use a map to maintain a mapping from a key to a value. But sometimes, we also have a need to maintain the reverse mapping (from value to key) on occasions when the values are also unique.
In this post, we will learn about the BiMap in Google Guava and how it eases the problem of maintaining two bi-directional maps.
Maintaining bidirectional mapping
A traditional map maintains mapping from keys to values. There are situations where we have to look up by a value from a Map. These situations assume that the key to value mapping is unique i.e., the values are also unique, and a value is mapped to only one key.
We usually do it in two ways.
1. Traverse the map each time
We perform a full map traversal to get the desired result (the key for a value to be looked up). This is not optimal as in the worst case, we perform a full map traversal.
String valueWeAreLookingFor = "value";
return map.entrySet()
.stream()
.filter(entry -> entry.getValue().equals(valueWeAreLookingFor))
.findFirst()
.map(entry -> entry.getKey())
.orElse(-1); //or throw an exception
2. Maintain the reverse mapping
Another solution is to maintain two maps ourselves - the forward and the reverse map. To do the reverse lookup, we use the reverse map.
Map<Integer, String> forwardMap = new HashMap<>();
Map<String, Integer> reverseMap = new HashMap<>();
forwardMap.put(1, "a");
forwardMap.put(2, "b");
reverseMap.put("a", 1);
reverseMap.put("b", 2);
It is efficient in terms of runtime (O(1)). But it costs 2x space and has the burden of keeping both the maps in sync. Whenever one changes, we have to update the other too.
Google Guava’s BiMap
The BiMap class in Google Guava can help us achieve this. It implements the interface of a Map and hence has all the functionalities of a Map. In addition to this, it takes care of maintaining the mapping in the reverse direction too (from value to a key). Thus, with a single method call, we can get the reverse direction’s map (similar to the reverseMap in the above example).
Let us look into what the BiMap has to offer.
A BiMap is an interface and there are a few implementing classes that are of interest. To demonstrate the functionalities of a BiMap interface, I will use the HashBiMap class. It uses a HashMap as the backing map. After seeing the interface methods of the BiMap, I’ll describe the other subclasses of the BiMap.
Creating a (Hash)BiMap
To create a HashBiMap, simply call the create static method on it.
BiMap<Integer, String> hashBiMap = HashBiMap.create();
If you already have a map populated with values, we can call the create method that accepts a map as an argument.
Map<Integer, String> existingMap = new HashMap<>();
// Populate map
BiMap<Integer, String> hasBiMap = HashBiMap.create(existingMap);
Inserting into a BiMap
Since a BiMap is a Map, it has the put and putAll methods. But there is a catch here. Since a BiMap is a bidirectional map, the mapping from value to key must be unique. If we attempt to add a mapping say k1 -> v1, there must be no mapping from a different key (say k) to v1. If it does, it throws an IllegalArgumentException.
Let us create a BiMap and add a couple of mappings.
BiMap<Integer, String> hashBiMap = HashBiMap.create();
hashBiMap.put(1, "a");
hashBiMap.put(2, "b");
System.out.println(hashBiMap);//{1=a, 2=b}
Let us see what happens when we add a mapping from a key to an existing value so that a value will be mapped to two unique keys.
hashBiMap.put(1, "b");
The above line throws the below exception
java.lang.IllegalArgumentException: value already present: b
We can use the putAll method to add all the entries from an existing map into a BiMap.
Map<Integer, String> map = new HashMap<>();
map.put(3, "c");
map.put(4, "d");
hashBiMap.putAll(map);
System.out.println("Original BiMap " + hashBiMap);//{1=a, 2=b, 3=c, 4=d}
Getting the inverse view of a map
Now, we will look at the core use of a BiMap i.e., getting the inverse view of a map which maps each of the BiMap’s values to its keys. It provides a method, inverse, for this.
BiMap<String, Integer> inverseOfHashBiMap = hashBiMap.inverse();
System.out.println(inverseOfHashBiMap);
The above line prints
{a=1, b=2, c=3, d=4}
The returned inverse map is a view of the original map and hence it is backed up by the same original map. Thus, changes to one will be reflected in the other.
Example: We can add a new entry or update an entry in one map, and the same will be reflected in the other too.
inverseOfHashBiMap.put("e", 5);
System.out.println("Original BiMap " + hashBiMap);
System.out.println("Inverse BiMap " + inverseOfHashBiMap);
Prints
Original BiMap {1=a, 2=b, 3=c, 4=d, 5=e}
Inverse BiMap {a=1, b=2, c=3, d=4, e=5}
We added a new mapping (e -> 5) in the inverse map, but we can see the mapping (5 -> e) in the original BiMap too.
BiMap Force Put
We have learnt that once we add a mapping (k1 -> v1), there can be no other mapping say k2 -> v1. What if we want to remove the mapping k1 -> v1 and map v1 to k2?
We do not want to perform two operations - remove mapping for k1 and add the new desired mapping. The BiMap has a method call forcePut that does this for us.
In the above map, if we want to change the mapping 5 -> e to 50 -> e, we have to do a force put
hashBiMap.forcePut(50, "e");
System.out.println("Original BiMap " + hashBiMap);//Original BiMap {1=a, 2=b, 3=c, 4=d, 50=e}
System.out.println("Inverse BiMap " + inverseOfHashBiMap);//Inverse BiMap {a=1, b=2, c=3, d=4, e=50}
BiMap Query methods
Since a BiMap is a Map, it has all the query methods available on a Map (like get, values, keySet and valueSet). One difference is that since the values are also unique in a BiMap, the values method returns a Set<V>, a more specific collection (rather than a Collection<V> as declared in the Map interface).
System.out.println(hashBiMap.values()); //[a, b, c, d, e]
System.out.println(hashBiMap.keySet()); //[1, 2, 3, 4, 50]
System.out.println(hashBiMap.entrySet()); //[1=a, 2=b, 3=c, 4=d_new, 50=e]
Other subclasses of BiMap
We have already looked at HashBiMap. Let us look at other subclasses of a BiMap, namely,
ImmutableBiMap
ImmutableBiMap creation
An ImmutableBiMap is a BiMap that is immutable. It is desirable to have immutable objects in your application/code (see Benefits of Immutable class).
It offers several static factory methods that return an ImmutableBiMap taking key-value pairs (upto five key-value pairs). So, you can use this if you have less than 6 entries to be inserted into the map.
BiMap<Integer, String> immutableBiMap = ImmutableBiMap.of(1, "a", 2, "b");
System.out.println(immutableBiMap); //{1=a, 2=b}
You can use the builder it offers to build if you have more than 5 entries or you want a fluent looking API.
BiMap<Integer, String> immutableBiMap = ImmutableBiMap.<Integer, String>builder()
.put(1, "a")
.put(2, "b")
.build();
The above fluent builder API is often confused with the Joshua Bloch’s Builder pattern. Refer to the posts on the GoF Builder Pattern and Joshua Bloch’s Builder pattern.
Last but not the least, you can create an ImmutableBiMap from an existing map by using the copyOf method.
BiMap<Integer, String> hashBiMap = HashBiMap.create();
hashBiMap.put(1, "a");
hashBiMap.put(2, "b");
immutableBiMap = ImmutableBiMap.copyOf(hashBiMap);
System.out.println(immutableBiMap); //{1=a, 2=b}
The toImmutableBiMap Collector
The ImmutableBiMap has a method called toImmutableMap. It returns a Collector and takes two functions to map an object to a key and a value. It is similar to the Collectors toMap method in Java. Hence, it plays well with streams when we have to collect a stream into an ImmutableBiMap.
Let us say we have a list of strings where there can be only one string of a given length. We want to convert this list to an ImmutableBiMap mapping from the string to its length. We can do it as.
List<String> strings = Arrays.asList("a", "bb", "ccc", "dddd");
BiMap<String, Integer> result = strings
.stream()
.collect(ImmutableBiMap.toImmutableBiMap(Function.identity(), String::length));
System.out.println(result); //{a=1, bb=2, ccc=3, dddd=4}
Since it is a BiMap, we can do the lookup in both ways
System.out.println(result.get("a")); //1
System.out.println(result.inverse().get(1)); //a
EnumBiMap
An EnumBiMap is backed up by two EnumMap instances. An EnumMap is a specialized Map implementation to be used with enum types in Java. Both the key and value of a EnumBiMap are enums.
This class is useful when we have to map two separate enums. Each of the enum instances in one enum is related/mapped to one enum instance from the other enum.
Say we have two enums viz., HttpVerb and ResourceOperation as shown below.
public enum HttpVerb {
GET,
PUT,
POST,
DELETE
}
public enum ResourceOperation {
RETRIEVE,
UPDATE,
CREATE,
REMOVE
}
GET is mapped to RETRIEVE, PUT is mapped to UPDATE and so on. To lookup one by the other (and vice versa), we usually add one enum instance as a field in another (as in this stack overflow answer).
public enum HttpVerb {
GET(ResourceOperation.RETRIEVE),
PUT(ResourceOperation.UPDATE),
POST(ResourceOperation.CREATE),
DELETE(ResourceOperation.REMOVE);
ResourceOperation resourceOperation;
HttpVerb(ResourceOperation resourceOperation) {
this.resourceOperation = resourceOperation;
}
}
But this ties the two enums closely and needs source code change of one of the enums. Still, the above only gives one way mapping.
Using EnumBiMap provides an elegant solution. We create an EnumBiMap and add the mapping from one enum to another. Since it is a BiMap, we get the reverse direction mapping for free.
EnumBiMap<HttpVerb, ResourceOperation> enumBiMap = EnumBiMap.create(HttpVerb.class, ResourceOperation.class);
enumBiMap.put(HttpVerb.GET, ResourceOperation.RETRIEVE);
enumBiMap.put(HttpVerb.PUT, ResourceOperation.UPDATE);
enumBiMap.put(HttpVerb.POST, ResourceOperation.CREATE);
enumBiMap.put(HttpVerb.DELETE, ResourceOperation.REMOVE);
We pass the key and value enum types as arguments.
System.out.println(enumBiMap); //{GET=RETRIEVE, PUT=UPDATE, POST=CREATE, DELETE=REMOVE}
System.out.println(enumBiMap.inverse().get(ResourceOperation.RETRIEVE)); //GET
We can create an EnumBiMap from an existing map too.
Map<HttpVerb, ResourceOperation> map = new HashMap<>();
map.put(HttpVerb.GET, ResourceOperation.RETRIEVE);
enumBiMap = EnumBiMap.create(map);
System.out.println(enumBiMap); //{GET=RETRIEVE}
EnumHashBiMap
An EnumHashBiMap maps an Enum to an arbitrary object i.e., it is like an EnumBiMap, but only the key is an enum. It uses an EnumMap for key-value mappings and an HashMap for value-key mappings.
EnumHashBiMap<HttpVerb, String> enumHashBiMap = EnumHashBiMap.create(HttpVerb.class);
enumHashBiMap.put(HttpVerb.PUT, "PUT");
System.out.println(enumHashBiMap); //{PUT=UPDATE}
Conclusion
We saw the options we had in maintaining a bidirectional mapping from a traditional map. We learnt that the BiMap class in Google Guava is a Map that maintains mappings in both ways (from key to value and from value to key). For this, the values in the map must also be unique. We looked at the methods of a BiMap and the subclasses of it.
There is a class called Multimap in Google Guava that allows us to add multiple values against a key in a Map.
Check out the other useful utility classes of Google Guava and let me know your thoughts and comments :)