What Are Persistent Data Structures

🟢 Junior Level

30-Second Summary

[!NOTE] In Computer Science, the term “Persistent Data Structure” does NOT refer to writing data to a database or disk (which is Data Persistence).

A Persistent Data Structure is an in-memory immutable data structure that always preserves all previous versions whenever it is modified (via addition, deletion, or update).

When a mutation occurs:

The previous version remains 100% untouched and accessible across all threads.
The newly created version reuses the majority of the existing memory via Structural Sharing.

Real-World Analogy: Git Version Control

Think of Git:

When you commit a one-line change in a repository, Git does not clone the entire 10GB project from scratch.
Git creates a new commit object pointing to a new tree node, while referencing all unchanged trees and blobs from previous commits.
You can inspect or check out any previous commit at any time without corrupting the current branch.

Code Example: Vavr Persistent List

// Persistent List from the Vavr library:
io.vavr.collection.List<String> v1 = io.vavr.collection.List.of("B", "C");

// "Adding" an element to the head:
io.vavr.collection.List<String> v2 = v1.prepend("A");

System.out.println(v1); // Prints List("B", "C")      <-- Version 1 is UNTOUCHED!
System.out.println(v2); // Prints List("A", "B", "C") <-- Version 2 reuses v1's tail

🟡 Middle Level

Naive immutability (such as new ArrayList<>(oldList) or List.copyOf()) copies the entire backing array on every update, incurring an $O(N)$ time and memory allocation penalty.

Persistent data structures eliminate this penalty via Structural Sharing:

1. Persistent Singly Linked List ($O(1)$ Prepend)

Version 1 (v1):                    [Node "B"] ──► [Node "C"] ──► null
                                         ▲
                                         │ (Shared Tail)
Version 2 (v2 = v1.prepend("A")):  [Node "A"] ──┘

Prepending an element executes in $O(1)$ time and allocates exactly one new node (Node "A").
Nodes "B" and "C" are safely shared between both versions in heap memory.

2. Persistent Trees: Path Copying ($O(\log N)$ Updates)

When updating a node in a balanced tree, only the nodes along the direct path from the root to the target leaf are duplicated ($O(\log N)$ nodes). All other branches (often 95%+ of the tree) remain shared:

Root v1 ──► [Left Subtree (Shared)]    [Old Node B]
                                             ▲
                                             │
Root v2 ──► [Left Subtree (Shared)]    [New Node B] ──► [New Leaf]

Classification of Persistence in Computer Science

Partially Persistent: Any historical version can be read, but write operations are permitted only to the most recent version (linear history).
Fully Persistent: Any version from history can be read and modified, creating branching trees of versions (identical to Git branches).
Confluently Persistent: Supports merging two distinct historical versions into a single unified version (similar to git merge).

Collection Comparison: JDK Collections vs. Vavr Persistent Structures

Collection	Immutability	Persistent?	Modification Cost	Standard Library
`Collections.unmodifiableList`	Read-only wrapper	❌ No	Throws `UnsupportedOperationException`	Built-in JDK
`List.of("A", "B")` (Java 9+)	✅ Yes	❌ No	$O(N)$ full array duplication	Built-in JDK
`io.vavr.collection.List`	✅ Yes	🟢 Yes	$O(1)$ (Tail sharing)	External (Vavr)
`io.vavr.collection.HashMap`	✅ Yes	🟢 Yes (HAMT)	$O(\log_{32} N)$	External (Vavr)

🔴 Senior Level

HAMT (Hash Array Mapped Trie) Architecture

In modern functional runtimes (Vavr in Java, Clojure, Scala), persistent maps and sets are built on Hash Array Mapped Tries (HAMT):

32-Way Branching (5-Bit Hash Chunks):
- The 32-bit hashCode() of a key is partitioned into 5-bit slices ($2^5 = 32$).
- Each level of the tree inspects a corresponding 5-bit chunk.
- For an index of 4 billion items, the maximum tree depth is $\lceil 32 / 5 \rceil = 7$ hops.
Bitmap Indexing and the Hardware POPCNT Instruction:
- To avoid allocating sparse 32-element arrays on every node, each node stores a 32-bit int bitmap mask and a compact array containing only populated children.
- The child’s array offset is computed in 1 CPU clock cycle using the hardware POPCNT instruction (counting set bits):
```
int index = Integer.bitCount(bitmap & ((1 << bitPos) - 1));
```
Algorithmic Complexity:
- Lookups and insertions take $O(\log_{32} N) \le 7$ pointer dereferences, performing with near-$O(1)$ speed in practice while preserving complete immutability and historical versioning.

High-Throughput Lock-Free State Snapshots

Persistent data structures enable atomic, lock-free reactive state management via AtomicReference:

public class MarketOrderBook {
    // Immutable persistent order book map
    private final AtomicReference<io.vavr.collection.Map<String, Order>> orders = 
        new AtomicReference<>(io.vavr.collection.HashMap.empty());

    public void placeOrder(Order order) {
        // Lock-Free atomic version rotation in O(log32 N) without mutex locks:
        orders.updateAndGet(current -> current.put(order.id(), order));
    }

    public io.vavr.collection.Map<String, Order> getSnapshot() {
        // Instantaneous O(1) point-in-time snapshot (single pointer copy):
        return orders.get();
    }
}

4 Tricky Questions

1. What is the fundamental difference between Partially Persistent and Fully Persistent data structures?

Answer:

Partially Persistent: Allows querying any past version $V_i$, but mutations are strictly restricted to the latest head version ($V_{latest}$). Modifications generate a linear historical progression ($V_0 \to V_1 \to V_2$).
Fully Persistent: Allows both reading and modifying any historical version. Mutating version $V_1$ creates a fork $V_1’$, structuring the version history as a directed acyclic tree of versions (analogous to branching in Git). Functional collections in Java (Vavr, PCollections) are fully persistent.

2. How does HAMT avoid allocating 32-element arrays in sparse nodes? Explain the role of `bitmap` and `POPCNT`.

Answer: Instead of storing a full Node[32] array where most slots are null, an HAMT node stores an int bitmap (32 bits) and a compact Node[] array sized to the exact count of active children. Each bit in the bitmap indicates whether that child slot is populated (1) or vacant (0). To locate a child’s offset in the compact array:

A bitmask is generated for all positions below the target slot: mask = (1 << bitPos) - 1.
A bitwise AND isolates the active lower bits: bitmap & mask.
The number of set bits (1s) represents the exact index in the compact array. In Java, this is computed via Integer.bitCount(...), which compiles directly to the x86-64 hardware POPCNT instruction, executing in a single CPU cycle.

3. Why does the standard Java JDK still lack built-in persistent data structures?