Clojure 不可变数据结构：结构共享、持久化与 transient 优化

不可变是 Clojure 的默认，但它不是「每次修改复制整份」——那会慢到没法用。Clojure 用的是持久化数据结构 + 结构共享：每次「修改」复用绝大部分旧结构，只新开变化的路径。本文把原理讲透：持久化数据结构是什么、结构共享如何工作、HAMT（哈希数组映射树）与 vector 的 trie 实现、transient 的批量构建捷径，然后给时空复杂度对比、线程安全红利、选型与性能陷阱。理解这些，你才能「放心用不可变」且「写得不慢」。

1. 不可变的前提：持久化数据结构

1.1 什么是持久化数据结构

「持久化（persistent）」指修改后旧版本依然可用：

(def v1 [1 2 3])
(def v2 (conj v1 4))   ;; 新 vector，v1 不变

v1  ;; => [1 2 3]   旧版本还在（历史保留）
v2  ;; => [1 2 3 4]  新版本新增

对比「可变数据结构」（如 Java 的 ArrayList）：add 改的是同一个对象，旧引用看到新值。持久化则每次修改产出一个新值，旧值不受影响。

心智：不可变 = 「历史可回溯」。函数拿到的数据永远不会被别人改，这让并发安全与引用透明成为默认属性。

1.2 天真实现的代价

如果每次 conj 都复制整个 vector，(conj [1..n] x) 就是 O(n)，构建 n 元素要 O(n²)——不可用。所以 Clojure 需要结构共享。

2. 结构共享：只复制路径

2.1 树形 vector 的实现

Clojure 的 vector 是分支因子 32 的树（每节点最多 32 个槽），下标按「分段」定位：

[0 .. 31]  → 根节点（32 槽）
[0 .. 1023] → 根 → 32 个子节点，每个 32 槽
[0 .. 32767] → 根 → 32 → 32 个子节点 = 三层

conj 一个元素到 [0..1023]：
  只新建「路径上的」节点（复制根 + 复制目标子节点）
  其他 31 个子节点「共享」—— 旧 vector 与新的共享大部分树
→ 修改成本 O(log32 n) ≈ O(1) 常数（32 分支因子）

旧 v1 树:     根 ──┬── a[0..31]   ├── b[32..63]  ... (共享)
                 └── c[..]  ...  （conj 时被复制为新路径）
新 v2 树:     根*──┬── a[0..31]  ├── b[32..63]  ...（与 v1 共享）
                 └── c*  (新建) └── 新元素槽

心法：结构共享 = 「修改路径复制，其余引用共享」。分支因子 32 让树很矮（log32），于是几乎每步操作都近似常数时间，旧版本只多占「路径上新增节点」的空间。

2.2 空间代价

旧 vector 与新的共享节点 → 不重复占空间
只有「修改路径」上的节点是新对象
一次 conj：O(log32 n) 个新节点，其余共享
→ 不可变的「空间开销」是「路径长度」而非「全量复制」

心智：不可变的内存增长是「每版本多一条路径」——对 32 分支的矮树，路径只有 2~3 层，所以多版本共存的空间代价可控。这也让「保留全部历史版本」（如撤销栈）变得可行。

3. HAMT：hash map 的实现

3.1 哈希数组映射树

hash-map 用 HAMT：键的哈希按 5 bit 一组逐层分叉（32 路），与 vector 同构，但用哈希寻址而非下标：

hash map 查找路径：
  (hash k) = 0x1A2B3C4D
  取低 5 bit（0x0D）→ 子节点 A
  取下 5 bit（0x26）→ 子节点 B
  ... 直到叶子放 {k v}
→ 查找/修改 O(log32 n)，同样结构共享

(def m1 {:a 1 :b 2 :c 3})
(def m2 (assoc m1 :d 4))   ;; 新建路径，其余共享
m1  ;; => {:a 1 :b 2 :c 3}（不变）

3.2 排序集合的特殊性

(sorted-map :a 1 :b 2)    ;; 红黑树实现，O(log n)，不可共享前缀
(sorted-set 1 2 3)        ;; 同上

排序集合是树（红黑树），修改也是 O(log n)，但节点更胖、缓存友好性差——只有需要「有序遍历/范围查询」时才用，否则普通 map/set 更快。

心法：普通 map/set 是 HAMT（哈希寻址、结构共享），sorted 是红黑树（有序、O(log n)）。能不用 sorted 就不用——「哈希 + 共享」是性能与内存的双优默认。

4. Transient：批量构建的捷径

4.1 反复 conj 的浪费

;; 不可变的痛点：循环里反复 conj，每次都新建路径
(reduce conj [] (range 100000))  ;; 10w 次结构共享，仍可接受
;; 但对「一次性构建大数据集」，transient 更快

transient 提供一个临时可变版本——构建期间可变（O(1) 原地改），结束 persistent! 变回不可变：

;; 批量构建：transient 快 ~2-3 倍
(defn build-index [items]
  (-> (transient {})                       ;; 可变起点
      (reduce (fn [acc item] (assoc! acc (:k item) (:v item))) items)
      (persistent!)))                      ;; 冻结为不可变

;; vector 同理
(def v (persistent! (reduce conj! (transient []) (range 1000000))))

4.2 transient 的纪律

transient 三条铁律：
  1. transient 版本只在本函数内用，不可逃逸
     （别把它塞进 atom/传给别处——那是可变状态泄漏）
  2. 只能调用带 ! 的变体（assoc!/conj!/dissoc!）
  3. 结束时必须 persistent!，否则数据不可读
→ transient 是「构建期优化」，不是「逃逸到可变世界」的通行证

心法：transient 用于「一次构建大量数据」——reduce 聚合、解析结果装配、批量清洗。构建期用可变（O(1)），完成后冻结成不可变（线程安全）。数据量小（< 几百）差别可忽略，别为微优化引入复杂度。

5. 复杂度总览与选型

5.1 时间复杂度对比

* vector 按下标查找是 O(1)（树高固定段内直取）。

5.2 选型决策

心法：默认 vector + map + set（都是 HAMT/矮树，结构共享），只有明确需要「有序」才上 sorted，只有「头插为主」才用 list。选型错了性能会差一个量级（如用 list 随机访问 = O(n²)）。

6. 不可变的并发红利

6.1 免费线程安全

;; 可变世界：多个线程读同一对象，一个写 → 竞态 → 需要锁
;; 不可变世界：数据永不变化 → 任何线程可安全共享读取
(def shared-config {:port 8080 :db "prod"})   ;; 可被任意线程读

;; 更新 = 产生新值，配合原子引用原子切换
(def state (atom {:count 0}))
(swap! state update :count inc)   ;; 原子地「读旧 → 算新 → CAS 替换」

6.2 函数式的心智简化

不可变带来的推理红利：
  1. 函数不改变入参 → 调用顺序无关紧要
  2. 引用透明 → 同样的输入永远同样输出
  3. 并发下无需「担心谁改了我的数据」
  4. 撤销/时间旅行 → 保留历史版本即可
→ 调试、测试、并发正确性成本大幅下降

心法：不可变是「并发正确性」的免费午餐——数据不可变则竞态只发生在「引用切换」这一处，交给 atom/ref 的原子语义即可。写并发代码不再逐行找「谁动了我的数组」。

7. 性能陷阱与优化实践

7.1 常见陷阱

7.2 优化三板斧

;; 1. 批量构建 → transient
(reduce (fn [acc x] (assoc! acc k x)) (transient {}) items)

;; 2. 热的局部状态 → atom + swap!（而非反复 conj 全量）
(def local (atom []))
(swap! local conj item)   ;; 只换引用，历史版本被 GC

;; 3. 数据量大且频繁改 → 分段（partition）+ 每段 transient

7.3 何时优化

数据量 < 1k：直接不可变操作，可读性优先
1k ~ 100k：注意批处理（transient）避免 O(n²)
100k+：显式测性能（criterium），看是不是结构问题
→ 先正确，再按数据规模对症优化

心法：不可变的性能陷阱几乎都是「算法级」而非「常数级」——用错结构（list 当数组）、批量操作没用 transient、数据量大还反复整份修改。先保证结构选型正确，再用 criterium 实测（见 /clojure-performance-graalvm/）。

8. 深入：自定义持久化结构

8.1 接口认知

Clojure 数据结构的「持久化」由内部树实现，但你感知到的是统一接口：

;; 核心操作：conj/assoc/get/dissoc/disj/count/seq
;; 所有持久化结构支持这些「纯函数」操作
;; 无论内部是 HAMT 还是 trie，对调用方透明

(defprotocol Persisted
  (add-v [this v])
  (get-v [this k]))

8.2 何时自定义

一般不需要：
  内置 vector/map/set/list 覆盖 99% 场景
自定义的价值：
  1. 特殊语义的集合（区间树、稀疏结构）
  2. 极致的性能要求（已被内置优化到近常数）
→ 先确认内置结构真的不够，再考虑手写

心法：Clojure 内置持久化结构已经「够好且够快」——理解它们背后的结构共享与 HAMT，更多是为了「放心使用」和「选对结构」，而非鼓励再造轮子。90% 的性能问题出在结构选型，而不是结构实现。

9. 实战：用不可变做事务性更新

事务性更新是结构共享的杀手级场景——保留历史、支持回滚、并发安全：

;; 订单状态机：每次更新产出新版本，历史留存
(defn apply-event [order event]
  (case (:type event)
    :created   (assoc order :status :created)
    :item-add  (update order :items conj (:item event))
    :paid      (assoc order :status :paid :paid-at (:at event))
    :shipped   (assoc order :status :shipped)))

;; 事件溯源：replay 历史事件重建任意状态
(defn replay [events]
  (reduce apply-event {:items []} events))

;; 版本化：保留每个快照，随时回滚
(def history (atom [{:order-id 42 :items [] :status :new}]))
(defn transition! [f]
  (swap! history (fn [h] (conj h (f (last h))))))   ;; 新版本追加，旧版本不丢

心法：事件溯源 + 不可变 = 「天然可回滚、可审计、可重放」——每次状态变更产生新版本，旧版本永不被破坏，replay 能用事件历史重建任意时刻状态。这是不可变结构共享在业务建模上的高价值用法。

10. 速查表与一句话记忆

一句话记忆：Clojure 不可变数据结构 = 持久化（修改出新值、旧值保留）+ 结构共享（分支 32 的矮树 / HAMT，只复制修改路径、其余引用共享 → O(log32 n) ≈ O(1)）——vector 按树下标、hash-map 按哈希寻址、sorted 才是红黑树（能不用就不用）；批量构建用 transient（构建期可变 O(1)、结束 persistent! 冻结、绝不逃逸）；不可变的并发红利是「数据不变 → 竞态只剩引用切换」，交给 atom/ref 即可；性能陷阱几乎都是结构选型错（list 当数组、反复整份改、滥用 sorted）——先选对结构，再用 criterium 实测。

延伸阅读

• Clojure 性能优化与 GraalVM 原生编译 — 类型提示与 criterium 基准
• Clojure 数据操作 — 序列与数据结构操作
• Clojure Transducers 深度解析 — 高效数据处理管线
• Clojure 函数式设计模式 — 不可变与纯函数的模式
• Rust 专题 — 所有权与不可变对比
• 系统架构专题 — 事件溯源与不可变数据