0
# Multi-Valued Maps (MultiMaps)
1

2
Multi-valued maps allow multiple values to be associated with each key. Unlike regular maps which have a 1:1 key-value relationship, multi-valued maps support 1:many relationships where each key can map to a collection of values.
3

4
## Core Interfaces
5

6
### MultiValuedMap<K, V> Interface
7

8
The primary interface for multi-valued maps that associates collections of values with keys.
9

10
```java { .api }
11
import org.apache.commons.collections4.MultiValuedMap;
12
import org.apache.commons.collections4.multimap.ArrayListValuedHashMap;
13
import java.util.Collection;
14

15
MultiValuedMap<String, String> multiMap = new ArrayListValuedHashMap<>();
16

17
// Add multiple values for the same key
18
multiMap.put("colors", "red");
19
multiMap.put("colors", "green");
20
multiMap.put("colors", "blue");
21
multiMap.put("animals", "cat");
22
multiMap.put("animals", "dog");
23

24
// Get all values for a key (returns Collection<V>)
25
Collection<String> colors = multiMap.get("colors");     // ["red", "green", "blue"]
26
Collection<String> animals = multiMap.get("animals");   // ["cat", "dog"]
27
Collection<String> empty = multiMap.get("plants");      // [] (empty collection)
28

29
// Check presence
30
boolean hasColors = multiMap.containsKey("colors");     // true
31
boolean hasRed = multiMap.containsValue("red");         // true
32
boolean hasMapping = multiMap.containsMapping("colors", "red"); // true
33

34
// Size operations
35
int totalMappings = multiMap.size();                    // 5 (total key-value pairs)
36
int uniqueKeys = multiMap.keySet().size();              // 2 (colors, animals)
37
boolean isEmpty = multiMap.isEmpty();                   // false
38

39
// Remove operations
40
boolean removed = multiMap.removeMapping("colors", "red"); // Remove specific mapping
41
Collection<String> removedColors = multiMap.remove("colors"); // Remove all values for key
42
```
43

44
### ListValuedMap<K, V> Interface
45

46
A multi-valued map where each key maps to a List of values, preserving order and allowing duplicates.
47

48
```java { .api }
49
import org.apache.commons.collections4.ListValuedMap;
50
import org.apache.commons.collections4.multimap.ArrayListValuedHashMap;
51
import java.util.List;
52

53
ListValuedMap<String, Integer> scores = new ArrayListValuedHashMap<>();
54

55
// Add scores in order (duplicates allowed)
56
scores.put("Alice", 85);
57
scores.put("Alice", 92);
58
scores.put("Alice", 88);
59
scores.put("Alice", 92); // Duplicate allowed
60

61
// Get as List (preserves order and duplicates)
62
List<Integer> aliceScores = scores.get("Alice");        // [85, 92, 88, 92]
63

64
// List-specific operations on values
65
aliceScores.add(95);                                    // Modifies underlying multimap
66
int firstScore = aliceScores.get(0);                    // 85
67
int lastScore = aliceScores.get(aliceScores.size() - 1); // 95
68
```
69

70
### SetValuedMap<K, V> Interface  
71

72
A multi-valued map where each key maps to a Set of values, ensuring uniqueness.
73

74
```java { .api }
75
import org.apache.commons.collections4.SetValuedMap;
76
import org.apache.commons.collections4.multimap.HashSetValuedHashMap;
77
import java.util.Set;
78

79
SetValuedMap<String, String> permissions = new HashSetValuedHashMap<>();
80

81
// Add permissions (duplicates automatically ignored)
82
permissions.put("admin", "read");
83
permissions.put("admin", "write");
84
permissions.put("admin", "delete");
85
permissions.put("admin", "read");  // Duplicate ignored
86

87
// Get as Set (no duplicates)
88
Set<String> adminPerms = permissions.get("admin");      // ["read", "write", "delete"]
89

90
// Set-specific operations
91
boolean hasReadPerm = adminPerms.contains("read");      // true
92
int uniquePerms = adminPerms.size();                    // 3
93
```
94

95
## Concrete Implementations
96

97
### ArrayListValuedHashMap<K, V>
98

99
HashMap-based implementation that stores values in ArrayList collections.
100

101
```java { .api }
102
import org.apache.commons.collections4.multimap.ArrayListValuedHashMap;
103
import java.util.Arrays;
104
import java.util.List;
105

106
ArrayListValuedHashMap<String, String> topics = new ArrayListValuedHashMap<>();
107

108
// Bulk operations
109
topics.putAll("java", Arrays.asList("collections", "streams", "generics"));
110
topics.putAll("python", Arrays.asList("lists", "dictionaries", "comprehensions"));
111

112
// Values maintain insertion order and allow duplicates
113
topics.put("java", "collections"); // Duplicate allowed
114
List<String> javaTopics = topics.get("java"); // ["collections", "streams", "generics", "collections"]
115

116
// Capacity optimization for known sizes
117
ArrayListValuedHashMap<String, Integer> optimized = new ArrayListValuedHashMap<>();
118
// Internal ArrayLists start with default capacity
119
```
120

121
### HashSetValuedHashMap<K, V>
122

123
HashMap-based implementation that stores values in HashSet collections.
124

125
```java { .api }
126
import org.apache.commons.collections4.multimap.HashSetValuedHashMap;
127
import java.util.Arrays;
128
import java.util.Set;
129

130
HashSetValuedHashMap<String, String> tags = new HashSetValuedHashMap<>();
131

132
// Bulk operations with automatic deduplication
133
tags.putAll("article1", Arrays.asList("java", "tutorial", "beginner", "java")); // Duplicate "java" ignored
134
tags.putAll("article2", Arrays.asList("python", "advanced", "tutorial"));
135

136
// Values are unique within each key
137
Set<String> article1Tags = tags.get("article1");       // ["java", "tutorial", "beginner"]
138

139
// Fast contains operations (Set performance)
140
boolean hasJavaTag = tags.containsMapping("article1", "java"); // true - O(1) average case
141
```
142

143
## Multi-Valued Map Operations
144

145
### Adding Values
146

147
```java { .api }
148
MultiValuedMap<String, String> contacts = new ArrayListValuedHashMap<>();
149

150
// Single value additions
151
contacts.put("John", "john@work.com");
152
contacts.put("John", "john@personal.com");
153
contacts.put("John", "john@mobile.com");
154

155
// Bulk additions
156
contacts.putAll("Jane", Arrays.asList("jane@work.com", "jane@home.com"));
157

158
// Add to existing collection
159
Collection<String> johnEmails = contacts.get("John");
160
johnEmails.add("john@backup.com"); // Modifies underlying multimap
161

162
// Conditional addition
163
if (!contacts.containsMapping("John", "john@spam.com")) {
164
    contacts.put("John", "john@spam.com");
165
}
166
```
167

168
### Removing Values
169

170
```java { .api }
171
// Remove specific key-value mapping
172
boolean removed = contacts.removeMapping("John", "john@mobile.com"); // true
173
boolean notRemoved = contacts.removeMapping("John", "nonexistent"); // false
174

175
// Remove all values for a key  
176
Collection<String> janeEmails = contacts.remove("Jane"); // Returns and removes all values
177
// janeEmails = ["jane@work.com", "jane@home.com"]
178

179
// Remove through collection view
180
Collection<String> johnEmails = contacts.get("John");
181
johnEmails.remove("john@work.com"); // Modifies underlying multimap
182

183
// Clear all mappings
184
contacts.clear();
185
```
186

187
### Querying and Iteration
188

189
```java { .api }
190
MultiValuedMap<String, Integer> studentGrades = new ArrayListValuedHashMap<>();
191
studentGrades.putAll("Alice", Arrays.asList(85, 92, 78, 95));
192
studentGrades.putAll("Bob", Arrays.asList(88, 76, 82));
193

194
// Key iteration
195
for (String student : studentGrades.keySet()) {
196
    System.out.println("Student: " + student);
197
}
198

199
// Value iteration (all values)
200
for (Integer grade : studentGrades.values()) {
201
    System.out.println("Grade: " + grade);
202
}
203

204
// Entry iteration (key-value pairs)
205
for (Map.Entry<String, Integer> entry : studentGrades.entries()) {
206
    System.out.println(entry.getKey() + " scored " + entry.getValue());
207
}
208

209
// Key-collection iteration  
210
for (Map.Entry<String, Collection<Integer>> entry : studentGrades.asMap().entrySet()) {
211
    String student = entry.getKey();
212
    Collection<Integer> grades = entry.getValue();
213
    double average = grades.stream().mapToInt(Integer::intValue).average().orElse(0.0);
214
    System.out.println(student + " average: " + average);
215
}
216
```
217

218
## Advanced Usage Patterns
219

220
### Grouping and Classification
221

222
```java { .api }
223
import java.util.stream.Collectors;
224

225
public class StudentManager {
226
    private final MultiValuedMap<String, Student> studentsByGrade = new ArrayListValuedHashMap<>();
227
    private final MultiValuedMap<String, Student> studentsBySubject = new HashSetValuedHashMap<>();
228
    
229
    public void addStudent(Student student) {
230
        // Group by grade level
231
        studentsByGrade.put(student.getGrade(), student);
232
        
233
        // Group by subjects (Set semantics - each student appears once per subject)
234
        for (String subject : student.getSubjects()) {
235
            studentsBySubject.put(subject, student);
236
        }
237
    }
238
    
239
    public List<Student> getStudentsInGrade(String grade) {
240
        return new ArrayList<>(studentsByGrade.get(grade));
241
    }
242
    
243
    public Set<Student> getStudentsInSubject(String subject) {
244
        return new HashSet<>(studentsBySubject.get(subject));
245
    }
246
    
247
    public Map<String, Long> getGradeDistribution() {
248
        return studentsByGrade.asMap().entrySet().stream()
249
            .collect(Collectors.toMap(
250
                Map.Entry::getKey,
251
                entry -> (long) entry.getValue().size()
252
            ));
253
    }
254
}
255
```
256

257
### Configuration Management
258

259
```java { .api }
260
public class ApplicationConfig {
261
    private final MultiValuedMap<String, String> properties = new ArrayListValuedHashMap<>();
262
    
263
    public void loadConfig(Properties props) {
264
        props.forEach((key, value) -> {
265
            String keyStr = key.toString();
266
            String valueStr = value.toString();
267
            
268
            // Support comma-separated values
269
            if (valueStr.contains(",")) {
270
                String[] values = valueStr.split(",");
271
                for (String v : values) {
272
                    properties.put(keyStr, v.trim());
273
                }
274
            } else {
275
                properties.put(keyStr, valueStr);
276
            }
277
        });
278
    }
279
    
280
    public List<String> getPropertyValues(String key) {
281
        return new ArrayList<>(properties.get(key));
282
    }
283
    
284
    public String getFirstPropertyValue(String key) {
285
        Collection<String> values = properties.get(key);
286
        return values.isEmpty() ? null : values.iterator().next();
287
    }
288
    
289
    public void addPropertyValue(String key, String value) {
290
        properties.put(key, value);
291
    }
292
    
293
    public boolean hasProperty(String key) {
294
        return properties.containsKey(key);
295
    }
296
    
297
    public boolean hasPropertyValue(String key, String value) {
298
        return properties.containsMapping(key, value);
299
    }
300
}
301
```
302

303
### Graph Adjacency Lists
304

305
```java { .api }
306
public class DirectedGraph<T> {
307
    private final MultiValuedMap<T, T> adjacencyList = new HashSetValuedHashMap<>();
308
    
309
    public void addEdge(T from, T to) {
310
        adjacencyList.put(from, to);
311
    }
312
    
313
    public void removeEdge(T from, T to) {
314
        adjacencyList.removeMapping(from, to);
315
    }
316
    
317
    public Set<T> getNeighbors(T vertex) {
318
        return new HashSet<>(adjacencyList.get(vertex));
319
    }
320
    
321
    public Set<T> getAllVertices() {
322
        Set<T> vertices = new HashSet<>(adjacencyList.keySet());
323
        vertices.addAll(adjacencyList.values());
324
        return vertices;
325
    }
326
    
327
    public int getOutDegree(T vertex) {
328
        return adjacencyList.get(vertex).size();
329
    }
330
    
331
    public int getInDegree(T vertex) {
332
        return (int) adjacencyList.entries().stream()
333
            .filter(entry -> entry.getValue().equals(vertex))
334
            .count();
335
    }
336
    
337
    public boolean hasPath(T from, T to) {
338
        if (from.equals(to)) return true;
339
        
340
        Set<T> visited = new HashSet<>();
341
        Queue<T> queue = new LinkedList<>();
342
        queue.offer(from);
343
        visited.add(from);
344
        
345
        while (!queue.isEmpty()) {
346
            T current = queue.poll();
347
            for (T neighbor : getNeighbors(current)) {
348
                if (neighbor.equals(to)) return true;
349
                if (!visited.contains(neighbor)) {
350
                    visited.add(neighbor);
351
                    queue.offer(neighbor);
352
                }
353
            }
354
        }
355
        return false;
356
    }
357
}
358
```
359

360
### Inverted Index
361

362
```java { .api }
363
public class InvertedIndex {
364
    private final MultiValuedMap<String, Document> termToDocuments = new HashSetValuedHashMap<>();
365
    private final MultiValuedMap<Document, String> documentToTerms = new HashSetValuedHashMap<>();
366
    
367
    public void addDocument(Document document) {
368
        Set<String> terms = tokenize(document.getContent());
369
        
370
        for (String term : terms) {
371
            termToDocuments.put(term.toLowerCase(), document);
372
            documentToTerms.put(document, term.toLowerCase());
373
        }
374
    }
375
    
376
    public Set<Document> search(String term) {
377
        return new HashSet<>(termToDocuments.get(term.toLowerCase()));
378
    }
379
    
380
    public Set<Document> searchMultiple(String... terms) {
381
        if (terms.length == 0) return Collections.emptySet();
382
        
383
        Set<Document> result = search(terms[0]);
384
        for (int i = 1; i < terms.length; i++) {
385
            result.retainAll(search(terms[i])); // Intersection
386
        }
387
        return result;
388
    }
389
    
390
    public Set<Document> searchAny(String... terms) {
391
        Set<Document> result = new HashSet<>();
392
        for (String term : terms) {
393
            result.addAll(search(term)); // Union
394
        }
395
        return result;
396
    }
397
    
398
    public void removeDocument(Document document) {
399
        Collection<String> terms = documentToTerms.remove(document);
400
        for (String term : terms) {
401
            termToDocuments.removeMapping(term, document);
402
        }
403
    }
404
    
405
    private Set<String> tokenize(String content) {
406
        // Simple tokenization - in practice, use proper text processing
407
        return Arrays.stream(content.toLowerCase().split("\\W+"))
408
            .filter(s -> !s.isEmpty())
409
            .collect(Collectors.toSet());
410
    }
411
}
412
```
413

414
## Utility Operations
415

416
### MultiMapUtils Class
417

418
```java { .api }
419
import org.apache.commons.collections4.MultiMapUtils;
420

421
// Create empty multimaps
422
MultiValuedMap<String, String> listMap = MultiMapUtils.newListValuedHashMap();
423
MultiValuedMap<String, String> setMap = MultiMapUtils.newSetValuedHashMap();
424

425
// Check if empty (null-safe)
426
boolean isEmpty = MultiMapUtils.isEmpty(null); // true
427
boolean isNotEmpty = MultiMapUtils.isEmpty(listMap); // false (depends on content)
428

429
// Create unmodifiable views
430
MultiValuedMap<String, String> unmodifiable = MultiMapUtils.unmodifiableMultiValuedMap(listMap);
431

432
// Create empty immutable multimap
433
MultiValuedMap<String, String> empty = MultiMapUtils.emptyMultiValuedMap();
434

435
// Transform multimaps
436
Transformer<String, String> upperCase = String::toUpperCase;
437
Transformer<String, String> addPrefix = s -> "prefix_" + s;
438

439
MultiValuedMap<String, String> transformed = MultiMapUtils.transformedMultiValuedMap(
440
    listMap, 
441
    upperCase,    // Key transformer
442
    addPrefix     // Value transformer
443
);
444
```
445

446
### Working with Map Views
447

448
```java { .api }
449
MultiValuedMap<String, Integer> scores = new ArrayListValuedHashMap<>();
450
scores.putAll("Alice", Arrays.asList(85, 92, 78));
451
scores.putAll("Bob", Arrays.asList(88, 76));
452

453
// Get as regular Map<K, Collection<V>>
454
Map<String, Collection<Integer>> asMap = scores.asMap();
455

456
// Modifications through map view affect original
457
asMap.get("Alice").add(95); // Adds to original multimap
458
Collection<Integer> bobScores = asMap.remove("Bob"); // Removes from original
459

460
// Create defensive copies
461
Map<String, List<Integer>> copyMap = new HashMap<>();
462
for (Map.Entry<String, Collection<Integer>> entry : asMap.entrySet()) {
463
    copyMap.put(entry.getKey(), new ArrayList<>(entry.getValue()));
464
}
465
```
466

467
## Performance Considerations  
468

469
### Implementation Choice Guidelines
470

471
```java { .api }
472
// Use ArrayListValuedHashMap when:
473
// - Order of values matters
474
// - Duplicates are needed
475
// - Values are accessed by index
476
ListValuedMap<String, String> orderedWithDuplicates = new ArrayListValuedHashMap<>();
477

478
// Use HashSetValuedHashMap when:  
479
// - Uniqueness of values is required
480
// - Fast contains() operations needed
481
// - Order doesn't matter
482
SetValuedMap<String, String> uniqueValues = new HashSetValuedHashMap<>();
483
```
484

485
### Memory Usage
486

487
```java { .api }
488
// Memory efficient for sparse data (few keys, many values per key)
489
MultiValuedMap<String, String> sparse = new ArrayListValuedHashMap<>();
490
sparse.putAll("key1", Arrays.asList("v1", "v2", "v3", /* ... many values ... */));
491

492
// Less efficient for dense data (many keys, few values per key)  
493
MultiValuedMap<String, String> dense = new ArrayListValuedHashMap<>();
494
for (int i = 0; i < 1000; i++) {
495
    dense.put("key" + i, "value" + i); // Creates many small collections
496
}
497

498
// For dense data, consider regular Map<K, V> instead
499
Map<String, String> regularMap = new HashMap<>();
500
```
501

502
### Bulk Operations Performance
503

504
```java { .api }
505
MultiValuedMap<String, Integer> numbers = new ArrayListValuedHashMap<>();
506

507
// Efficient bulk addition
508
List<Integer> manyNumbers = IntStream.range(1, 1000).boxed().collect(Collectors.toList());
509
numbers.putAll("range", manyNumbers); // Single operation
510

511
// Less efficient individual additions
512
for (int i = 1; i < 1000; i++) {
513
    numbers.put("range2", i); // Multiple operations, more overhead
514
}
515

516
// Efficient collection manipulation
517
Collection<Integer> existing = numbers.get("range");
518
existing.addAll(Arrays.asList(1001, 1002, 1003)); // Direct collection modification
519
```
520

521
## Thread Safety
522

523
MultiValuedMaps are not thread-safe by default. For concurrent access:
524

525
```java { .api }
526
// Option 1: External synchronization
527
MultiValuedMap<String, String> multiMap = new ArrayListValuedHashMap<>();
528
MultiValuedMap<String, String> syncMultiMap = MultiMapUtils.synchronizedMultiValuedMap(multiMap);
529

530
// Option 2: Custom concurrent wrapper
531
public class ConcurrentMultiValuedMap<K, V> {
532
    private final MultiValuedMap<K, V> map = new ArrayListValuedHashMap<>();
533
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
534
    
535
    public boolean put(K key, V value) {
536
        lock.writeLock().lock();
537
        try {
538
            return map.put(key, value);
539
        } finally {
540
            lock.writeLock().unlock();
541
        }
542
    }
543
    
544
    public Collection<V> get(K key) {
545
        lock.readLock().lock();
546
        try {
547
            return new ArrayList<>(map.get(key)); // Defensive copy
548
        } finally {
549
            lock.readLock().unlock();
550
        }
551
    }
552
}
553

554
// Option 3: Use ConcurrentHashMap with CopyOnWriteArrayList
555
Map<String, Collection<String>> concurrent = new ConcurrentHashMap<>();
556
String key = "example";
557
concurrent.computeIfAbsent(key, k -> new CopyOnWriteArrayList<>()).add("value");
558
```
559

560
Multi-valued maps provide powerful abstractions for one-to-many relationships and are particularly useful for grouping, classification, and graph-like data structures. Choose between List and Set semantics based on whether you need ordering/duplicates or uniqueness guarantees.