Multimap
Overview
A Multimap is an abstract data type that associates a single key with multiple values. Unlike a standard map, a multimap allows duplicate keys, each mapping to one or more values.
It is useful when relationships are one-to-many.
What Is a Multimap?
A multimap:
- Allows multiple values per key
- Maintains key-based access
- Often implemented as a map of collections
Keys remain unique at the top level, values do not.
How It Works
Internally, a multimap is commonly implemented as:
Map<Key, Collection<Value>>
Each key points to a list, set, or another container of values.
Example
Pseudocode
students["Math"] = ["Anu", "Ravi"]
students["Science"].add("Kiran")
Real-world Analogy
A multimap is like a course enrollment list. One course name, many students 🎓📋.
Core Operations
| Operation | Description |
|---|---|
| Put | Add value to a key |
| Get | Retrieve all values for a key |
| Remove | Remove one or all values |
| Contains | Check key or value |
| Iterate | Traverse keys and values |
Time Complexity
Depends on underlying map and collection:
- Key access: O(1) or O(log n)
- Value insertion: O(1) (amortized)
Use Cases
- Grouping data
- Inverted indexes
- Tagging systems
- Graph adjacency lists
Advantages
- Models one-to-many relationships
- Clean abstraction
- Flexible value storage
Limitations
- Slightly more complex than maps
- Higher memory usage
- Ordering depends on implementation