Что такое персистентные (иммутабельные) структуры данных и structural sharing?

Персистентная структура при изменении не портит себя, а возвращает новую версию, причём старые версии остаются доступными; дёшево это благодаря structural sharing — новая версия переиспользует все неизменённые части старой.

Как достигается sharing

• Иммутабельный связный список: добавление в голову создаёт один узел, хвост общий для обеих версий.
• Деревья и path copying: при изменении копируется только путь от корня до изменённого узла — O(log n) новых узлов, остальное общее.
• Векторы и мапы в Clojure, Scala и Immutable.js — префиксные деревья с ветвлением 32 (HAMT для мап): глубина не больше 7 даже для миллиардов элементов, обновление почти O(1).

Тот же принцип в JS-коде

const prev = { user: { name: "Ann" }, settings: { theme: "dark" } };

const next = { ...prev, user: { ...prev.user, name: "Bob" } };

next.settings === prev.settings; // true — ветка переиспользована
next.user === prev.user;         // false — путь скопирован

На этом React и Redux строят дешёвое обнаружение изменений через ===.

Плюсы и цена

• Безопасное разделение между потоками, undo/redo и time-travel почти даром.
• Цена: больше аллокаций и нагрузки на GC, pointer chasing хуже для кеша; для пакетных изменений есть transients — временно мутабельная копия.

Коротко для собеседования

Персистентная структура при изменении создаёт новую версию, копируя только путь до изменённого места и переиспользуя остальное. В JS это спред по пути обновления: нетронутые ветки сохраняют ссылку, и сравнение через === сразу показывает, что поменялось — на этом держатся React, Redux и Immer.