---

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. Як захистити колекцію від змін]]