Multimap — How it works

Nikhil Nanivadekar
Jun 23, 2018 · 5 min read
https://www.eclipse.org/collections/

In my previous blogs I explained how Eclipse Collections UnifiedMap and UnifiedSet works. In this blog, we will take a look at Multimap or Multi-valued Map in Eclipse Collections.

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.:

  1. List of values will behave as a List: allows duplicates, maintain order.
  2. Set of values will behave as a Set: hashed data structure, contains unique elements.
  3. 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.

Item.java
Item data set for tests.

Let us see how we can group the list of items:

  1. In the JDK we can use the streams API with Collectors.groupingBy() to get a Map<String, List<Item>> in this case.
  2. Eclipse Collections provides the groupBy() API which returns an Eclipse Collections Multimap . Since we are calling groupBy() on a MutableList we will get a ListMultimap<String, Item>.
JDK Map<String, List<Item>>
Eclipse Collections ListMultimap<String, Item>

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:

  1. On a List returns a ListMultimap
  2. On a Set returns a SetMultimap
  3. On a Bag returns a BagMultimap.

Let us see them side by side:

JDK vs Eclipse Collections Multimap construction from top to bottom: ListMultimap, SetMultimap, BagMultimap.

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.

Eclipse Collections Multimap Architecture Schematic Diagram

Adding and Removing elements from Eclipse Collections MutableMultimap:

Eclipse Collections MutableMultimap has mutating operations like put(), putAll(), remove(), removeAll(). There are a few interesting aspects of these mutating methods, let us look at each one:

  1. put(), 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.
MutableMultimap.put() operation in Eclipse Collections.

2. remove(), 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.

MutableMultimap.remove() operation in Eclipse Collections.

The Eclipse Collections Multimap has a rich and an intuitive API specifically designed to help with iteration patterns pertaining to Multimap like keyBag(), keySet(), forEachKey(), forEachValue(), forEachKeyValue(), forEachKeyMultiValues(), selectKeysValues(), rejectKeysValues(), selectKeysMultiValues(), rejectKeysMultiValues(), collectKeysValues(), 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.

Memory Comparison: EC ListMultimap<Integer, Integer> and JDK HashMap<Integer, List<Integer>>
Memory Comparison: EC ListMultimap<String, String> and JDK HashMap<String, List<String>>
Memory Comparison: EC SetMultimap<Integer, Integer> and JDK HashMap<Integer, Set<Integer>>
Memory Comparison: EC SetMultimap<String, String> and JDK HashMap<String, Set<String>>
Memory Comparison: EC BagMultimap<Integer, Integer> and JDK HashMap<Integer, Map<Integer, Long>>
Memory Comparison: EC BagMultimap<String, String> and JDK HashMap<String, Map<String, Long>>

Summary:

  1. Eclipse Collections provides Multimap implementations with List, Set and Bag as backing collections.
  2. Eclipse Collections provides an intuitive API to create a Multimap.
  3. Eclipse Collections Multimap has a Multimap specific API which handles initialization and eviction of backing collections for you.
  4. Eclipse Collections Multimap API is intuitive for use and the API is kept similar to the API provided by Maps.
  5. 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.

  1. Website
  2. Source code on GitHub
  3. Contribution Guide
  4. Reference Guide

Oracle Groundbreakers

Aggregation of articles from Oracle and partner’s engineers, Groundbreaker Ambassadors and the developer community on all things Oracle Cloud and its technologies. The views expressed are those of the authors and not necessarily those of Oracle. Contact @jimgris or @brhubart

Nikhil Nanivadekar

Written by

Lead Eclipse Collections: eclipse.org/collections, Java Champion. I enjoy hiking, skiing, reading. All opinions stated by me are my own. Twitter @nikhilnanivade

Oracle Groundbreakers

Aggregation of articles from Oracle and partner’s engineers, Groundbreaker Ambassadors and the developer community on all things Oracle Cloud and its technologies. The views expressed are those of the authors and not necessarily those of Oracle. Contact @jimgris or @brhubart

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade