0
# Immutable Collections
1

2
Thread-safe, high-performance immutable data structures that can be safely shared between threads and cached without defensive copying. All immutable collections are inherently thread-safe and provide strong guarantees about their contents never changing.
3

4
## Package: com.google.common.collect
5

6
### ImmutableList
7

8
Immutable ordered collection that maintains insertion order and allows duplicate elements.
9

10
```java { .api }
11
import com.google.common.collect.ImmutableList;
12

13
// Creating immutable lists
14
ImmutableList<String> empty = ImmutableList.of();
15
ImmutableList<String> single = ImmutableList.of("single");
16
ImmutableList<String> multiple = ImmutableList.of("a", "b", "c", "d");
17

18
// From existing collections
19
List<String> mutableList = Arrays.asList("x", "y", "z");
20
ImmutableList<String> fromCollection = ImmutableList.copyOf(mutableList);
21
ImmutableList<String> fromIterator = ImmutableList.copyOf(iterator);
22

23
// Using builder for dynamic construction
24
ImmutableList<String> built = ImmutableList.<String>builder()
25
    .add("first")
26
    .add("second", "third")
27
    .addAll(Arrays.asList("fourth", "fifth"))
28
    .build();
29

30
// List operations (returns new immutable instances)
31
ImmutableList<String> reversed = list.reverse();
32
ImmutableList<String> subList = list.subList(1, 3);
33

34
// Element access
35
String first = list.get(0);
36
int index = list.indexOf("b"); // -1 if not found
37
int lastIndex = list.lastIndexOf("b");
38

39
// Conversion
40
List<String> mutableCopy = list.asList(); // Returns the same instance (already a List)
41
String[] array = list.toArray(new String[0]);
42

43
// Iteration maintains order
44
for (String item : list) {
45
    System.out.println(item);
46
}
47
```
48

49
**Key Features:**
50
- **Order**: Maintains insertion order
51
- **Duplicates**: Allows duplicate elements
52
- **Performance**: O(1) random access, optimized for reads
53
- **Memory**: Space-efficient, shares structure when possible
54

55
### ImmutableSet
56

57
Immutable unordered collection with unique elements, optimized for containment checks.
58

59
```java { .api }
60
import com.google.common.collect.ImmutableSet;
61

62
// Creating immutable sets
63
ImmutableSet<String> empty = ImmutableSet.of();
64
ImmutableSet<String> single = ImmutableSet.of("unique");
65
ImmutableSet<String> multiple = ImmutableSet.of("a", "b", "c");
66

67
// From collections (automatically removes duplicates)
68
Set<String> mutableSet = new HashSet<>(Arrays.asList("x", "y", "z", "x"));
69
ImmutableSet<String> fromCollection = ImmutableSet.copyOf(mutableSet); // {x, y, z}
70

71
// Using builder
72
ImmutableSet<String> built = ImmutableSet.<String>builder()
73
    .add("alpha")
74
    .add("beta")
75
    .addAll(Arrays.asList("gamma", "delta"))
76
    .add("alpha") // Duplicates ignored
77
    .build();
78

79
// Set operations (return new immutable instances)
80
ImmutableSet<String> union = set1.union(set2);
81
ImmutableSet<String> intersection = set1.intersection(set2);
82

83
// Containment (optimized performance)
84
boolean contains = set.contains("item"); // O(1) average case
85
boolean containsAll = set.containsAll(Arrays.asList("a", "b"));
86

87
// Conversion
88
Set<String> mutableCopy = new HashSet<>(set);
89
List<String> asList = set.asList(); // Arbitrary order
90
```
91

92
### ImmutableSortedSet
93

94
Immutable set with elements maintained in sorted order according to their natural ordering or a provided comparator.
95

96
```java { .api }
97
import com.google.common.collect.ImmutableSortedSet;
98
import java.util.Comparator;
99

100
// Natural ordering
101
ImmutableSortedSet<String> natural = ImmutableSortedSet.of("c", "a", "b"); // Stored as [a, b, c]
102
ImmutableSortedSet<Integer> numbers = ImmutableSortedSet.of(5, 1, 3, 2); // [1, 2, 3, 5]
103

104
// Custom comparator
105
ImmutableSortedSet<String> byLength = ImmutableSortedSet.orderedBy(
106
    Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder())
107
).add("apple").add("pie").add("a").build(); // [a, pie, apple]
108

109
// Builders for different orderings
110
ImmutableSortedSet<String> naturalOrder = ImmutableSortedSet.<String>naturalOrder()
111
    .add("zebra")
112
    .add("apple") 
113
    .add("banana")
114
    .build(); // [apple, banana, zebra]
115

116
ImmutableSortedSet<String> reverseOrder = ImmutableSortedSet.<String>reverseOrder()
117
    .addAll(Arrays.asList("a", "b", "c"))
118
    .build(); // [c, b, a]
119

120
// Range operations (leveraging sorted order)
121
ImmutableSortedSet<Integer> range = ImmutableSortedSet.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
122
ImmutableSortedSet<Integer> headSet = range.headSet(5); // [1, 2, 3, 4]
123
ImmutableSortedSet<Integer> tailSet = range.tailSet(7); // [7, 8, 9, 10]  
124
ImmutableSortedSet<Integer> subSet = range.subSet(3, 8); // [3, 4, 5, 6, 7]
125

126
// First/Last access (O(1))
127
Integer first = range.first(); // 1
128
Integer last = range.last(); // 10
129

130
// Floor/Ceiling operations
131
Integer floor = range.floor(4); // 4 (largest element ≤ 4)
132
Integer ceiling = range.ceiling(4); // 4 (smallest element ≥ 4)
133
Integer lower = range.lower(4); // 3 (largest element < 4)  
134
Integer higher = range.higher(4); // 5 (smallest element > 4)
135
```
136

137
### ImmutableMap
138

139
Immutable key-value mapping with unique keys, optimized for lookups.
140

141
```java { .api }
142
import com.google.common.collect.ImmutableMap;
143

144
// Creating immutable maps
145
ImmutableMap<String, Integer> empty = ImmutableMap.of();
146
ImmutableMap<String, Integer> single = ImmutableMap.of("key", 42);
147
ImmutableMap<String, Integer> multiple = ImmutableMap.of(
148
    "one", 1,
149
    "two", 2,
150
    "three", 3
151
);
152

153
// From existing maps
154
Map<String, Integer> mutableMap = new HashMap<>();
155
mutableMap.put("x", 24);
156
mutableMap.put("y", 25);
157
ImmutableMap<String, Integer> fromMap = ImmutableMap.copyOf(mutableMap);
158

159
// Using builder for larger maps
160
ImmutableMap<String, String> built = ImmutableMap.<String, String>builder()
161
    .put("CA", "California")
162
    .put("NY", "New York")
163
    .putAll(existingStateMap)
164
    .build();
165

166
// Builder with expected size for performance
167
ImmutableMap<Integer, String> withCapacity = ImmutableMap.<Integer, String>builderWithExpectedSize(100)
168
    .put(1, "first")
169
    .put(2, "second")
170
    .build();
171

172
// Map operations
173
Integer value = map.get("key"); // null if not present
174
Integer valueWithDefault = map.getOrDefault("missing", 0);
175
boolean hasKey = map.containsKey("key");
176
boolean hasValue = map.containsValue(42);
177

178
// Views (all immutable)
179
ImmutableSet<String> keys = map.keySet();
180
ImmutableCollection<Integer> values = map.values();  
181
ImmutableSet<Map.Entry<String, Integer>> entries = map.entrySet();
182

183
// Iteration maintains insertion order (in most implementations)
184
for (Map.Entry<String, Integer> entry : map.entrySet()) {
185
    String key = entry.getKey();
186
    Integer value = entry.getValue();
187
}
188
```
189

190
### ImmutableSortedMap
191

192
Immutable map with keys maintained in sorted order, enabling efficient range operations.
193

194
```java { .api }
195
import com.google.common.collect.ImmutableSortedMap;
196

197
// Natural key ordering
198
ImmutableSortedMap<String, Integer> natural = ImmutableSortedMap.of(
199
    "zebra", 26,
200
    "apple", 1,
201
    "banana", 2
202
); // Keys stored as: [apple, banana, zebra]
203

204
// Custom comparator for keys  
205
ImmutableSortedMap<String, String> byLength = ImmutableSortedMap.<String, String>orderedBy(
206
    Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder())
207
)
208
.put("a", "short")
209
.put("medium", "middle")  
210
.put("z", "also short")
211
.build(); // Keys: [a, z, medium]
212

213
// Builders with different orderings
214
ImmutableSortedMap<Integer, String> ascending = ImmutableSortedMap.<Integer, String>naturalOrder()
215
    .put(3, "three")
216
    .put(1, "one")
217
    .put(2, "two")
218
    .build(); // Keys: [1, 2, 3]
219

220
ImmutableSortedMap<String, Integer> descending = ImmutableSortedMap.<String, Integer>reverseOrder()
221
    .put("a", 1)
222
    .put("c", 3)
223
    .put("b", 2)  
224
    .build(); // Keys: [c, b, a]
225

226
// Range operations on keys
227
ImmutableSortedMap<Integer, String> numbers = ImmutableSortedMap.of(
228
    1, "one", 3, "three", 5, "five", 7, "seven", 9, "nine"
229
);
230

231
ImmutableSortedMap<Integer, String> headMap = numbers.headMap(5); // {1=one, 3=three}
232
ImmutableSortedMap<Integer, String> tailMap = numbers.tailMap(5); // {5=five, 7=seven, 9=nine}
233
ImmutableSortedMap<Integer, String> subMap = numbers.subMap(3, 8); // {3=three, 5=five, 7=seven}
234

235
// Key navigation
236
Integer firstKey = numbers.firstKey(); // 1
237
Integer lastKey = numbers.lastKey(); // 9
238
String firstValue = numbers.values().iterator().next(); // "one"
239
```
240

241
### ImmutableMultiset
242

243
Immutable collection that allows duplicate elements and tracks count of each element.
244

245
```java { .api }
246
import com.google.common.collect.ImmutableMultiset;
247

248
// Creating immutable multisets
249
ImmutableMultiset<String> empty = ImmutableMultiset.of();
250
ImmutableMultiset<String> single = ImmutableMultiset.of("apple");
251
ImmutableMultiset<String> multiple = ImmutableMultiset.of("apple", "banana", "apple", "cherry");
252

253
// From collections (preserves counts)
254
List<String> fruits = Arrays.asList("apple", "apple", "banana", "apple");
255
ImmutableMultiset<String> fromCollection = ImmutableMultiset.copyOf(fruits);
256

257
// Using builder with counts
258
ImmutableMultiset<String> built = ImmutableMultiset.<String>builder()
259
    .add("apple")
260
    .addCopies("banana", 3)
261
    .add("cherry", "cherry")
262
    .setCount("orange", 2)
263
    .build();
264

265
// Count operations
266
int appleCount = multiset.count("apple"); // Number of occurrences
267
int totalSize = multiset.size(); // Total elements including duplicates
268
int distinctSize = multiset.elementSet().size(); // Number of unique elements
269

270
// Views
271
ImmutableSet<String> elements = multiset.elementSet(); // Unique elements
272
ImmutableSet<Multiset.Entry<String>> entries = multiset.entrySet(); // Element-count pairs
273

274
// Iteration over unique elements with counts
275
for (Multiset.Entry<String> entry : multiset.entrySet()) {
276
    String element = entry.getElement();
277
    int count = entry.getCount();
278
    System.out.println(element + " appears " + count + " times");
279
}
280

281
// Converting to other immutable collections
282
ImmutableList<String> allElements = multiset.asList(); // All elements including duplicates
283
ImmutableSortedMultiset<String> sorted = ImmutableSortedMultiset.copyOf(multiset);
284
```
285

286
### ImmutableSortedMultiset
287

288
Immutable multiset with elements maintained in sorted order.
289

290
```java { .api }
291
import com.google.common.collect.ImmutableSortedMultiset;
292

293
// Natural ordering  
294
ImmutableSortedMultiset<String> natural = ImmutableSortedMultiset.of(
295
    "zebra", "apple", "banana", "apple"
296
); // Elements: [apple (×2), banana, zebra]
297

298
// Custom comparator
299
ImmutableSortedMultiset<String> byLength = ImmutableSortedMultiset.<String>orderedBy(
300
    Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder())
301
)
302
.addCopies("a", 3)
303
.addCopies("apple", 2)
304
.add("pie")
305
.build(); // Elements by length: [a (×3), pie, apple (×2)]
306

307
// Range operations
308
ImmutableSortedMultiset<Integer> numbers = ImmutableSortedMultiset.of(1, 1, 2, 3, 3, 3, 4, 5);
309
ImmutableSortedMultiset<Integer> headMultiset = numbers.headMultiset(3, BoundType.CLOSED); // [1 (×2), 2, 3 (×3)]
310
ImmutableSortedMultiset<Integer> tailMultiset = numbers.tailMultiset(3, BoundType.OPEN); // [4, 5]
311

312
// First/Last operations
313
Multiset.Entry<Integer> firstEntry = numbers.firstEntry(); // 1 (count: 2)
314
Multiset.Entry<Integer> lastEntry = numbers.lastEntry(); // 5 (count: 1)
315
```
316

317
### ImmutableMultimap
318

319
Immutable mapping from keys to multiple values, combining the benefits of multimaps with immutability.
320

321
```java { .api }
322
import com.google.common.collect.ImmutableMultimap;
323
import com.google.common.collect.ImmutableListMultimap;
324
import com.google.common.collect.ImmutableSetMultimap;
325

326
// Creating immutable multimaps
327
ImmutableMultimap<String, String> empty = ImmutableMultimap.of();
328
ImmutableMultimap<String, String> single = ImmutableMultimap.of("key", "value");
329
ImmutableMultimap<String, String> multiple = ImmutableMultimap.of(
330
    "fruits", "apple",
331
    "fruits", "banana", 
332
    "colors", "red"
333
);
334

335
// From existing multimaps
336
ListMultimap<String, String> mutable = ArrayListMultimap.create();
337
mutable.put("a", "1");
338
mutable.put("a", "2");
339
ImmutableMultimap<String, String> fromMultimap = ImmutableMultimap.copyOf(mutable);
340

341
// Using builders
342
ImmutableListMultimap<String, Integer> listMultimap = ImmutableListMultimap.<String, Integer>builder()
343
    .put("even", 2)
344
    .put("even", 4)
345
    .put("even", 6)
346
    .put("odd", 1)
347
    .putAll("odd", Arrays.asList(3, 5))
348
    .build();
349

350
ImmutableSetMultimap<String, String> setMultimap = ImmutableSetMultimap.<String, String>builder()
351
    .put("vowels", "a")
352
    .put("vowels", "e")
353
    .put("vowels", "a") // Duplicate ignored in SetMultimap
354
    .build();
355

356
// Access operations
357
ImmutableCollection<String> fruits = multimap.get("fruits"); // All values for key
358
boolean hasKey = multimap.containsKey("fruits");
359
boolean hasEntry = multimap.containsEntry("fruits", "apple");
360
boolean hasValue = multimap.containsValue("apple");
361

362
// Views (all immutable)
363
ImmutableSet<String> keys = multimap.keySet();
364
ImmutableCollection<String> values = multimap.values();
365
ImmutableCollection<Map.Entry<String, String>> entries = multimap.entries();
366
ImmutableMap<String, Collection<String>> asMap = multimap.asMap();
367

368
// Inverse operation (for certain multimap types)
369
ImmutableMultimap<String, String> inverse = multimap.inverse();
370
```
371

372
### ImmutableTable
373

374
Immutable two-dimensional table structure for row-column-value mappings.
375

376
```java { .api }
377
import com.google.common.collect.ImmutableTable;
378

379
// Creating immutable tables
380
ImmutableTable<String, String, Integer> empty = ImmutableTable.of();
381
ImmutableTable<String, String, Integer> single = ImmutableTable.of("row", "col", 42);
382

383
// Using builder for multiple entries
384
ImmutableTable<String, String, Integer> grades = ImmutableTable.<String, String, Integer>builder()
385
    .put("Alice", "Math", 95)
386
    .put("Alice", "Science", 87)
387
    .put("Bob", "Math", 82)
388
    .put("Bob", "Science", 91)
389
    .build();
390

391
// From existing tables
392
Table<String, String, Integer> mutable = HashBasedTable.create();
393
mutable.put("x", "y", 1);
394
ImmutableTable<String, String, Integer> fromTable = ImmutableTable.copyOf(mutable);
395

396
// Access operations
397
Integer grade = grades.get("Alice", "Math"); // 95, null if not present
398
boolean hasEntry = grades.contains("Alice", "Math");
399
boolean hasRow = grades.containsRow("Alice");
400
boolean hasColumn = grades.containsColumn("Math");
401

402
// Row and column views (all immutable)
403
ImmutableMap<String, Integer> aliceGrades = grades.row("Alice"); // {Math=95, Science=87}
404
ImmutableMap<String, Integer> mathGrades = grades.column("Math"); // {Alice=95, Bob=82}
405

406
// All views
407
ImmutableSet<String> students = grades.rowKeySet(); // [Alice, Bob] 
408
ImmutableSet<String> subjects = grades.columnKeySet(); // [Math, Science]
409
ImmutableCollection<Integer> allGrades = grades.values(); // [95, 87, 82, 91]
410
ImmutableSet<Table.Cell<String, String, Integer>> cells = grades.cellSet();
411

412
// Size
413
int totalEntries = grades.size(); // 4
414
boolean isEmpty = grades.isEmpty();
415
```
416

417
## Performance Characteristics
418

419
### Space Efficiency
420
- **Structural Sharing**: Immutable collections share structure when possible (e.g., sublists, tail operations)
421
- **Optimized Storage**: Specialized implementations for different sizes (e.g., singleton sets)
422
- **No Defensive Copying**: Safe to pass around without copying
423

424
### Time Complexity
425
- **ImmutableList**: O(1) get, O(n) contains, O(log n) insertion via builder
426
- **ImmutableSet**: O(1) contains, O(1) iteration per element
427
- **ImmutableMap**: O(1) get/containsKey, O(1) iteration per entry
428
- **Sorted Collections**: O(log n) for navigation operations, O(n) for range operations
429

430
### Thread Safety
431
All immutable collections are inherently thread-safe:
432
- No synchronization needed for read operations  
433
- Safe to share between threads without defensive copying
434
- Can be used as keys in maps or elements in sets safely
435

436
## Best Practices
437

438
### When to Use Immutable Collections
439

440
```java { .api }
441
// Good: Public API return values
442
public ImmutableList<String> getNames() {
443
    return names; // Safe to return directly, no defensive copying needed
444
}
445

446
// Good: Configuration and constants  
447
public static final ImmutableMap<String, String> CONFIG = ImmutableMap.of(
448
    "host", "localhost",
449
    "port", "8080"
450
);
451

452
// Good: Builder pattern for optional parameters
453
public class Configuration {
454
    private final ImmutableSet<String> enabledFeatures;
455
    
456
    private Configuration(Builder builder) {
457
        this.enabledFeatures = builder.featuresBuilder.build();
458
    }
459
    
460
    public static class Builder {
461
        private final ImmutableSet.Builder<String> featuresBuilder = ImmutableSet.builder();
462
        
463
        public Builder addFeature(String feature) {
464
            featuresBuilder.add(feature);
465
            return this;
466
        }
467
        
468
        public Configuration build() {
469
            return new Configuration(this);
470
        }
471
    }
472
}
473
```
474

475
### Builder Patterns
476

477
```java { .api }
478
// Efficient building of large collections
479
ImmutableList.Builder<String> listBuilder = ImmutableList.builderWithExpectedSize(1000);
480
for (String item : largeDataSet) {
481
    if (shouldInclude(item)) {
482
        listBuilder.add(process(item));
483
    }
484
}
485
ImmutableList<String> result = listBuilder.build();
486

487
// Combining builders with other operations
488
ImmutableSet.Builder<String> setBuilder = ImmutableSet.builder();
489
setBuilder.addAll(existingCollection);
490
setBuilder.add("additional", "items");
491
ImmutableSet<String> combined = setBuilder.build();
492
```
493

494
### Migration from Mutable Collections
495

496
```java { .api }
497
// Before: Mutable with defensive copying
498
public List<String> getItems() {
499
    return new ArrayList<>(this.items); // Expensive defensive copy
500
}
501

502
public void setItems(List<String> items) {
503
    this.items = new ArrayList<>(items); // Another defensive copy
504
}
505

506
// After: Immutable without copying
507
public ImmutableList<String> getItems() {
508
    return this.items; // No copying needed, safe to return directly
509
}
510

511
public void setItems(Collection<String> items) {
512
    this.items = ImmutableList.copyOf(items); // Copy once, then immutable
513
}
514
```
515

516
Immutable collections provide a powerful foundation for building thread-safe, efficient applications while eliminating common sources of bugs related to unintended mutation and concurrent access.