multimaps

Multimap is a data structure that maps keys to collections of values, enabling a one-to-many relationship. Unlike a standard map, which associates each key with a single value, a multimap stores multiple values for the same key. The per-key collections can be lists, sets, or other containers, and the exact behavior depends on the implementation. Some variants preserve insertion order, others sort keys or values.

In languages with dedicated multimap types, the concept is implemented in slightly different ways. In C++, the standard library provides std::multimap, a container of key-value pairs in which keys may repeat; searching for a key yields the range of all elements with that key. In Java, libraries such as Guava expose a Multimap abstraction that maps a key to a collection of values; implementations include ArrayListMultimap (values in a list) and HashMultimap (values stored in a set).

In Python, there is no built-in multimap type, but a common pattern uses collections.defaultdict to accumulate values under a key, e.g., defaultdict(list). Other languages offer various flavors, including per-key lists, per-key sets, or more complex backings.

Common operations include inserting values for a key, retrieving all values for a key as a collection, and removing or replacing the value collection. Performance depends on the backend: hash-based mappings are typically near-constant time for insert and lookup, while ordered structures offer logarithmic complexity and sorted traversal. Use cases include tagging, indexing, and grouping query results.

Considerations include memory usage, whether duplicate values are allowed for a key, and whether per-key ordering or uniqueness is required. When a single key must be associated with many distinct values, a multimap is often preferable to a map of collections, as it centralizes the relationship and provides convenient APIs.

See also: Map, Hash map, List, Set, Multiset.