Immutable Objects - Learning Module

Loading content...

0/246

Immutable Collections

Collections That Never Change

Individual immutable objects are powerful, but real applications work with collections—lists, maps, sets, and more complex structures containing many elements. How do we apply immutability principles to collections while maintaining practical performance?

Naive immutability for collections seems expensive: to 'add' an element to a list of 1 million items, must we copy all 1 million? For small collections this is fine, but at scale it becomes prohibitive.

Formerly, this was used as an argument against immutable collections. But decades of research in functional programming have produced elegant solutions: persistent data structures that enable efficient 'modification' operations while preserving immutability through structural sharing.

This page explores immutable collections from practical built-in options to sophisticated persistent structures, equipping you to work with large immutable datasets efficiently.

What You Will Learn

By the end of this page, you will understand: built-in immutable collection factories in modern languages, copy-on-write collections and their tradeoffs, persistent data structures and structural sharing, popular immutable collection libraries (Guava, Vavr, Immutable.js), performance characteristics and when to use each approach, and practical patterns for immutable collection usage in concurrent systems.

Built-in Immutable Collections

Modern languages provide built-in factory methods for creating immutable collections. These are the simplest starting point for immutable data.

Java
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
// Java 9+ immutable collection factories
import java.util.List;
import java.util.Set;
import java.util.Map;
 
// Immutable List
List<String> names = List.of("Alice", "Bob", "Charlie");
// names.add("Dave");  // UnsupportedOperationException
// names.set(0, "X");  // UnsupportedOperationException
 
// Immutable Set
Set<Integer> numbers = Set.of(1, 2, 3, 4, 5);
// numbers.add(6);  // UnsupportedOperationException
// Duplicate elements throw IllegalArgumentException at creation:
// Set.of(1, 2, 2);  // IllegalArgumentException
 
// Immutable Map
Map<String, Integer> ages = Map.of(
    "Alice", 30,
    "Bob", 25,
    "Charlie", 35
);
// ages.put("Dave", 40);  // UnsupportedOperationException
 
// For more than 10 entries, use Map.ofEntries:
Map<String, String> config = Map.ofEntries(
    Map.entry("host", "localhost"),
    Map.entry("port", "8080"),
    Map.entry("debug", "true"),
    Map.entry("timeout", "30000")
);
 
// Creating immutable copies from existing mutable collections
List<String> mutableList = new ArrayList<>(Arrays.asList("A", "B", "C"));
List<String> immutableCopy = List.copyOf(mutableList);
 
// The copy is truly independent:
mutableList.add("D");
System.out.println(immutableCopy.size());  // 3 - unaffected
 
// Characteristics:
// ✅ Null-hostile: null elements are not allowed (throws NullPointerException)
// ✅ Randomized iteration for Set/Map (security against hash collision attacks)
// ✅ Compact internal representation (less memory than wrapper-based approaches)
// ✅ Thread-safe for reads
// ❌ No indexed access optimization for Set
// ❌ No way to "derive" new collection with changes

Unmodifiable vs Immutable

Be careful of the distinction: Collections.unmodifiableList() in Java creates a VIEW that doesn't allow modifications through that view, but if someone holds a reference to the backing list, changes will be visible. List.copyOf() creates a true immutable COPY. Always prefer copyOf() for thread safety.

Copy-On-Write Collections

Copy-on-write (COW) is a strategy where modifications to a collection create a complete copy, while all read operations access the existing structure without copying. This provides thread-safe reads without synchronization.

Java provides two built-in copy-on-write collections:

CopyOnWriteCollections.java
Java
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;
    }
}

Copy-On-Write Performance Characteristics
Operation	Time Complexity	Notes
add(element)	O(n)	Copies entire array
remove(element)	O(n)	Copies entire array
get(index)	O(1)	Direct array access
contains(element)	O(n)	Linear scan
iterator()	O(1)	Returns snapshot reference
iteration (full)	O(n)	No synchronization needed
size()	O(1)	Cached value

When NOT to Use Copy-On-Write

Avoid CopyOnWriteArrayList when: writes are frequent (more than a few per second), the collection is large (copying becomes expensive), or you need indexed access patterns like contains() that require linear scans. For these cases, consider ConcurrentHashMap or persistent data structures.

Persistent Data Structures

Persistent data structures solve the efficiency problem of immutable collections through structural sharing: when you 'modify' a persistent collection, the new version shares as much structure as possible with the original, only allocating new nodes for the changed portions.

This is not 'persistence' in the database sense—it means the old version 'persists' (remains available) after modifications.

Conceptual Example: Persistent List

Converting Mermaid diagram...

The Key Insight:

Persistent data structures use tree-like internal representations (often tries or balanced trees) where modification only requires creating new nodes along the path from root to the changed element. Unchanged subtrees are shared between versions.

Example: Persistent Vector (as used in Clojure, Scala)

A persistent vector uses a tree of 32-element arrays (a 32-way branching trie):

For a million elements, the tree is only ~4 levels deep (log₃₂(1,000,000) ≈ 4)
Updating one element creates ~4 new nodes, sharing all others
Time complexity: O(log₃₂ n) ≈ O(1) for practical sizes

This makes both old and new versions available efficiently.

PersistentDataStructures.java
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));

Hash Array Mapped Trie (HAMT)

Most persistent maps and sets use a Hash Array Mapped Trie (HAMT) internally. It provides O(log₃₂ n) operations by using 32-way branching based on hash code bits. For a billion elements, that's only ~6 levels deep. Phil Bagwell's 2001 paper 'Ideal Hash Trees' introduced this structure, now widely used in Clojure, Scala, and other functional languages.

Immutable Collection Libraries

Several mature libraries provide immutable collections for mainstream languages. Here's a comparison:

Immutable Collection Libraries Comparison
Library	Language	Key Features	Best For
Guava ImmutableCollections	Java	Simple API, good performance, null-hostile, builder pattern	Straightforward immutable collections without persistence
Vavr	Java	Full persistent collections, functional patterns, Option/Try/Either, pattern matching	Functional programming style, complex transformations
Eclipse Collections	Java	Rich API, primitive collections, lazy evaluation, immutable & mutable variants	High-performance with primitive specialization
Immutable.js	JavaScript	Persistent collections, deep equality, React-optimized, fromJS/toJS	React/Redux state management, complex nested data
Immer	JavaScript	Write 'mutable' code, produce immutable result, structural sharing	Simpler mental model, Redux reducers, migration from mutable code
pyrsistent	Python	Persistent vector, map, set; freeze/thaw pattern	Python immutable data structures with good performance

GuavaImmutable.java
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}

Performance Characteristics

Understanding performance characteristics helps choose the right immutable collection for your use case:

Time Complexity Comparison
Operation	ArrayList	CopyOnWriteList	Persistent Vector	Persistent List
get(index)	O(1)	O(1)	O(log₃₂ n) ≈ O(1)	O(n)
add (end)	O(1) amortized	O(n)	O(log₃₂ n) ≈ O(1)	O(n)
add (start)	O(n)	O(n)	O(log₃₂ n) ≈ O(1)	O(1)
update(index)	O(1)	O(n)	O(log₃₂ n) ≈ O(1)	O(n)
remove	O(n)	O(n)	O(log₃₂ n) ≈ O(1)	O(n)
iterate	O(n)	O(n)	O(n)	O(n)
Thread-safe reads	❌ No	✅ Yes	✅ Yes	✅ Yes

Key Observations:

Persistent Vector is the best general-purpose immutable list. It provides near-O(1) operations for all common cases.
Persistent List (linked list) excels at prepending but is slow for indexed access. Use when you only need stack-like operations.
CopyOnWriteArrayList is faster for reads than persistent structures but expensive for writes. Ideal for mostly-read scenarios.
Memory overhead of persistent structures (tree nodes) is usually offset by structural sharing on updates.

Benchmarks:

For a collection of 1 million elements:

Operation	CopyOnWriteArrayList	Vavr Vector
Single update	~5ms (full copy)	~0.001ms (path copy)
1000 updates	~5000ms	~1ms
Single read	~0.00001ms	~0.00003ms

The difference in update performance is dramatic—4-5 orders of magnitude!

Choose Based on Access Patterns

If you're creating a collection once and only reading after: use built-in List.of() or Guava ImmutableList (simpler, slightly faster reads). If you need to derive modified versions: use persistent structures (Vavr, Immutable.js) for dramatic write performance improvements.

Practical Patterns for Concurrent Systems

Let's see how immutable collections are used in real concurrent systems:

ConcurrencyPatterns.java
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;
        });
    }
}

Building Collections Efficiently

When building immutable collections incrementally, use transient or builder patterns to avoid creating intermediate immutable objects:

EfficientBuilding.java
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);

The Rule of Thumb

Use mutable builders or transients when building from scratch. Use persistent operations when deriving from existing collections. The asymptotic complexity is the same, but constant factors differ significantly for large-scale building.

Summary: Immutable Collections for Concurrent Systems

We've explored the full spectrum of immutable collection options, from simple built-in factories to sophisticated persistent data structures:

Key Takeaways

•Built-in factories (List.of, Set.of) — Use for simple cases where you create once and only read. No dependencies, good performance.
•Copy-on-write collections — Use for read-heavy scenarios with rare writes, like event listeners or configuration caches.
•Persistent data structures — Use when you need to derive modified versions efficiently. Structural sharing makes updates near-O(1).
•Choose libraries based on needs — Guava for simple immutability, Vavr for functional style, Immutable.js for React/Redux, Immer for easy migration.
•AtomicReference + immutable state — The primary pattern for thread-safe state management. Reads are lock-free; writes atomically swap references.
•Snapshot for consistency — Capture state at operation start for consistent view throughout complex operations.
•Build efficiently — Use builders or transients for bulk construction; reserve persistent operations for derivation.

Module Complete:

You've now mastered immutability as a concurrency strategy. From understanding what immutability means and why it provides thread safety, through designing immutable objects correctly, to working with sophisticated immutable collections—you have the complete toolkit.

Immutability is one of the most powerful tools in a concurrent programmer's arsenal. It eliminates entire classes of bugs by design rather than through careful synchronization. While not applicable everywhere, for the vast majority of application code—domain models, messages, events, configurations, and more—immutability provides clarity, safety, and often performance benefits.

Module Complete

Congratulations! You've completed the module on Immutable Objects for Concurrency. You understand what immutability means at a deep level, how it provides thread safety, how to design immutable objects correctly, and how to work with immutable collections efficiently. These skills will serve you throughout your career in building safe, scalable concurrent systems.