Что такое persistent data structures

В Computer Science термин «Persistent Data Structure» (Персистентная структура данных) НЕ имеет отношения к записи данных на диск или в базу данных (это называется Data Persiste...

🟢 Junior Level

30-секундный ответ

В Computer Science термин «Persistent Data Structure» (Персистентная структура данных) НЕ имеет отношения к записи данных на диск или в базу данных (это называется Data Persistence).

Персистентная структура данных — это неизменяемая (иммутабельная) структура в оперативной памяти, которая при любых операциях изменения (добавление, удаление, обновление) всегда сохраняет все свои предыдущие версии доступными для чтения.

При модификации создаётся новая версия структуры, при этом:

Старая версия остаётся на 100% нетронутой.
Новая версия переиспользует большую часть памяти старой версии благодаря принципу структурного разделения (Structural Sharing).

Наглядная аналогия из жизни: Git

Представьте систему контроля версий Git:

Когда вы фиксируете новый коммит, изменив одну строчку в файле, Git не копирует заново весь репозиторий на 10 гигабайт.
Git создаёт объект нового коммита и переиспользует неизменённые деревья и файлы из предыдущих коммитов.
Вы можете в любой момент переключиться на старый коммит или работать с новым параллельно.

Наглядный пример (на библиотеке Vavr)

// Персистентный список из библиотеки Vavr:
io.vavr.collection.List<String> v1 = io.vavr.collection.List.of("B", "C");

// "Добавляем" элемент в начало:
io.vavr.collection.List<String> v2 = v1.prepend("A");

System.out.println(v1); // List("B", "C")      <-- Старая версия не изменилась!
System.out.println(v2); // List("A", "B", "C") <-- Новая версия переиспользует v1

🟡 Middle Level

Наивная иммутабельность (например, new ArrayList<>(oldList) или List.copyOf()) при добавлении одного элемента вынуждена полностью копировать массив за $O(N)$ по времени и памяти.

Персистентные структуры данных решают эту проблему через Structural Sharing:

1. Персистентный связный список (Singly Linked List)

Версия 1 (v1):                    [Node "B"] ──► [Node "C"] ──► null
                                        ▲
                                        │ (Разделяемый хвост)
Версия 2 (v2 = v1.prepend("A")):  [Node "A"] ──┘

Операция prepend выполняется за $O(1)$ по времени и выделяет память ровно под один новый узел Node "A".
Узлы "B" и "C" безопасно разделяются между обеими версиями в памяти кучи (Heap).

2. Персистентные деревья: Копирование пути (Path Copying)

При модификации узла в сбалансированном дереве создаются копии только тех узлов, которые лежат на пути от корня к целевому листу ($O(\log N)$ узлов). Все остальные поддеревья (до 99% дерева) остаются разделяемыми:

Старый корень (Root v1) ──► [Left Subtree (Общее)]    [Node B (Старый)]
                                                             ▲
                                                             │
Новый корень (Root v2)  ──► [Left Subtree (Общее)]    [Node B (Новый)] ──► [New Leaf]

Классификация персистентности в Computer Science

Частично персистентные (Partially Persistent): можно читать любые прошлые версии, но модифицировать разрешено только самую последнюю версию (линейная история).
Полностью персистентные (Fully Persistent): любую версию из прошлого можно модифицировать, создавая ветвления истории версий (дерево версий, как ветки в Git).
Конфлуэнтно персистентные (Confluently Persistent): поддерживают слияние двух разных версий в одну (аналог git merge).

Разница между коллекциями JDK и Vavr

🔴 Senior Level

HAMT (Hash Array Mapped Trie) — Стандарт функциональных структур

В библиотеках Vavr (Java), Clojure и Scala персистентные Map и Set реализованы на базе структуры HAMT (Hash Array Mapped Trie):

32-ричное префиксное дерево (32-way Branching):
- 32-битный hashCode() ключа разбивается на фрагменты по 5 бит ($2^5 = 32$).
- Каждый уровень дерева отвечает за свои 5 бит хэша.
- Максимальная глубина дерева для 4 миллиардов элементов составляет всего $\lceil 32 / 5 \rceil = 7$ уровней!
Битовое сжатие (Bitmap Indexing) и инструкция POPCNT:
- Чтобы узлы дерева не хранили массив из 32 пустых указателей, каждый узел хранит 32-битное число-маску (bitmap) и массив только реально существующих дочерних ссылок.
- Позиция ребенка вычисляется за 1 такт CPU через аппаратную инструкцию процессора POPCNT (подсчёт установленных бит в маске):
```
int index = Integer.bitCount(bitmap & ((1 << bitPos) - 1));
```
Сложность:
- Поиск и добавление занимают $O(\log_{32} N) \le 7$ переходов, что на практике работает так же быстро, как $O(1)$ в стандартной HashMap, но обеспечивает полную неизменяемость и сохранение версий.

Lock-Free управление состоянием через `AtomicReference`

Персистентные структуры данных идеальны для моделирования высоконагруженного реактивного состояния:

public class MarketOrderBook {
    // Неизменяемая персистентная мапа стакана заявок
    private final AtomicReference<io.vavr.collection.Map<String, Order>> orders = 
        new AtomicReference<>(io.vavr.collection.HashMap.empty());

    public void placeOrder(Order order) {
        // Lock-Free атомарная смена версий за O(log32 N) без мьютексов:
        orders.updateAndGet(current -> current.put(order.id(), order));
    }

    public io.vavr.collection.Map<String, Order> getSnapshot() {
        // Мгновенный снимок всего стакана за O(1) (копирование 1 ссылки на Root):
        return orders.get();
    }
}

4 Tricky Questions

1. В чём фундаментальная разница между частично персистентными (Partially Persistent) и полностью персистентными (Fully Persistent) структурами данных?

Ответ:

Partially Persistent (Частично персистентные): позволяют читать состояние структуры на любой момент времени в прошлом, но операция записи разрешена только к самой последней (актуальной) версии. История модификаций строго линейна ($V_0 \to V_1 \to V_2$).
Fully Persistent (Полностью персистентные): позволяют выполнять операции записи к любой версии из прошлого. При модификации версии $V_1$ порождается новая ветка $V_1’$, превращая историю версий в дерево (как ветвление веток branch в Git). Почти все функциональные структуры в Java (Vavr, PCollections) являются полностью персистентными.

2. Как структура HAMT избегает расхода памяти на 32-элементные массивы в каждом узле, если у узла всего 2 потомка? Объясните работу `bitmap` и `POPCNT`.

Ответ: Вместо массива Node[32] узел HAMT хранит 32-битный примитив int bitmap и компактный массив Node[], чей размер равен количеству реальных потомков (в данном случае 2). Каждый бит в bitmap указывает, занят ли соответствующий из 32 слотов (1 — узел есть, 0 — узла нет). Чтобы узнать индекс нужного потомка в компактном массиве:

Вычисляется битовая маска для всех слотов, расположенных правее нужного: mask = (1 << bitPosition) - 1.
Выполняется побитовое И: bitmap & mask.
Количество единиц в результате даёт точный индекс в компактном массиве. Этот подсчёт компилируется в одну аппаратную инструкцию процессора POPCNT (в Java: Integer.bitCount(...)), выполняющуюся за 1 такт CPU без циклов и проверок.

3. Почему в стандартной библиотеке Java (JDK) до сих пор нет встроенных персистентных структур данных?

Ответ:

Историческая приверженность императивной парадигме: Java изначально проектировалась вокруг изменяемых массивов (Object[]) и мутабельных коллекций (ArrayList, HashMap) для максимальной производительности на однопоточных процессорах конца 90-х.
Локальность данных в кэше CPU (Cache Locality): Стандартный ArrayList использует непрерывный блок памяти, что идеально утилизирует кэш-линии L1/L2 процессора и аппаратный prefetcher. Древовидные структуры (HAMT, деревья) имеют больше ссылочных переходов (pointer chasing), что при однопоточных вычислениях может уступать плоским массивам по задержке доступа.
Сложность API: Персистентные коллекции требуют возврата новой ссылки на коллекцию при каждой операции (list = list.append(x)), что ломает привычный контракт интерфейсов java.util.Collection.

4. Как персистентные векторы (Persistent Vector в Clojure / Vavr) обеспечивают быстрое случайное чтение по индексу за $O(1)$?

Ответ: Персистентный вектор реализован не как связный список, а как 32-ричное сбалансированное дерево (32-way B-tree / Trie), где все данные хранятся в листьях.

Чтение по индексу $i$ разбивает двоичное представление индекса на блоки по 5 бит.
Каждый 5-битный блок используется как прямой индекс в массиве узла соответствующего уровня.
Поскольку максимальная глубина дерева фиксирована и не превышает 6–7 уровней (даже для миллиардов элементов), переход по фиксированному числу ссылок считается алгоритмически $O(\log_{32} N) \approx O(1)$ константным доступом.

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

Главное о Persistent Data Structures

Определение: иммутабельные структуры в RAM, сохраняющие все предыдущие версии при любых изменениях.
Главный механизм: Structural Sharing (переиспользование узлов между старой и новой версией вместо полного $O(N)$ копирования).
HAMT (Hash Array Mapped Trie): основа быстрых персистентных Map/Set (32-ричные деревья, битовые маски, инструкция POPCNT).
Сложность: добавление/поиск за $O(1)$ для списков и $O(\log_{32} N)$ для Map/Set.
Где применять: Lock-Free управление состоянием (AtomicReference), Event Sourcing, Undo/Redo, реактивные системы.
Библиотеки для Java: Vavr, PCollections.

Сравнение с обычными подходами

Красные флаги на собеседовании (Чего говорить нельзя)

❌ «Персистентные структуры данных — это таблицы, сохраняемые на жесткий диск через Hibernate/JPA» — фатальная путаница терминов CS и Enterprise Java.
❌ «Персистентная структура при добавлении копирует весь массив целиком» — нет, копируются только изменённые узлы (Structural Sharing).
❌ «List.of() в Java — это персистентная структура» — нет, у него нет механизма эффективного создания версий.