1. Overview
In this tutorial, we’ll take a look at MultiMap, a Map implementation that doesn’t exist in Kotlin stdlib but is provided by libraries such as Guava, Spring, and Apache.
First, we’ll understand what a MultiMap is, and then, we’ll create our own MultiMap implementation.
2. What Is a MultiMap
Before we understand the MultiMap concept, let’s see the Map interface.
2.1. Map Interface
Map is an interface present in Kotlin Collections since 1.0 (also in Java since 1.2) with many implementations such as HashMap and LinkedHashMap:
public interface Map<K, out V> {
public val size: Int
public fun isEmpty(): Boolean
public fun containsKey(key: K): Boolean
public fun containsValue(value: @UnsafeVariance V): Boolean
public operator fun get(key: K): V?
public fun getOrDefault(key: K, defaultValue: @UnsafeVariance V): V {
throw NotImplementedError()
}
}
It represents a Collection of keys and values. Given a key, the Map implementation retrieves the corresponding value. Map keys are a Set, so it doesn’t support duplicate elements and, by definition, each key can map up to one value.
What would we do if we needed to associate multiple values to a single key? One approach is to create an implementation of Map<K, Collection<V>>, but it can affect the behavior of most Map implementations. So, we’ll create a MultiMap class to address these issues.
2.2. MultiMap Definition and Semantics
A MultiMap is a Map that can store multiple values for each key:
- key “even” -> 2, 4, 6
- key “odd” -> 1
The definition of the size() method is the number of key/value pairs in the map. Let’s consider an example with four key/value pairs:
- key “even” -> 2
- key “even” -> 4
- key “even” -> 6
- key “odd” -> 1
In this implementation, the size is 4, even though there are only two keys.
So, with these concepts in mind, let’s start to code our implementation of MultiMap.
3. MultiMap Implementation
First of all, since a MultiMap has some functions that are different from a Map, we won’t use any interface. Let’s start creating a class named MultiMap with two generic types for the keys and values:
class MultiMap<K, V> {
private val map: MutableMap<K, MutableCollection<V>> = HashMap()
}
We have a private attribute of MutableMap with the same generic types of our class, but for the value type, we’re using a MutableCollection. To simplify the implementation, we initialize it as a HashMap.
4. MultiMap Methods
The basic operations of a Map are to put and retrieve elements for a given key.
4.1. put()
Since the MultiMap is parametrized for a generic type of value and we’d like to have multiple values for the same key, we can handle this in the put() method:
fun put(key: K, value: V) {
if (!map.containsKey(key) {
map[key] = HashSet()
}
map[key].add(value)
}
Note that if the key is not contained in the map it’s necessary to initialize the Collection. We’re using a HashSet as a Collection because we don’t want duplicate values for a key.
4.2. get()
The get() method returns all the elements for a given key. If the key is not found it returns an empty HashSet:
operator fun get(key: K): Collection<V> {
return map[key] ?: hashSetOf()
}
The operator keyword gives us a simpler way to access an entry. Since our get() returns a collection, we can check its size:
val multiMap = MultiMap<String, Int>()
multiMap.put("even", 2)
assertEquals(1, multiMap["even"].size)
4.3. putAll(), remove(), and removeAll()
Let’s also create a putAll() method to make putting multiple elements at once more convenient:
fun putAll(key: K, values: Collection<V>){
if (!map.containsKey(key)) {
map[key] = HashSet()
}
map[key].addAll(values)
}
Let’s also write a remove() method for removing a value for a given key:
fun remove(key: K, value: V): Boolean {
return map[key].remove(value)
}
For the removeAll() method, it’s simpler to recreate the value:
fun removeAll(key: K) {
map[key] = HashSet()
}
We can test putAll(), remove(), and removeAll() together:
val multiMap = MultiMap<String, Int>()
multiMap.putAll("even", setOf(2, 4, 6))
multiMap.remove("even", 2)
assertEquals(2, multiMap["even"].size)
multiMap.removeAll("even")
assertEquals(0, multiMap["even"].size)
4.4. replace() and replaceAll()
Let’s combine the remove() and put() methods to create a replace() method:
fun replace(key: K, oldValue: V, newValue: V): Boolean {
return if(remove(key, oldValue)){
put(key, newValue)
true
} else {
false
}
}
The replaceAll() method may only reassign the value:
fun replaceAll(key: K, values: Collection<V>){
map[key] = values.toHashSet()
}
We can test both replace() and replaceAll() together:
val multiMap = MultiMap<String, Int>()
multiMap.put("even", 2)
multiMap.replace("even", 2, 4)
assertTrue(multiMap["even"].contains(4))
assertFalse(multiMap["even"].contains(2))
multiMap.replaceAll("even", setOf(6))
assertTrue(multiMap["even"].contains(6))
assertFalse(multiMap["even"].contains(4))
4.5. clear()
Finally, we’ll add a clear() method to remove all keys and values:
fun clear() {
map.clear()
}
Let’s test this:
val multiMap = MultiMap<String, Int>()
multiMap.put("even", 2)
multiMap.clear()
assertNull(multiMap["even"])
5. Condition Check Methods
Since we’re creating a class that could be shared by many projects, let’s create a couple of methods to check conditions called containsKey() and containsValue():
fun containsKey(key: K): Boolean {
return map.containsKey(key)
}
fun containsValue(value: V): Boolean {
return map.values.flatten().contains(value)
}
That should make testing easier:
val multiMap = MultiMap<String, Int>()
multiMap.put("even", 2)
assertTrue(multiMap.containsKey("even"))
assertTrue(multiMap.containsValue(2))
Also, let’s write an isEmpty() method:
fun isEmpty(): Boolean {
return map.isEmpty()
}
This will return true for a recently created MultiMap:
val multiMap = MultiMap<String, Int>()
assertTrue(multiMap.isEmpty())
6. Get Attribute Methods
The only property of the MultiMap until now is a private map. Let’s create some read-only computed properties for size, keys, values, and entries:
val size: Int
get() {
var size = 0
for (value in map.values) {
size += value.size
}
return size
}
val keys: Set<K>
get() {
return map.keys
}
val values: Set<V>
get() {
return map.values.flatten().toSet()
}
val entries: Set<Map.Entry<K, V>>
get() {
val hashSet = HashSet<Map.Entry<K, V>>()
keys.forEach { key ->
map[key]?.forEach { value ->
hashSet.add(SimpleEntry(key, value))
}
}
return hashSet
}
Let’s write a test for these methods:
val multiMap = MultiMap<String, Int>()
multiMap.putAll("even", setOf(2, 4))
multiMap.put("odd", 1)
assertEquals(3, multiMap.size)
assertEquals(hashSetOf("even", "odd"), multiMap.keys)
assertEquals(hashSetOf(1, 2, 4), multiMap.values)
assertEquals(3, multiMap.entries.size)
It’s worth noticing that both size() and entries() consider each pair of keys and values individually.
7. Conclusion
In this article, we’ve learned how MultiMap can be a powerful tool and that it’s commonly used where a Map<K, Collection<V>> would be used. There are advantages to the MultiMap, such as not worrying about Collection handling or nullability checking. The size() method considering all entries and the methods to check keys and values are also convenient. Even though there are third-party implementations, it’s interesting to know the concepts and implement them as we need.
As always, all the code is available over on GitHub.
