According to Javadoc of Map, a Map is an object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. However, we come across scenarios wherein more than one value has to be mapped to a key. In such scenarios where multiple values need to be mapped to a single key, we end up creating a Map with a single key but a collection of values. It is important that the semantics of the value collection are maintained viz.:
- List of values will behave as a List: allows duplicates, maintain order.
- Set of values will behave as a Set: hashed data structure, contains unique elements.
- Bag of values will behave as a Bag: hashed data structure, allows duplicates.
Eclipse Collections provides Multimaps for all 3 types of value collections: ListMultimap, SetMultimap (Sorted, Unsorted) and BagMultimap (Sorted, Unsorted). Mutable, Immutable, Synchronized and MultiReader variants of all these Multimaps are available in Eclipse Collections.
Let us consider an Item object and an Item data set as below. The Item data set consists of three fruits, two vegetables and one meat.
Let us see how we can group the list of items:
- In the JDK we can use the streams API with
Collectors.groupingBy()to get a
Map<String, List<Item>>in this case.
- Eclipse Collections provides the
groupBy()API which returns an Eclipse Collections
Multimap. Since we are calling
MutableListwe will get a
We need to use the overloaded methods which accept a target value collection to get a desired type of Multimap, because, both JDK and Eclipse Collections have covariant overrides. The covariant override contract ensures that a groupBy() operation:
- On a List returns a ListMultimap
- On a Set returns a SetMultimap
- On a Bag returns a BagMultimap.
Let us see them side by side:
Eclipse Collections Multimaps Architecture:
Multimaps are backed up by UnifiedMap, which is the more memory efficient Map included in Eclipse Collections. The overall architecture for a Multimap without collisions can be seen below, the strategy for handling collisions is same as that of UnifiedMap.
Adding and Removing elements from Eclipse Collections MutableMultimap:
Eclipse Collections MutableMultimap has mutating operations like
removeAll(). There are a few interesting aspects of these mutating methods, let us look at each one:
putAll(): These methods are interesting when called for a key which does not exist in the Multimap. The Eclipse Collections implementation handles these cases by creating a new Collection and then adding the key and value. In the example below, there is no element with key=beverage. When we add key-value = beverage-milk, internally Eclipse Collections will create an empty List and then add to the MutableMultimap. Any further additions of values to key=beverage, the new values are added to the list. In case of the JDK implementation of Map<K, List<V>> we have to handle the empty List creation.
removeAll() : These methods are interesting when the result of removal will leave an empty collection. The Eclipse Collections implementation ensures that there will not exists a key without a non-empty collection. In cases where the last value is removed for a particular key, the key as well is removed. This ensures that the Multimap will contain only those keys which have a non-empty value collection.
The Eclipse Collections Multimap has a rich and an intuitive API specifically designed to help with iteration patterns pertaining to Multimap like
collectValues() to name a few.
Memory Footprint (lower number the better)
Below are few memory footprint comparisons between JDK 1.8 HashMap and Eclipse Collections Multimap. This shows the total memory footprint including the constituents of the data structures.
- Eclipse Collections provides Multimap implementations with List, Set and Bag as backing collections.
- Eclipse Collections provides an intuitive API to create a Multimap.
- Eclipse Collections Multimap has a Multimap specific API which handles initialization and eviction of backing collections for you.
- Eclipse Collections Multimap API is intuitive for use and the API is kept similar to the API provided by Maps.
- Eclipse Collections Multimaps consistently have a smaller memory footprint compared to the equivalent JDK Multimap implementation. Eclipse Collections SetMultimap memory footprint is ~55% that of JDK SetMultimap memory footprint.
Show your support star us on GitHub.
Eclipse Collections Resources:
Eclipse Collections comes with it’s own implementations of List, Set and Map. It also has additional data structures like Multimap, Bag and an entire Primitive Collections hierarchy. Each of our collections have a rich API for commonly required iteration patterns.