Immutable Collections

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CopyOnWriteArraySet;
 
// CopyOnWriteArrayList - thread-safe list with COW semantics
CopyOnWriteArrayList<EventListener> listeners = new CopyOnWriteArrayList<>();
 
// Write operations copy the entire internal array
listeners.add(new EventListener());  // O(n) - copies all elements
 
// Read operations are lock-free and fast
for (EventListener listener : listeners) {  // O(1) to start iteration
    listener.onEvent(event);
}
 
// Key characteristics:
// ✅ Iteration never throws ConcurrentModificationException
// ✅ Reads are lock-free and very fast
// ✅ Iterators see a consistent snapshot at iteration start
// ✅ Thread-safe without external synchronization
// ❌ Writes are expensive - O(n) copy every time
// ❌ Memory overhead - may have multiple copies during concurrent writes
// ❌ Not suitable for write-heavy workloads
 
// CopyOnWriteArraySet - backed by CopyOnWriteArrayList
CopyOnWriteArraySet<String> tags = new CopyOnWriteArraySet<>();
tags.add("important");
tags.add("urgent");
// Contains check is O(n) - linear scan of array
 
// Ideal use cases:
// 1. Event listeners - rarely added/removed, frequently iterated
class EventDispatcher {
    private final CopyOnWriteArrayList<EventListener> listeners = 
        new CopyOnWriteArrayList<>();
    
    public void addListener(EventListener listener) {
        listeners.add(listener);  // Rare operation
    }
    
    public void removeListener(EventListener listener) {
        listeners.remove(listener);  // Rare operation
    }
    
    public void dispatch(Event event) {
        // Very frequent operation - lock-free!
        for (EventListener listener : listeners) {
            listener.onEvent(event);
        }
    }
}
 
// 2. Configuration caches
class ConfigCache {
    private final CopyOnWriteArrayList<ConfigEntry> entries = 
        new CopyOnWriteArrayList<>();
    
    // Called rarely on config reload
    public void updateAll(List<ConfigEntry> newEntries) {
        entries.clear();
        entries.addAll(newEntries);
    }
    
    // Called constantly for every request
    public ConfigEntry find(String key) {
        for (ConfigEntry entry : entries) {
            if (entry.getKey().equals(key)) {
                return entry;
            }
        }
        return null;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// Vavr (formerly Javaslang) provides persistent collections for Java
import io.vavr.collection.List;
import io.vavr.collection.Map;
import io.vavr.collection.Set;
import io.vavr.collection.Vector;
 
// Persistent List (linked list - prepend is O(1))
List<String> list1 = List.of("B", "C", "D");
List<String> list2 = list1.prepend("A");  // O(1) - shares tail
 
System.out.println(list1);  // List(B, C, D) - unchanged
System.out.println(list2);  // List(A, B, C, D) - new list
 
// Persistent Vector (indexed access in O(log32 n) ≈ O(1))
Vector<Integer> vec1 = Vector.of(1, 2, 3, 4, 5);
Vector<Integer> vec2 = vec1.append(6);      // Near O(1)
Vector<Integer> vec3 = vec2.update(2, 99);  // Update element at index 2
 
System.out.println(vec1);  // Vector(1, 2, 3, 4, 5) - unchanged
System.out.println(vec2);  // Vector(1, 2, 3, 4, 5, 6)
System.out.println(vec3);  // Vector(1, 2, 99, 4, 5, 6)
 
// Persistent Map (hash array mapped trie - O(log32 n))
Map<String, Integer> map1 = Map.of("a", 1, "b", 2);
Map<String, Integer> map2 = map1.put("c", 3);
Map<String, Integer> map3 = map2.remove("a");
 
System.out.println(map1);  // HashMap((a, 1), (b, 2)) - unchanged
System.out.println(map2);  // HashMap((a, 1), (b, 2), (c, 3))
System.out.println(map3);  // HashMap((b, 2), (c, 3))
 
// Persistent Set
Set<String> set1 = Set.of("x", "y", "z");
Set<String> set2 = set1.add("w");
Set<String> set3 = set2.remove("y");
 
// All versions coexist - perfect for concurrent access!
 
// Common operations with fluent API
Vector<Integer> result = Vector.rangeClosed(1, 100)
    .filter(n -> n % 2 == 0)      // Keep evens
    .map(n -> n * n)               // Square them
    .takeRight(10);                // Last 10
 
// Thread-safe by design - no synchronization needed
AtomicReference<Map<String, User>> users = new AtomicReference<>(Map.empty());
 
// Safe concurrent updates
users.updateAndGet(current -> current.put("alice", aliceUser));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

// Google Guava immutable collections
import com.google.common.collect.*;
 
// ImmutableList with builder
ImmutableList<String> list = ImmutableList.<String>builder()
    .add("Alpha")
    .add("Beta")
    .addAll(existingList)
    .build();
 
// ImmutableSet preserves insertion order (unlike Set.of())
ImmutableSet<String> set = ImmutableSet.of("A", "B", "C");
 
// ImmutableMap with builder
ImmutableMap<String, Integer> map = ImmutableMap.<String, Integer>builder()
    .put("one", 1)
    .put("two", 2)
    .put("three", 3)
    .buildOrThrow();  // Throws on duplicate keys
 
// ImmutableMultimap - multiple values per key
ImmutableMultimap<String, String> multimap = ImmutableMultimap.<String, String>builder()
    .put("fruit", "apple")
    .put("fruit", "banana")
    .put("vegetable", "carrot")
    .build();
 
multimap.get("fruit");  // Returns ImmutableCollection ["apple", "banana"]
 
// ImmutableBiMap - bidirectional map
ImmutableBiMap<String, Integer> bimap = ImmutableBiMap.of(
    "one", 1,
    "two", 2
);
bimap.get("one");     // 1
bimap.inverse().get(1);  // "one"
 
// ImmutableSortedSet / ImmutableSortedMap
ImmutableSortedSet<Integer> sorted = ImmutableSortedSet.of(3, 1, 4, 1, 5, 9, 2, 6);
// [1, 2, 3, 4, 5, 6, 9] - duplicates removed, sorted
 
// ImmutableTable - two-dimensional map
ImmutableTable<String, String, Integer> table = ImmutableTable.<String, String, Integer>builder()
    .put("Alice", "Math", 95)
    .put("Alice", "English", 88)
    .put("Bob", "Math", 92)
    .build();
 
table.get("Alice", "Math");  // 95
table.row("Alice");  // Map: {"Math": 95, "English": 88}
table.column("Math");  // Map: {"Alice": 95, "Bob": 92}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// Pattern 1: AtomicReference with Immutable Collection
// The collection is immutable; updates atomically swap the reference
 
public class UserRegistry {
    // Vavr persistent map for efficient updates
    private final AtomicReference<io.vavr.collection.Map<String, User>> users
        = new AtomicReference<>(io.vavr.collection.HashMap.empty());
    
    public void registerUser(User user) {
        users.updateAndGet(current -> current.put(user.getId(), user));
    }
    
    public Optional<User> findUser(String id) {
        return users.get().get(id).toJavaOptional();
    }
    
    public List<User> getAllUsers() {
        return users.get().values().toJavaList();
    }
    
    public void removeUser(String id) {
        users.updateAndGet(current -> current.remove(id));
    }
    
    // Bulk operations are also atomic
    public void registerAll(Collection<User> newUsers) {
        users.updateAndGet(current -> {
            io.vavr.collection.Map<String, User> updated = current;
            for (User user : newUsers) {
                updated = updated.put(user.getId(), user);
            }
            return updated;
        });
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// ❌ INEFFICIENT: Creating intermediate immutable objects
io.vavr.collection.List<Integer> inefficient = io.vavr.collection.List.empty();
for (int i = 0; i < 1000000; i++) {
    inefficient = inefficient.append(i);  // Each append creates new list structure!
}
// Result: ~1 trillion operations instead of ~1 million
 
// ✅ EFFICIENT: Use mutable builder, then convert
List<Integer> efficient = IntStream.range(0, 1000000)
    .boxed()
    .collect(Collectors.toUnmodifiableList());
 
// ✅ EFFICIENT: Guava builder pattern
ImmutableList.Builder<Integer> builder = ImmutableList.builder();
for (int i = 0; i < 1000000; i++) {
    builder.add(i);  // Mutable accumulation
}
ImmutableList<Integer> result = builder.build();  // One-time immutable conversion
 
// ✅ EFFICIENT: Vavr collector
io.vavr.collection.Vector<Integer> vavrEfficient = IntStream.range(0, 1000000)
    .boxed()
    .collect(io.vavr.collection.Vector.collector());
 
// ✅ EFFICIENT: Prepending to persistent list (O(1) each)
io.vavr.collection.List<Integer> prependEfficient = io.vavr.collection.List.empty();
for (int i = 999999; i >= 0; i--) {
    prependEfficient = prependEfficient.prepend(i);  // O(1) prepend
}
 
// ❌ INEFFICIENT: Multiple immutable map puts in loop
io.vavr.collection.Map<String, Integer> inefficientMap = io.vavr.collection.HashMap.empty();
for (int i = 0; i < 10000; i++) {
    inefficientMap = inefficientMap.put("key" + i, i);  // Still O(log n) each, but many allocations
}
 
// ✅ EFFICIENT: Convert from mutable builder
Map<String, Integer> mutableMap = new HashMap<>();
for (int i = 0; i < 10000; i++) {
    mutableMap.put("key" + i, i);
}
ImmutableMap<String, Integer> efficientMap = ImmutableMap.copyOf(mutableMap);