---

Junior Level

Персистентные (постоянные) структуры данных — это неизменяемые структуры, которые при “изменении” сохраняют предыдущую версию и возвращают новую.

Простая аналогия

Представьте Git: когда вы делаете коммит, создаётся новая версия кода, но все старые коммиты остаются доступными.

Пример

io.vavr.collection.List<String> v1 = io.vavr.collection.List.of("A", "B");
io.vavr.collection.List<String> v2 = v1.append("C");
// v1 = List("A", "B"), v2 = List("A", "B", "C") — v1 не изменился!

Обе версии существуют одновременно и не мешают друг другу.

---

Middle Level

Принцип работы: Structural Sharing

Вместо полного копирования, персистентные структуры используют разделение данных:

При добавлении элемента в персистентное дерево:

1. Создаётся новая нода для добавляемого элемента
2. Копируются только узлы на пути от корня до нового элемента
3. Все остальные ветви остаются общими для старой и новой версии

Результат: новая версия за $O(\log n)$ вместо $O(n)$ при полном копировании.

В стандартном JDK

В JDK нет персистентных коллекций с structural sharing. List.of() и аналоги создают иммутабельные, но не персистентные коллекции:

• List.of(), Collections.unmodifiableList() — либо копируют всё, либо запрещают изменения

Библиотеки для Java

• Vavr (бывший Javaslang) — List, HashMap, Set на базе HAMT
• PCollections — лёгкая библиотека персистентных коллекций

Когда использовать

• Undo/Redo — история изменений хранится “бесплатно”
• Event Sourcing / CQRS — снапшоты состояния
• Многопоточность — безопасные снапшоты без блокировок

---

Senior Level

HAMT (Hash Array Mapped Trie)

Большинство персистентных Map используют HAMT — дерево, где ключи распределяются по битам хеш-кода:

• Поиск: $O(\log_{32} n)$ — фактически $O(1)$
• Вставка: $O(\log_{32} n)$ — копируется только путь
• Structural sharing — общие ветви между версиями

Сравнение с обычными коллекциями

Операция	ArrayList	Persistent Vector (Vavr)
get(i)	O(1)	O(log₃₂ n)
add	O(1)*	O(log₃₂ n)
update	O(1)	O(log₃₂ n)
Копирование	O(n)	O(log₃₂ n)

*amortized

Применение в распределённых системах

• Event Sourcing — каждое событие иммутабельно, состояние пересчитывается
• Snapshot isolation — сохранение “состояния БД на 12:00”
• Реактивное программирование — потоки неизменяемых состояний

Резюме для Senior

• Персистентность = Иммутабельность + Structural Sharing
• Решение проблемы $O(n)$ копирования при иммутабельных изменениях
• HAMT — ключевая структура данных: $O(\log_{32} n)$ для всех операций
• Критично для Event Sourcing, CQRS, функционального программирования

---

🎯 Шпаргалка для интервью

Обязательно знать:

• Персистентные структуры = иммутабельность + structural sharing — при изменении копируется только путь
• Аналогия — Git: новый коммит = новая версия, старые доступны
• Structural Sharing: при добавлении элемента копируются узлы на пути, остальные ветви общие — $O(\log n)$
• HAMT (Hash Array Mapped Trie) — дерево с распределением по битам хеша: $O(\log_{32} n)$
• JDK не имеет персистентных коллекций; List.of() — иммутабельные, но не персистентные
• Библиотеки: Vavr, PCollections; применение: Undo/Redo, Event Sourcing, Snapshot isolation

Частые уточняющие вопросы:

• Persistent = сохраняется на диск? — Нет, “persistent” = сохраняет предыдущие версии в памяти
• List.of() — персистентная коллекция? — Нет, иммутабельная но не персистентная; нет structural sharing
• Чем лучше обычной копии? — $O(\log n)$ вместо $O(n)$ — копируется только путь к изменённому элементу
• Где применять? — Undo/Redo, Event Sourcing, CQRS, многопоточность с безопасными снапшотами

Красные флаги (НЕ говорить):

• «Персистентные = сериализуемые» — persistent = сохраняют версии, не про persistence
• «List.of() — персистентная структура» — это иммутабельная, но без structural sharing
• «Vavr — часть JDK» — это сторонняя библиотека
• «Персистентные структуры медленнее ArrayList» — для get O(1) vs O(log₃₂ n), но для копирования O(log n) vs O(n)

Связанные темы:

• [[14. В чём разница между shallow copy и deep copy]]
• [[23. Как иммутабельность влияет на производительность]]
• [[25. Есть ли недостатки у иммутабельных объектов]]
• [[12. Как защитить коллекцию от изменений]]