结构共享（Structural Sharing）：Immutable.js 如何高效更新树？

——利用持久化数据结构（Persistent Data Structures）复用未变节点

“每次‘修改’都返回新对象？
别担心——99% 的节点，其实都是旧的。”

一、问题：不可变性的性能幻觉

当我们说“不可变”，直觉是：

const newState = { ...oldState, user: { ...oldState.user, age: 26 } };

这看起来要复制整个对象树，O(n) 时间与空间，性能灾难？

但 Immutable.js 等库通过 结构共享（Structural Sharing），让更新接近 O(log n)。

二、核心思想：持久化数据结构（Persistent Data Structure）

每次更新不修改原结构，而是生成一个新版本
新旧版本共享未变化的部分

这叫 “完全持久化”（Fully Persistent） —— 所有历史版本都有效。

类比：Git 的文件系统

• 你修改一个文件，Git 不复制整个项目
• 它只存储差异（diff），其他文件通过指针共享
• 历史版本依然可访问

Immutable.js 的数据结构就像“内存中的 Git”。

三、实现原理：从数组到树

1. 普通数组的困境

const arr = [1,2,3,4];
const newArr = [...arr.slice(0,2), 99, ...arr.slice(2)]; // [1,2,99,4]

需要复制 1,2 和 4，空间与时间 O(n)。

2. Immutable.js 的 Vector Trie（位向量Trie）

Immutable.js 将数组实现为 32 叉树（32-ary Tree），称为 Vector Trie。

结构示例（简化版）：

        Root
       /  |  \
     [ ][ ][*]     ← 每个节点是长度为 32 的数组
           |
         [ ][99][ ]... ← 只有这一条路径变化

当你更新索引 35 的元素：

• 索引 35 在第二层的第 1 个节点（35 ÷ 32 = 1）
• 只需创建：
  • 一个新的子节点（包含修改后的值）
  • 一个新的根节点（指向新子节点，其他子节点复用）

其他 31 个子节点完全复用。

四、深度更新：为何只复制一条路径？

示例：更新 map.getIn(['users', 0, 'profile', 'name'])

const newMap = map.setIn(['users', 0, 'profile', 'name'], 'Alice');

执行过程：

1. 从根开始，找到 users 节点
2. 创建 users 的新副本
3. 在新 users 中，只更新第 0 个用户节点
4. 创建该用户的 profile 新副本
5. 在新 profile 中更新 name

最终，只创建了从根到 name 的一条路径上的新节点，其余全部共享。

内存开销：

• 树高约 log₃₂(n)，每层创建一个新节点
• 对于 100 万元素，树高仅 4 层 → 只新增 4 个节点

五、关键数据结构与策略

结构	实现方式	共享策略
List / Vector	32 叉 Trie	路径复制
Map / OrderedMap	Hash Array Mapped Trie (HAMT)	子树共享
Set	基于 HAMT	同上
Stack	基于 List	复用底层结构

HAMT（哈希数组映射 Trie）：

• 使用哈希值决定节点位置
• 动态扩展，空间利用率高
• 支持高效查找、插入、删除

六、性能对比：突变 vs 不可变 + 结构共享

操作	突变数组	Immutable List
更新索引 i	O(1)	O(log₃₂ n) ≈ O(1)
内存开销	0（原地）	O(log n) 新节点
历史版本保留	❌	✅
时间旅行调试	❌	✅

对于 n=1,000,000：

• 突变：快，但破坏历史
• Immutable：慢常数倍，但安全、可追溯

七、代码示例：观察结构共享

const { List } = require('immutable');

const list1 = List([1,2,3,4,5]);
const list2 = list1.set(2, 99); // 更新索引 2

console.log(list1.get(0) === list2.get(0)); // true ← 元素 1 共享
console.log(list1.get(1) === list2.get(1)); // true ← 元素 2 共享
console.log(list1.get(3) === list2.get(3)); // true ← 元素 4 共享

// 只有索引 2 不同

即使 list1 和 list2 是“不同版本”，它们的大部分节点是物理共享的。

八、现代替代方案：Proxy + Immer

Immutable.js 的 API 较重，现代方案使用 Immer：

import produce from 'immer';

const nextState = produce(prevState, draft => {
  draft.users[0].name = 'Alice'; // 看似突变
  // Immer 内部使用 Proxy + 结构共享，生成新不可变对象
});

Immer 在底层依然依赖结构共享思想，但提供了更自然的写法。

九、工程实践建议

使用场景

• 状态管理（Redux, Zustand）
• 需要时间旅行或撤销功能
• 高频小更新，且需精确变更检测

避免场景

• 超高频更新（如游戏帧）
• 极致性能要求，且数据小
• 团队不熟悉 FP

结语：结构共享是“不可变性的灵魂”

它让“每次返回新对象”从性能噩梦变为工程可行方案。

Immutable.js 不是简单地复制数据，
而是用精巧的 树形结构 + 路径复制，
实现了 高效、安全、可追溯 的状态管理。

当你调用 setIn，
你得到的不是一个全新副本，
而是一个与旧版本共享 99% 节点的“新视角”。

这才是函数式编程在现实世界落地的关键。