Community hub
0 subscribers7 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Multimap.
Nothing was collected or created yet.
Multimap
View on Wikipediafrom Wikipedia
 | This article needs additional citations for verification. (February 2022) |
In computer science, a multimap (sometimes also multihash, multidict or multidictionary) is a generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key. Both map and multimap are particular cases of containers (for example, see C++ Standard Template Library containers). Often the multimap is implemented as a map with lists or sets as the map values.
Examples
[edit]- In a student enrollment system, where students may be enrolled in multiple classes simultaneously, there might be an association for each enrollment of a student in a course, where the key is the student ID and the value is the course ID. If a student is enrolled in three courses, there will be three associations containing the same key.
- The index of a book may report any number of references for a given index term, and thus may be coded as a multimap from index terms to any number of reference locations or pages.
- Querystrings may have multiple values associated with a single field. This is commonly generated when a web form allows multiple check boxes or selections to be chosen in response to a single form element.
Language support
[edit]C++
[edit]C++'s Standard Template Library provides the multimap container for the sorted multimap using a self-balancing binary search tree,[1] and SGI's STL extension provides the hash_multimap container, which implements a multimap using a hash table.[2]
As of C++11, the Standard Template Library provides the unordered_multimap for the unordered multimap.[3]
Dart
[edit]Quiver provides a Multimap for Dart.[4]
Java
[edit]Apache Commons Collections provides a MultiMap interface for Java.[5] It also provides a MultiValueMap implementing class that makes a MultiMap out of a Map object and a type of Collection.[6]
Google Guava provides a Multimap interface and implementations of it.[7]
Kotlin
[edit]Kotlin does not have explicit support for multimaps,[8] but can implement them using Maps with containers[9] for the value type. E.g. a Map<User, List<Book>> can associate each User with a list of Books.
Python
[edit]Python provides a collections.defaultdict class that can be used to create a multimap. The user can instantiate the class as collections.defaultdict(list).
OCaml
[edit]OCaml's standard library module Hashtbl implements a hash table where it's possible to store multiple values for a key.
Scala
[edit]The Scala programming language's API also provides Multimap and implementations.[10]
See also
[edit]- Multiset for the case where same item can appear several times
References
[edit]- ^ "multimap<Key, Data, Compare, Alloc>". Standard Template Library Programmer's Guide. Silicon Graphics International.
- ^ "hash_multimap<Key, HashFcn, EqualKey, Alloc>". Standard Template Library Programmer's Guide. Silicon Graphics International.
- ^ "Working Draft, Standard for Programming Language C++" (PDF). p. 7807.
- ^ "Multimap". Quiver API docs.
- ^ "Interface MultiMap". Commons Collections 3.2.2 API, Apache Commons.
- ^ "Class MultiValueMap". Commons Collections 3.2.2 API, Apache Commons.
- ^ "Interface Multimap<K,V>". Guava Library 2.0. Archived from the original on 2013-01-15. Retrieved 2013-01-01.
- ^ "Implement a MultiMap in Kotlin | Baeldung on Kotlin". 5 December 2023.
- ^ "Accessing data using Room DAOs".
- ^ "Scala.collection.mutable.MultiMap". Scala stable API.
Multimap
View on Grokipediafrom Grokipedia
A multimap is an abstract data type in computer science that generalizes the associative array by permitting multiple values to be associated with a single key, unlike a standard map which enforces unique keys.[1][2] This structure stores elements as key-value pairs.[1][3]
In implementations such as the C++ Standard Template Library (STL),
This approach was enabled by the introduction of
For immutable multimaps, developers often use
std::multimap is an associative container that maintains keys in sorted order based on a comparison function, defined in the <map> header, supporting bidirectional iterators and operations like insertion, erasure, and range queries with average logarithmic time complexity.[1][2] It differs from std::map primarily by allowing duplicate keys, with equivalent keys preserving their relative insertion order during traversal since C++11.[1] While keys remain immutable, associated values can be modified post-insertion.[2]
Multimaps find applications in scenarios requiring grouped associations, such as storing multiple events under a single date in a calendar system or multiple courses linked to a student identifier.[3] They are also used in language implementations beyond C++, including Java's Guava library[4] and Python's third-party collections such as MultiMap,[5] for efficient handling of non-unique mappings in algorithms and data processing.
Fundamentals
Definition
A multimap is a generalization of the map or associative array abstract data type, allowing multiple values to be associated with a single key rather than enforcing a strict one-to-one correspondence as in standard maps.[6] This structure supports scenarios where a key naturally relates to several values, such as indexing multiple entries under the same identifier.[6] Formally, a multimap is a dynamic collection of key-value pairs , where multiple pairs may share the same key , and the values associated with each key form a multiset upon which operations are defined. Standard maps represent a special case of this structure, restricting each key to at most one value.[7] Multimaps differ from multisets, which are collections permitting duplicate elements but lacking explicit keys to associate values, thereby maintaining no key-value pairing semantics. Instead, multimaps explicitly preserve these associations, enabling keyed retrieval of multiple values.[8][1]Comparison to Standard Maps
A standard map, also known as an associative array or dictionary, enforces unique keys where each key maps to exactly one value, ensuring no duplicate keys exist within the structure. In contrast, a multimap extends this by allowing duplicate keys, with each key associating to multiple values, often stored as a collection such as a list or set to group related items.[9][2][10] Both data structures share fundamental similarities in their associative nature, supporting efficient lookups, insertions, and deletions based on keys through mechanisms like balanced binary search trees (e.g., red-black trees) or hashing, typically achieving O(log n) time complexity for ordered variants and average O(1) for unordered ones. They also utilize key-value pairs as the core unit of storage and iteration, enabling ordered or unordered traversal depending on the implementation.[11][10] The primary trade-offs arise in efficiency and flexibility: standard maps provide optimal performance and minimal storage for scenarios requiring unique associations, as each key requires only a single value slot, whereas multimaps introduce overhead in both space—due to storing multiple entries or nested collections per key—and potentially in access time when retrieving or managing value groups. This makes multimaps preferable when one-to-many relationships are essential, but standard maps more efficient for strict one-to-one mappings.[11][12][10] For instance, a standard map suits mapping unique usernames to individual user profiles, ensuring fast and direct access without redundancy, while a multimap is ideal for linking tags to multiple documents, accommodating the scenario where a single tag applies to numerous resources.[10][2]Key Characteristics
Multiple Values per Key
A multimap's defining feature is its ability to associate multiple values with a single key, enabling more expressive data structures for scenarios where one-to-many relationships are natural, in contrast to standard maps that enforce a one-to-one mapping. This multiplicity enhances flexibility, allowing representations like word frequencies in text or multiple attributes per entity without requiring composite keys.[13][14] The values linked to a key form an underlying collection, whose type determines the collection's nature: unordered for bags, ordered for lists or trees, or set-like for uniqueness enforcement. For instance, in list-based variants such as ListMultimap, values maintain insertion order and permit duplicates, treating the association as a sequence. In contrast, set-based variants like SetMultimap enforce uniqueness among values per key, rejecting duplicates to prevent redundancy while still allowing multiple distinct values. C++'s std::multimap, being a sorted associative container, stores values for identical keys adjacently in order, inherently supporting duplicates as separate key-value pairs.[15][16][2] Accessing values for a key typically yields a view of the associated collection rather than a full copy, promoting efficient iteration over the elements without duplicating storage. This view remains synchronized with the multimap's state, so modifications to the values (where permitted) reflect back in the structure. For example, in Java's Guava library, the get method returns a live collection view, while in C++, equal_range provides iterator bounds to traverse the relevant pairs.[14][2] Edge cases arise with keys lacking values, where most implementations treat such keys as absent, returning an empty collection upon query without storing an explicit empty entry to conserve space. This uniformity simplifies behavior: a count query for an unassociated key yields zero, and removal operations have no effect, mirroring the absence in standard maps but via an empty iterable. In designs allowing explicit empty collections, a key might persist with a zero-sized view, though this variant is less common and depends on the specific multimap abstraction.[14][2][13]Key-Value Pairing Behavior
In ordered multimaps, such as those implemented using balanced tree structures, keys are maintained in a sorted sequence based on a provided comparison function, typically the less-than operator for the key type, ensuring that all pairs with equivalent keys are grouped adjacently in the traversal order.[1] Within each group of equivalent keys, the key-value pairs are ordered according to their insertion sequence, maintaining stability such that the relative order of insertions with the same key remains unchanged unless explicitly modified.[1] This grouping facilitates efficient range queries for all values associated with a specific key, as equal keys form a contiguous block in the sorted structure.[1] Key equality is established using the comparison function, where two keys are considered equivalent if neither is strictly less than the other, allowing multiple pairs to share the identical key without conflict.[1] Values associated with a key have no inherent ordering imposed by the multimap unless a variant like a sorted-set multimap is used, in which case the value collection may be sorted independently.[14] This equality rule applies standard language semantics, such as the == operator for built-in types, but relies on the comparator for custom key types to define equivalence consistently across the structure.[1] Consistency in key-value pairing is governed by thread-safety models that vary across implementations; for instance, standard library multimaps like std::multimap permit concurrent read-only access from multiple threads but require external synchronization for modifications to avoid data races or iterator invalidation. Some libraries provide immutable multimap variants, where the structure is frozen after construction to ensure thread-safe sharing without locks, or concurrent implementations that support lock-free updates under specific conditions.[14] These models preserve the integrity of pairings during access, preventing key mismatches or lost values in multi-threaded environments. Internally, multimaps represent pairings as explicit key-value pairs, duplicating the key in each entry to accommodate multiple values, which allows direct storage and retrieval without aggregating values into separate collections until queried.[1] This explicit duplication ensures that each pair is treated as a distinct element in operations like iteration or searching, while still enabling grouped access for equivalent keys.[1] Such representation supports the core concept of multiple values per key by maintaining full visibility of each individual association in the underlying sequence.[14]Operations
Insertion and Update
In multimap data structures, insertion operations typically append new values to the existing collection associated with a given key, preserving all prior values without overwriting them. This behavior distinguishes multimaps from standard maps, where keys map to single values. For instance, theinsert method in C++'s std::multimap adds a key-value pair by placing it at the upper bound among equivalent keys, allowing multiple entries per key in sorted order.[17] Similarly, in Java's Guava library, the put method in Multimap associates a value with a key by adding it to the key's collection, which may be a list or set depending on the implementation.[18]
Update variants in multimap APIs provide flexibility for modifying associations, often through methods that either append or conditionally add based on the multimap type. In Guava's SetMultimap, for example, put(key, value) adds the value only if it is not already present for that key, returning true if the multimap size increases and false otherwise to indicate no change due to duplicates.[18] In contrast, ListMultimap always appends via put, even for duplicates, and returns true since the size always grows.[19] While explicit "upsert" operations (insert if absent, update if present) are not standard in core multimap interfaces, conditional addition like that in SetMultimap serves a similar purpose by avoiding redundant entries. In C++ std::multimap, insertion always appends without built-in conditional checks, requiring manual verification if uniqueness is needed.[17]
Batch insertion methods enable efficient addition of multiple values, often from iterables or other collections, to support bulk operations. Guava's Multimap offers putAll(key, iterable) to add all elements from an iterable to a single key's collection, returning true if any additions occur, and putAll(multimap) to merge pairs from another multimap while respecting the source's entry order.[18] In C++ std::multimap, range-based insert(first, last) or initializer list insertion allows adding multiple key-value pairs at once, with no return value but increasing the container size accordingly.[17] These approaches optimize for scenarios involving large datasets, such as aggregating logs or configurations.
Return values from insertion operations provide feedback on the outcome, aiding in error handling or verification. In C++ std::multimap, single-element insert returns an iterator to the newly inserted position, facilitating immediate access or chaining, while batch methods return void.[17] Guava's put and putAll methods consistently return a boolean indicating whether the multimap was modified, which is particularly useful in SetMultimap to detect skipped duplicates.[18] Such indicators ensure that applications can confirm successful accumulation of multiple values per key without additional queries.
Retrieval and Iteration
Retrieval in a multimap involves accessing the values associated with a specific key, typically through a method that returns a collection or iterator over those values. For instance, theget(key) operation yields a view of the values linked to the key, allowing efficient access without copying the data.[18] To determine if a key exists, the containsKey(key) method returns true if at least one value is mapped to it, enabling preliminary checks before retrieval.[18] In ordered multimap implementations, such as those using balanced trees, retrieval can leverage range-based lookups to isolate elements with the given key.[1]
Iteration over a multimap supports traversal of its entire contents through dedicated views that provide access to keys, values, or pairs without exposing the underlying storage. The entrySet() view returns all key-value pairs as entries, facilitating operations like processing each association individually.[18] Similarly, keySet() offers a collection of unique keys, while values() provides all values with their multiplicity, preserving duplicates from multiple mappings.[18] For ordered variants, full traversal follows the sorted order of keys, and iterators are bidirectional to support forward and reverse navigation.[1] Range queries in these structures, such as equal_range(key), delimit the iterators bounding all elements for a key, enabling targeted iteration over subsets.[1]
Value access patterns in multimaps emphasize enumeration over direct random access, aligning with the associative nature of the structure. For keys with multiple values stored in ordered collections like lists, direct indexing into the value sequence is possible after retrieval, such as accessing the n-th value via get(key).get(n).[19] In set-based implementations, values are unordered, so foreach-style enumeration is the primary pattern, iterating without indices to process all associations.[20] These patterns ensure that modifications to the retrieved view propagate back to the multimap, maintaining consistency during traversal.[18]
When a key is absent from the multimap, retrieval operations return an empty collection or iterator range rather than null or throwing an exception, promoting safe and predictable code without additional null checks.[18] This behavior applies uniformly: get(key) yields an empty view, containsKey(key) returns false, and range queries produce iterators pointing to the end of the container.[1] Such handling facilitates robust applications where keys may be queried speculatively.[18]
Deletion and Size Management
Deletion operations in a multimap typically allow for the removal of all values associated with a specific key or the targeted removal of individual value instances for a given key. Theremove(key) method erases all entries sharing that key, effectively eliminating the key from the multimap if no values remain, as implemented in standard C++ std::multimap where erase(key) returns the count of removed elements and leaves no trace of the key. Similarly, in Java's Guava library, removeAll(key) removes all values for the key and returns the deleted collection, with the key being absent thereafter if emptied.[21]
For more granular control, the remove(key, value) operation deletes specific occurrences of a value under the key, returning a boolean indicating success, and may leave the key intact if other values persist. This is evident in Hazelcast's MultiMap where remove(key, value) targets individual pairs without affecting others for the same key.[22] In C++, erase(iterator) provides iterator-based removal for precise control over individual elements, invalidating only the targeted iterator while preserving the rest. Post-deletion, keys with no remaining values are generally not retained in the structure, ensuring the multimap reflects only populated associations, though some designs may require explicit cleanup.[23]
The clear() operation empties the entire multimap by removing all key-value pairs, reducing it to an empty state without preserving any data. This is a standard method across implementations, such as std::multimap::clear() which destroys all elements efficiently.
Size management in multimaps involves queries for the overall scale and per-key details. The size() method returns the total number of key-value pairs, counting multiplicities—for instance, a key with three values contributes three to the total in Guava's Multimap.size().[24] To obtain the number of distinct keys, implementations often provide access via keySet().size() or equivalent, as in Hazelcast where it yields the count of unique keys with at least one value.[22] For value counts per key, retrieval of the associated collection (e.g., via get(key)) followed by its size() query is common; in C++, use the count(key) method or std::distance between the iterators from equal_range(key) to determine the number of values for a key, allowing assessment of multiplicity without altering the structure. The empty() check verifies if the total size is zero, useful for post-deletion validation.
Use Cases
Data Aggregation Scenarios
Multimaps are particularly useful in grouping operations where data needs to be aggregated by categories, allowing multiple values to be associated with each key without requiring separate list structures. A representative example is in search indexing, where terms are mapped to lists of document identifiers that contain them, effectively creating an inverted index for efficient retrieval. This structure supports rapid aggregation of related items, such as compiling all occurrences of a word across documents during query processing.[6] In frequency counting scenarios, multimaps enable tallying occurrences by inserting duplicate key-value pairs directly, with the count of values per key providing the frequency metric without preprocessing steps like explicit incrementation. For instance, repeated insertions of the same key with identical or varying values allow straightforward computation of totals using built-in count operations, preserving the original data entries for further analysis. This approach is advantageous in dynamic environments where occurrences arrive incrementally.[25] Event logging applications leverage multimaps to associate multiple events with keys like user identifiers or timestamps, facilitating the accumulation of logs without overwriting prior entries. Keys representing users can hold lists of actions performed, while timestamp keys can aggregate concurrent or sequential events, enabling efficient querying and analysis of temporal or user-specific patterns. Insertion operations build these aggregations incrementally as events occur (as of 2025).[26] The multimap concept emerged in the late 1990s as part of the C++ Standard Template Library, developed by Alexander Stepanov while at Hewlett-Packard Laboratories and standardized in the C++98 standard to handle associative data with duplicates.[27][1] Its utility extended to database query results, such as GROUP BY operations producing multiple rows per key, and graph representations like adjacency lists mapping nodes to multiple neighbors.Configuration and Indexing Applications
Multimaps find significant application in configuration management, where a single key represents a parameter or setting that can map to multiple values, such as aliases or options. For instance, in systems like Apache Commons Configuration, properties files or XML configurations can define multi-valued entries, allowing a key like "database.host" to associate with several server addresses or fallback options without requiring separate keys for each. This approach simplifies parsing and validation of settings in applications, enabling flexible handling of optional configurations like command-line flags, where a flag such as "--verbose" might alias to multiple logging levels or behaviors defined in a properties file. In indexing structures, multimaps are particularly suited for implementing inverted indexes, which map terms or keywords to lists of documents or positions where they appear. An inverted index can be modeled as a multimap where each key is a term from a corpus, and the associated values form a posting list of document identifiers containing that term, facilitating efficient retrieval for search queries.[6] This structure underpins full-text search engines, as seen in conceptual designs where the multimap abstraction directly supports the one-to-many relationship between terms and occurrences, enabling operations like union or intersection of posting lists for query processing.[6] Multimaps also enhance caching mechanisms by allowing a single key to cache multiple related resources, such as variants of an object or query results under a shared identifier. In distributed caching systems like Hazelcast's IMultiMap (as of 2025), a key representing a user session can store multiple associated tokens or preferences, ensuring atomic updates and retrievals across nodes without duplicating keys.[28] Similarly, Red Hat Data Grid's MultimapCache (as of 2025) supports this by mapping keys to collections of values, ideal for scenarios like caching multiple API responses tied to a common endpoint.[29] Compared to standard maps, multimaps offer key advantages in handling optional or variable associations by inherently supporting multiple values per key, thus avoiding the need for null values or sentinel entries to represent absence. For example, in Google Guava's Multimap implementation, theget(key) method returns an empty collection rather than null when no values exist, preventing NullPointerExceptions and simplifying code for scenarios with unpredictable multiplicity.[30] This design promotes cleaner APIs for lookup-oriented uses, as developers do not need to manually initialize collections like lists for each key insertion.[30]
Implementations
Underlying Data Structures
Multimaps are commonly implemented as a combination of a map data structure associating each key with a collection of values, such as a list for allowing duplicates or a set for unique values per key. For unordered multimaps, the underlying map is typically a hash table mapping keys to dynamic arrays (lists) or hash sets, enabling average O(1) access to value collections.[31] In ordered multimaps, a balanced binary search tree, such as a red-black tree, serves as the map, pairing keys with sorted collections like ordered lists or tree sets to maintain key ordering.[32] Specific variants illustrate these designs. The C++ standard library'sstd::multimap employs a red-black tree where each node stores a std::pair<const Key, T> (key-value pair), allowing multiple entries with identical keys by treating the pair as the comparable element, thus preserving insertion order among equivalent keys.[32] In contrast, Java's Guava library provides Multimap implementations like HashMultimap, which uses a HashMap<Key, Collection<Value>> backend with customizable value collections (e.g., ArrayList for multisets or HashSet for uniqueness), and TreeMultimap, which substitutes a TreeMap for sorted keys and a TreeSet for ordered values.[31]
These structures incur storage overhead primarily from the per-key value collections, including object headers, pointers to the map entries, and capacity allocations in arrays or linked lists even for sparse or single-value cases. Each collection instance adds fixed metadata, compounded by hash table load factors or tree node pointers (typically 3 pointers per node in red-black trees).
The concept of multimaps evolved from ad-hoc implementations in 1990s software, where developers manually paired maps with vectors or lists for multiple values, to formal standardization in the C++98 library via std::multimap and std::unordered_multimap (added in C++11). In Java, native support emerged later through third-party libraries, with Guava's Multimap framework later integrated from Google Collections.[33]
Performance Considerations
The performance of a multimap is largely determined by its underlying data structure, such as balanced binary search trees or hash tables. For tree-based implementations, insertion, retrieval (e.g., finding the range of values for a key), and deletion operations exhibit time complexity, where is the number of unique keys, due to the balanced tree maintenance. In contrast, hash-based implementations achieve average-case time complexity for these operations, though worst-case performance can degrade to in the presence of hash collisions.[1][34] Iteration over the values associated with a specific key takes time, where is the multiplicity (number of values) for that key, as values are typically stored in a linked list or similar linear structure within the key's node or bucket. Full traversal of all elements in the multimap requires time, with denoting the total number of value mappings. These complexities stem from hash tables enabling constant-time key access, which underpins efficient multimap behavior in average cases.[34][1] Space complexity for a multimap is , accounting for storage of unique keys and total values, along with overhead from the underlying collections (e.g., pointers or hash table buckets). This linear scaling holds for both tree- and hash-based variants, as each mapping requires dedicated memory.[1][35] Key bottlenecks arise when multiplicity is high, resulting in large value lists that slow down operations like full retrieval or iteration for a single key, potentially leading to excessive memory traversal and cache inefficiencies. In concurrent environments, thread-safe multimaps incur additional costs from synchronization mechanisms, such as per-key locking, which can reduce throughput compared to non-concurrent versions by introducing contention overhead.[36][37] For handling sparse key distributions, bucketing strategies in hash-based multimaps distribute entries across fixed-size buckets to minimize collision chains and improve load factor efficiency.[38]Programming Language Support
C++ and Java
In C++, the Standard Template Library (STL) provides native support for multimaps through two primary classes:std::multimap and std::unordered_multimap. The std::multimap class, introduced in the C++98 standard, is an ordered associative container implemented as a balanced binary search tree (typically red-black tree), storing key-value pairs sorted by key using the less-than comparator by default. It allows multiple equivalent keys, with elements inserted in non-decreasing key order. Key operations include insert(), which adds a new key-value pair (with logarithmic time complexity), equal_range(key), which returns a range of iterators to all elements with the given key (also logarithmic), and erase(key), which removes all elements associated with the specified key (logarithmic in the number of elements erased).
Introduced in the C++11 standard, std::unordered_multimap offers an unordered, hash-based alternative from the <unordered_map> header, providing average constant-time complexity for insertions, lookups, and erasures under good hash distribution. Like its ordered counterpart, it supports multiple values per key, with insert() adding pairs without ordering, equal_range(key) yielding a bucket-range iterator for all matching elements (amortized constant time), and erase(key) removing all instances of the key (linear in the number of elements erased). Both classes leverage C++ templates for flexible key and value types, enabling compile-time type safety and customization via allocators and comparators (for ordered) or hash functions (for unordered).[39][40]
Java's standard library, as defined in the Java Platform, Standard Edition (Java SE), lacks a built-in multimap implementation, requiring developers to simulate it using a java.util.Map where values are collections such as List or Set (e.g., Map<Key, List<Value>>).[30] This approach involves manual management of inner collections for insertions and retrievals, which can lead to boilerplate code. For dedicated support, the Google Guava library introduces the Multimap interface in its collections module, originating in the predecessor Google Collections library (first versions released in 2008, with version 1.0 on December 30, 2009) and integrated into Guava starting with version 2.0 in early 2010.[14][41] Implementations like HashMultimap, ArrayListMultimap, and TreeMultimap provide varying backing structures, with core methods including put(key, value) for adding values (potentially creating new keys), get(key) returning a mutable collection view of values (empty for absent keys), and asMap() yielding a read-only Map view of keys to value collections. Guava's design emphasizes generics for type parameterization and offers immutable variants via ImmutableMultimap for thread-safe, unmodifiable instances.
While C++ multimaps are integral to the language's standard library and prioritize template-based flexibility for performance-critical systems programming, Java's reliance on third-party libraries like Guava highlights a focus on generics-enabled interfaces and convenient, immutable views to enhance usability in enterprise applications.[42]
Python and Scala
In Python, there is no dedicated multimap class in the standard library, but thecollections.defaultdict with a list as the default factory is a common idiom for implementing multimap behavior, where multiple values for a key are stored in a list and appended as needed.[43] For example, the following code demonstrates adding values:
python
from collections import defaultdict
multimap = defaultdict(list)
multimap['key1'].append('value1')
multimap['key1'].append('value2')
print(multimap['key1']) # Output: ['value1', 'value2']
from collections import defaultdict
multimap = defaultdict(list)
multimap['key1'].append('value1')
multimap['key1'].append('value2')
print(multimap['key1']) # Output: ['value1', 'value2']
defaultdict in Python 2.5, released in 2006.[44] Third-party libraries, such as the MultiMap package available on PyPI, offer more explicit multimap implementations with features like order preservation for values.[5]
In Scala, the standard library provides the MultiMap trait in the scala.collection.mutable package, which extends Map to support multiple values per key by internally mapping keys to mutable sets of values. The MultiMap trait, available since at least Scala 2.7 (2008), was part of the standard library and refined in later versions like 2.8 (2010).[45] This trait is typically mixed into concrete mutable map classes, allowing operations like +=(key, value) to add a value to the set associated with the key without overwriting existing ones. For instance:
scala
import scala.collection.mutable.{HashMap, MultiMap}
val multimap: HashMap[String, String] with MultiMap[String, String] = HashMap.empty
multimap += ("key1" -> "value1")
multimap += ("key1" -> "value2")
println(multimap("key1")) // Output: Set(value1, value2)
import scala.collection.mutable.{HashMap, MultiMap}
val multimap: HashMap[String, String] with MultiMap[String, String] = HashMap.empty
multimap += ("key1" -> "value1")
multimap += ("key1" -> "value2")
println(multimap("key1")) // Output: Set(value1, value2)
immutable.Map[K, immutable.Set[V]] compositions, leveraging Scala's persistent data structures for thread-safe and functional-style usage.
Python's multimap patterns emphasize simplicity and flexibility in dynamic, scripting environments, while Scala's offerings prioritize type safety, with mutable traits for efficiency and immutable alternatives for concurrency and functional purity.
Other Languages
In Dart, multimap functionality is not part of the core libraries but is readily available through popular packages like quiver, which provides aMultimap class in its collection module. This class allows mapping keys to multiple values, supporting operations such as add(key, value) to append values to a key's collection, remove(key, value) to eliminate specific value instances, and iteration methods like keys and values for traversing the structure. Similarly, the built_collection package offers immutable alternatives, such as ListMultimap, emphasizing efficient, type-safe handling in Dart's object-oriented ecosystem.[46]
Kotlin lacks a native multimap type in its standard library, instead encouraging implementations via extensions on MutableMap where values are lists or sets to accommodate multiple entries per key. Developers commonly use the groupBy function from the collections package to transform iterables into map-like structures with grouped values, enabling concise multimap behavior without dedicated classes. This approach aligns with Kotlin's idiomatic emphasis on functional extensions and interoperability with Java's collections, such as Guava's Multimap.[47]
In OCaml, the standard Map module from the core library supports ordered associations but is limited to single values per key, requiring manual augmentation with lists for multimap semantics. Specialized libraries like containers address this by providing CCMultiMap, a module for bidirectional n-to-n mappings that supports efficient addition, removal, and querying of key-value associations. This reflects OCaml's functional paradigm, where such structures enhance type-safe data aggregation in applications like symbolic computation.
Since the 2010s, modern languages have shown growing support for multimap constructs through libraries and built-in grouping utilities, driven by demands for concise handling of relational data in web, mobile, and data-processing domains. This trend facilitates paradigm-agnostic operations like aggregation and indexing across diverse ecosystems. In contrast, older languages like C provide no native multimap support, compelling programmers to implement custom solutions using structs, arrays, or pointers for key-list associations.[48]