0
# Bidirectional Maps (BidiMaps)
1

2
Bidirectional maps allow efficient lookup in both directions - from key to value and from value to key. They maintain 1:1 relationships between keys and values, ensuring that both keys and values are unique within the map.
3

4
## Core Interfaces
5

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

8
The primary interface for bidirectional maps.
9

10
```java { .api }
11
import org.apache.commons.collections4.BidiMap;
12
import org.apache.commons.collections4.bidimap.DualHashBidiMap;
13

14
BidiMap<String, Integer> bidiMap = new DualHashBidiMap<>();
15

16
// Standard map operations (key -> value)
17
bidiMap.put("one", 1);
18
bidiMap.put("two", 2);
19
bidiMap.put("three", 3);
20

21
Integer value = bidiMap.get("two");           // Returns 2
22

23
// Reverse lookup operations (value -> key)  
24
String key = bidiMap.getKey(2);               // Returns "two"
25
String removedKey = bidiMap.removeValue(3);   // Removes and returns "three"
26

27
// Get inverse view
28
BidiMap<Integer, String> inverse = bidiMap.inverseBidiMap();
29
String keyFromInverse = inverse.get(1);       // Returns "one"
30

31
// Both views reflect the same underlying data
32
bidiMap.put("four", 4);
33
Integer newValue = inverse.get("four");       // Returns 4
34
```
35

36
### OrderedBidiMap<K, V> Interface
37

38
A bidirectional map that maintains insertion order.
39

40
```java { .api }
41
import org.apache.commons.collections4.OrderedBidiMap;
42
import org.apache.commons.collections4.bidimap.DualLinkedHashBidiMap;
43
import org.apache.commons.collections4.OrderedMapIterator;
44

45
OrderedBidiMap<String, Integer> orderedBidi = new DualLinkedHashBidiMap<>();
46
orderedBidi.put("first", 1);
47
orderedBidi.put("second", 2);
48
orderedBidi.put("third", 3);
49

50
// Navigate in insertion order
51
String firstKey = orderedBidi.firstKey();     // Returns "first"
52
String lastKey = orderedBidi.lastKey();       // Returns "third"
53
String nextKey = orderedBidi.nextKey("first"); // Returns "second"
54
String prevKey = orderedBidi.previousKey("third"); // Returns "second"
55

56
// Ordered iteration
57
OrderedMapIterator<String, Integer> iterator = orderedBidi.mapIterator();
58
while (iterator.hasNext()) {
59
    String key = iterator.next();
60
    Integer value = iterator.getValue();
61
    System.out.println(key + " -> " + value);
62
}
63
```
64

65
### SortedBidiMap<K, V> Interface  
66

67
A bidirectional map that maintains elements in sorted order.
68

69
```java { .api }
70
import org.apache.commons.collections4.SortedBidiMap;
71
import org.apache.commons.collections4.bidimap.DualTreeBidiMap;
72
import java.util.Comparator;
73

74
// Natural ordering
75
SortedBidiMap<String, Integer> sortedBidi = new DualTreeBidiMap<>();
76
sortedBidi.put("zebra", 26);
77
sortedBidi.put("alpha", 1);
78
sortedBidi.put("beta", 2);
79

80
// Elements are maintained in sorted order
81
String firstKey = sortedBidi.firstKey();      // Returns "alpha"  
82
String lastKey = sortedBidi.lastKey();        // Returns "zebra"
83

84
// Custom comparators for keys and values
85
Comparator<String> keyComp = Comparator.reverseOrder();
86
Comparator<Integer> valueComp = Comparator.naturalOrder();
87
SortedBidiMap<String, Integer> customSorted = new DualTreeBidiMap<>(keyComp, valueComp);
88
```
89

90
## Concrete Implementations
91

92
### DualHashBidiMap<K, V>
93

94
Hash-based implementation using two HashMap instances for O(1) performance.
95

96
```java { .api }
97
import org.apache.commons.collections4.bidimap.DualHashBidiMap;
98
import java.util.Map;
99
import java.util.HashMap;
100

101
// Create empty bidirectional map
102
DualHashBidiMap<String, String> countryCapital = new DualHashBidiMap<>();
103

104
// Populate with data
105
countryCapital.put("USA", "Washington");
106
countryCapital.put("France", "Paris");
107
countryCapital.put("Japan", "Tokyo");
108
countryCapital.put("Germany", "Berlin");
109

110
// Efficient bidirectional lookups
111
String capital = countryCapital.get("France");        // "Paris"
112
String country = countryCapital.getKey("Tokyo");      // "Japan"
113

114
// Create from existing map
115
Map<String, String> existingMap = new HashMap<>();
116
existingMap.put("Italy", "Rome");
117
existingMap.put("Spain", "Madrid");
118
DualHashBidiMap<String, String> fromMap = new DualHashBidiMap<>(existingMap);
119

120
// Duplicate value detection
121
try {
122
    countryCapital.put("UK", "Paris"); // Throws IllegalArgumentException
123
} catch (IllegalArgumentException e) {
124
    System.out.println("Paris is already mapped to France");
125
}
126
```
127

128
### DualLinkedHashBidiMap<K, V>
129

130
LinkedHashMap-based implementation that maintains insertion order.
131

132
```java { .api }
133
import org.apache.commons.collections4.bidimap.DualLinkedHashBidiMap;
134

135
DualLinkedHashBidiMap<Integer, String> priorities = new DualLinkedHashBidiMap<>();
136

137
// Add in specific order
138
priorities.put(1, "High");
139
priorities.put(2, "Medium");  
140
priorities.put(3, "Low");
141

142
// Maintains insertion order during iteration
143
for (Map.Entry<Integer, String> entry : priorities.entrySet()) {
144
    System.out.println("Priority " + entry.getKey() + ": " + entry.getValue());
145
}
146
// Output: Priority 1: High, Priority 2: Medium, Priority 3: Low
147

148
// Inverse also maintains corresponding order
149
BidiMap<String, Integer> inversePriorities = priorities.inverseBidiMap();
150
for (String level : inversePriorities.keySet()) {
151
    System.out.println(level + " has priority " + inversePriorities.get(level));
152
}
153
// Output: High has priority 1, Medium has priority 2, Low has priority 3
154
```
155

156
### DualTreeBidiMap<K, V>
157

158
TreeMap-based implementation that maintains sorted order for both keys and values.
159

160
```java { .api }
161
import org.apache.commons.collections4.bidimap.DualTreeBidiMap;
162
import java.util.Comparator;
163

164
// Natural ordering for both keys and values
165
DualTreeBidiMap<String, Integer> grades = new DualTreeBidiMap<>();
166
grades.put("Alice", 95);
167
grades.put("Bob", 87);
168
grades.put("Charlie", 92);
169

170
// Keys sorted alphabetically
171
System.out.println("First student: " + grades.firstKey());    // "Alice"
172
System.out.println("Last student: " + grades.lastKey());      // "Charlie"
173

174
// Values also sorted in inverse map
175
SortedBidiMap<Integer, String> byGrades = grades.inverseBidiMap();
176
System.out.println("Lowest grade: " + byGrades.firstKey());   // 87
177
System.out.println("Highest grade: " + byGrades.lastKey());   // 95
178

179
// Custom comparators
180
Comparator<String> nameComp = (a, b) -> a.length() - b.length(); // By name length
181
Comparator<Integer> gradeComp = Comparator.reverseOrder();        // Descending grades
182
DualTreeBidiMap<String, Integer> customOrder = new DualTreeBidiMap<>(nameComp, gradeComp);
183
```
184

185
### TreeBidiMap<K, V>
186

187
Red-black tree implementation for Comparable objects with excellent performance.
188

189
```java { .api }
190
import org.apache.commons.collections4.bidimap.TreeBidiMap;
191
import java.time.LocalDate;
192
import java.util.Map;
193
import java.util.HashMap;
194

195
// For Comparable types
196
TreeBidiMap<LocalDate, String> events = new TreeBidiMap<>();
197
events.put(LocalDate.of(2024, 1, 1), "New Year");
198
events.put(LocalDate.of(2024, 7, 4), "Independence Day");
199
events.put(LocalDate.of(2024, 12, 25), "Christmas");
200

201
// Sorted by date
202
LocalDate firstDate = events.firstKey();      // 2024-01-01
203
LocalDate lastDate = events.lastKey();        // 2024-12-25
204

205
// Create from existing map
206
Map<String, Integer> scoreMap = new HashMap<>();
207
scoreMap.put("Alpha", 100);
208
scoreMap.put("Beta", 85);
209
scoreMap.put("Gamma", 92);
210
TreeBidiMap<String, Integer> scores = new TreeBidiMap<>(scoreMap);
211
```
212

213
## Bidirectional Map Operations
214

215
### Unique Key-Value Constraints
216

217
BidiMaps enforce 1:1 relationships between keys and values.
218

219
```java { .api }
220
BidiMap<String, String> usernames = new DualHashBidiMap<>();
221

222
// Initial mapping
223
usernames.put("john.doe", "John Doe");
224
usernames.put("jane.smith", "Jane Smith");
225

226
// Attempting to add duplicate value removes existing mapping
227
String oldKey = usernames.put("j.doe", "John Doe"); // oldKey is null
228
// Now "John Doe" maps to "j.doe", "john.doe" mapping is removed
229

230
System.out.println(usernames.getKey("John Doe"));  // Returns "j.doe"
231
System.out.println(usernames.get("john.doe"));     // Returns null
232

233
// Using putAll with conflicting values
234
Map<String, String> newMappings = Map.of(
235
    "admin", "Administrator",
236
    "jane.doe", "Jane Smith"  // Conflicts with existing value
237
);
238
usernames.putAll(newMappings);
239
// "Jane Smith" now maps to "jane.doe", "jane.smith" is removed
240
```
241

242
### Inverse Map Views
243

244
Inverse maps provide a flipped view of the same underlying data.
245

246
```java { .api }
247
BidiMap<String, Integer> original = new DualHashBidiMap<>();
248
original.put("A", 1);
249
original.put("B", 2);
250

251
BidiMap<Integer, String> inverse = original.inverseBidiMap();
252

253
// Both views share the same data
254
System.out.println(original.size());           // 2
255
System.out.println(inverse.size());            // 2
256

257
// Modifications through inverse affect original
258
inverse.put(3, "C");
259
System.out.println(original.get("C"));        // Returns 3
260

261
// Removing through inverse
262
String removed = inverse.remove(2);            // Returns "B"
263
System.out.println(original.containsKey("B")); // false
264

265
// Getting inverse of inverse returns original
266
BidiMap<String, Integer> doubleInverse = inverse.inverseBidiMap();
267
System.out.println(doubleInverse == original); // true
268
```
269

270
### MapIterator Usage
271

272
Efficient iteration over bidirectional maps.
273

274
```java { .api }
275
import org.apache.commons.collections4.MapIterator;
276

277
BidiMap<String, Double> stockPrices = new DualHashBidiMap<>();
278
stockPrices.put("AAPL", 150.25);
279
stockPrices.put("GOOGL", 2750.80);
280
stockPrices.put("MSFT", 305.15);
281

282
// Iterate with MapIterator
283
MapIterator<String, Double> iterator = stockPrices.mapIterator();
284
while (iterator.hasNext()) {
285
    String symbol = iterator.next();
286
    Double price = iterator.getValue();
287
    
288
    // Update prices with 5% increase  
289
    iterator.setValue(price * 1.05);
290
    
291
    System.out.println(symbol + ": $" + iterator.getValue());
292
}
293

294
// Iterate inverse map
295
MapIterator<Double, String> priceIterator = stockPrices.inverseBidiMap().mapIterator();
296
while (priceIterator.hasNext()) {
297
    Double price = priceIterator.next();
298
    String symbol = priceIterator.getValue();
299
    System.out.println("$" + price + " -> " + symbol);
300
}
301
```
302

303
## Advanced Usage Patterns
304

305
### Caching and Lookup Tables  
306

307
```java { .api }
308
public class UserManager {
309
    private final BidiMap<String, Long> usernameToId = new DualHashBidiMap<>();
310
    
311
    public void registerUser(String username, Long userId) {
312
        // BidiMap ensures both username and userId are unique
313
        usernameToId.put(username, userId);
314
    }
315
    
316
    public Long getUserId(String username) {
317
        return usernameToId.get(username);
318
    }
319
    
320
    public String getUsername(Long userId) {
321
        return usernameToId.getKey(userId);
322
    }
323
    
324
    public boolean isUsernameTaken(String username) {
325
        return usernameToId.containsKey(username);
326
    }
327
    
328
    public boolean isUserIdTaken(Long userId) {
329
        return usernameToId.containsValue(userId);
330
    }
331
    
332
    public void deleteUser(String username) {
333
        usernameToId.remove(username);
334
    }
335
    
336
    public void deleteUserById(Long userId) {
337
        usernameToId.removeValue(userId);
338
    }
339
}
340
```
341

342
### State Machine Mappings
343

344
```java { .api }
345
public enum OrderState { PENDING, CONFIRMED, SHIPPED, DELIVERED, CANCELLED }
346
public enum StatusCode { 100, 200, 300, 400, 500 }
347

348
public class OrderStateMachine {
349
    private final BidiMap<OrderState, StatusCode> stateCodes = new DualHashBidiMap<>();
350
    
351
    public OrderStateMachine() {
352
        stateCodes.put(OrderState.PENDING, StatusCode.100);
353
        stateCodes.put(OrderState.CONFIRMED, StatusCode.200);
354
        stateCodes.put(OrderState.SHIPPED, StatusCode.300);
355
        stateCodes.put(OrderState.DELIVERED, StatusCode.400);
356
        stateCodes.put(OrderState.CANCELLED, StatusCode.500);
357
    }
358
    
359
    public StatusCode getStatusCode(OrderState state) {
360
        return stateCodes.get(state);
361
    }
362
    
363
    public OrderState getState(StatusCode code) {
364
        return stateCodes.getKey(code);
365
    }
366
    
367
    public Set<OrderState> getAllStates() {
368
        return stateCodes.keySet();
369
    }
370
    
371
    public Set<StatusCode> getAllCodes() {
372
        return stateCodes.values();
373
    }
374
}
375
```
376

377
### Configuration Management
378

379
```java { .api }
380
public class ConfigurationManager {
381
    private final OrderedBidiMap<String, String> properties = new DualLinkedHashBidiMap<>();
382
    
383
    public void loadConfiguration(Properties props) {
384
        props.forEach((key, value) -> properties.put(key.toString(), value.toString()));
385
    }
386
    
387
    public String getProperty(String key) {
388
        return properties.get(key);
389
    }
390
    
391
    public String getPropertyKey(String value) {
392
        return properties.getKey(value);
393
    }
394
    
395
    public void setProperty(String key, String value) {
396
        properties.put(key, value);
397
    }
398
    
399
    // Maintain insertion order for configuration display
400
    public Map<String, String> getAllProperties() {
401
        return new LinkedHashMap<>(properties);
402
    }
403
    
404
    // Find all keys with a specific value pattern
405
    public Set<String> getKeysForValue(String valuePattern) {
406
        return properties.entrySet().stream()
407
            .filter(entry -> entry.getValue().matches(valuePattern))
408
            .map(Map.Entry::getKey)
409
            .collect(Collectors.toSet());
410
    }
411
}
412
```
413

414
## Performance Characteristics
415

416
### Implementation Comparison
417

418
| Implementation | Key Lookup | Value Lookup | Ordering | Memory Overhead |
419
|---------------|------------|--------------|----------|-----------------|
420
| DualHashBidiMap | O(1) | O(1) | None | Low |
421
| DualLinkedHashBidiMap | O(1) | O(1) | Insertion | Medium |
422
| DualTreeBidiMap | O(log n) | O(log n) | Sorted | Medium |
423
| TreeBidiMap | O(log n) | O(log n) | Natural | Low |
424
425
### Memory Considerations
426

427
```java { .api }
428
// DualHashBidiMap uses two HashMap instances
429
BidiMap<String, Integer> hash = new DualHashBidiMap<>();
430
// Memory: ~2x HashMap overhead + entry objects
431

432
// TreeBidiMap uses single tree structure  
433
BidiMap<String, Integer> tree = new TreeBidiMap<>();
434
// Memory: ~1.5x TreeMap overhead + navigation pointers
435

436
// For memory-critical applications with large datasets
437
BidiMap<Integer, Integer> compact = new TreeBidiMap<>(); // More memory efficient
438
BidiMap<String, String> spacious = new DualHashBidiMap<>(); // Faster but more memory
439
```
440

441
### Thread Safety
442

443
BidiMaps are not thread-safe by default. For concurrent access:
444

445
```java { .api }
446
// Option 1: External synchronization
447
BidiMap<String, Integer> bidiMap = new DualHashBidiMap<>();
448
Map<String, Integer> syncMap = Collections.synchronizedMap(bidiMap);
449

450
// Option 2: Concurrent wrapper (custom implementation needed)
451
public class ConcurrentBidiMap<K, V> {
452
    private final BidiMap<K, V> map;
453
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
454
    
455
    public ConcurrentBidiMap(BidiMap<K, V> map) {
456
        this.map = map;
457
    }
458
    
459
    public V get(K key) {
460
        lock.readLock().lock();
461
        try {
462
            return map.get(key);
463
        } finally {
464
            lock.readLock().unlock();
465
        }
466
    }
467
    
468
    public K getKey(V value) {
469
        lock.readLock().lock();
470
        try {
471
            return map.getKey(value);
472
        } finally {
473
            lock.readLock().unlock();
474
        }
475
    }
476
    
477
    public V put(K key, V value) {
478
        lock.writeLock().lock();
479
        try {
480
            return map.put(key, value);
481
        } finally {
482
            lock.writeLock().unlock();
483
        }
484
    }
485
}
486
```
487

488
## Best Practices
489

490
### Choosing the Right Implementation
491

492
```java { .api }
493
// Fast lookups, no ordering requirements
494
BidiMap<String, Integer> fast = new DualHashBidiMap<>();
495

496
// Need to maintain insertion order
497
BidiMap<String, Integer> ordered = new DualLinkedHashBidiMap<>();
498

499
// Need sorted iteration, have Comparable keys/values
500
BidiMap<String, Integer> sorted = new DualTreeBidiMap<>();
501

502
// Memory efficient for Comparable types
503
BidiMap<String, Integer> efficient = new TreeBidiMap<>();
504
```
505

506
### Error Handling
507

508
```java { .api }
509
BidiMap<String, String> errorProne = new DualHashBidiMap<>();
510

511
try {
512
    errorProne.put("key1", "value1");
513
    errorProne.put("key2", "value1"); // May remove key1 mapping
514
} catch (Exception e) {
515
    // Handle potential issues
516
}
517

518
// Safer approach - check before inserting
519
public boolean safePut(BidiMap<String, String> map, String key, String value) {
520
    if (map.containsValue(value)) {
521
        String existingKey = map.getKey(value);
522
        if (!key.equals(existingKey)) {
523
            System.out.println("Warning: Value '" + value + "' already mapped to '" + existingKey + "'");
524
            return false;
525
        }
526
    }
527
    map.put(key, value);
528
    return true;
529
}
530
```
531

532
Bidirectional maps provide efficient two-way lookup capabilities while maintaining data consistency through 1:1 key-value relationships. Choose the appropriate implementation based on your performance requirements and ordering needs.