Multimaps
Most programmers have at one point or another used some variation of a map. Maps are some of the most versatile and useful data structures, but many of the different implementations and variations of map-like containers such as the multimap are lesser-known.
A multimap is an associative-array abstract data type in which more than one value may be associated with a given key. Multimaps come in a variety of flavors, and typically are categorized as hash-based or comparison-based.
Comparison based multimaps such as the C++ multimap take a key-value pair and insert them in a tree where the elements are sorted by key. In the case of the GNU Standard C++ Library, multimap is implemented with a red-black tree. Conversely, a hash-based multimap such as the C++ unordered_multimap, operates by hashing a key to determine which bucket a given key-value pair belongs in. Hash-based maps can have many underlying data structures containing values within each bucket, the most common implementation is a list. Both comparison and hash-based multimaps differ from their singular-map counterparts, in that inserting a value with a an existing key does not overwrite the value for the key, and instead a new pair is always emplaced.
Why use a multimap?
There exist many problems where associating a singular key with multiple values can be useful. An example of a use case for a multimap would be a book’s index. For any given term used in a book, it can be referenced on many pages. Being able to store all the pages for a single word in one structure is very useful, especially when considering both comparison-based and hash-based multimaps are performant for insertion, search, and removal. Another prime example would be a dictionary. In a dictionary, a single word can have multiple definitions, while still being of the exact same spelling.
Look at the above diagram, this is how a typical unordered map looks. There are many different elements in an array where each index in the array contains a range of hash values. For example hash(key1) hashes to 1, placing the value in the second place in the array. When another key such as key2 hashes to the same value it gets appended to the list of key-value pairs in that position in the array. Setting the value of an existing key to anything will overwrite the value because the hashes and the keys are equal. In a multimap, the structure looks the same except there can be multiple values for the same key despite sharing the same hashes and keys.
In this diagram you can see that keys can be duplicated while preserving the keys’ associations with indexes in the array. This principle still applies to ordered maps which use trees, as trees can contain multiple of the same value.
Lets take a look at how to use multimaps
In python a simple multimap can be implemented by using a list-based dictionary.
In the above demonstration we have two keys, type and fall both of these words have multiple meanings despite being spelled the same. In a typical map, only one value can be stored per key. This would mean that type would relate to the value write (something) on a… In our use case of a dictionary, this does not work. However, because this is a multimap, if we look at the values of our dictionary —
[('type', ['a category of people or things having common characteristics', 'write (something) on a typewriter or computer by pressing the keys']), ('fall', ['an act of falling or collapsing; a sudden uncontrollable descent', 'autumn'])]We can see that type has two definitions. This is great, multiple values can be associated to a single key.
Get Nick Wall’s stories in your inbox
Join Medium for free to get updates from this writer.
For another example, how would you access the values for a single key?
Multimaps, just like maps can be be searched by using a key, like you would an array index. For the above example we can see that the values of each of our students are arrays of scores, exactly like we want.
Alice Grades: [99, 85]
Bob Grades: [79]The last major feature of a map is removing values, in many languages and implementations, you can just set the value at a key to be null because in a typical map values get overwritten for a key. Multimaps operate a little differently because keys can have multiple values.
If we look at the values of the shopping cart, it starts with 2 keys and three items.
[('person1@example.com', ['Toothbrush', 'Sneakers']), ('person2@example.com', ['Headphones'])]Then the toothbrush value is removed and the shopping cart looks like this:
[('person1@example.com', ['Sneakers']), ('person2@example.com', ['Headphones'])]
And then finally, all values for the key person2@example.com are removed, leaving the final state of the cart as follows:
[('person1@example.com', ['Sneakers'])]Performance
Not only are multimaps a useful container for many different problems, but they are often implemented in very performant ways. A traditional multimap behaves like a map, as insertion, search, and deletion operations can be described as O(logn) operations. This is great as performance scales well with the amount of data in the container regardless of the shape. This is great but even greater performance can be achieved with unsorted implementations given the right data. Hash-based containers benefit from very efficient operation performance as the result of consistent lookups because of hashing the keys. The unsorted multimap, like the unsorted map, on average performs the insertion, search, and deletion operations in O(1) time. This performance is optimal, making the unsorted multimap an excellent choice for key-value storage. This is not without consequence though. Should the keys collide at a high rate, the performance begins to move towards O(n) across the board. It is important to take into account the shape of your data when considering what kind of associative container to use, and the multimap is no exception.
A few notes
There are a variety of implementations of multimaps with their own trade-offs and features that are really interesting and can give further insight into the multimap data structure. These are a few of my favorite:
- Multimap · google/guava Wiki (github.com)
- multimap — C++ Reference (cplusplus.com)
- unordered_multimap — C++ Reference (cplusplus.com)
- MultiMap (Oracle Fusion Middleware)
- multimap::MultiMap — Rust (docs.rs)
- jwangsadinata/go-multimap (github.com)
For the full source code of the examples used in this article, refer to this repository.
