持久化数据结构：路径复制、节点复制与宽分支 trie

“保留每一个历史版本”听上去意味着每次修改都要整体复制。实际上，一棵 \(2^{20}\) 个键的持久化 AVL 树插入一个键，只新增约 21 个节点；一个 \(2^{20}\) 个元素的 32 路持久化向量改一个元素，只新分配 1056 字节，而整份数组是 8 MiB（第二节、第五节的实测）。关于这类结构，流传着几种不准确的说法：Clojure 的向量”就是 HAMT”；32 路分支让更新”实际上是 \(O(1)\)“；Driscoll 等人证明了”胖节点只要 \(O(1)\) 均摊空间”；Git “就是路径复制”。每一句都有一部分对。

本文按”定义 → 路径复制 → DSST 的通用变换 → 纯函数式实现与均摊分析 → 宽分支 trie → HAMT/CHAMP → Git → 工程问题 → 争论”的顺序展开。数字来自同目录 reproduce/ 下的程序，源码以 Clojure 1.12.6、Scala 2.13.18 为准。同主题的旧文 记录历史：持久化数据结构 详细推演过节点复制在链表上的例子，本文不重复。

一、定义：部分、完全与汇合持久化

普通数据结构是短暂的（ephemeral）：一次修改破坏旧版本，只留下新版本。Driscoll、Sarnak、Sleator 和 Tarjan（下文简称 DSST）在 1989 年的 JCSS 论文里给出了沿用至今的定义：

• 部分持久化（partial persistence）：所有版本都能读，只有最新版本能改；
• 完全持久化（full persistence）：任何版本都能读、都能改；
• 论文第 6 节把”用两个以上旧版本组合出新版本”（例如拼接两个列表）列为开放问题 (ii)。后来这种能力被称为汇合持久化（confluent persistence），Driscoll、Sleator、Tarjan（JACM 1994）的可拼接持久化列表和 Fiat、Kaplan（J. Algorithms 2003）的通用变换是这条线上的代表工作。

三者的区别在版本图的形状上：

• 部分持久化的版本是全序的，版本号可以直接用整数比较，查旧版本时”找不超过 \(v\) 的最大时间戳”就够了。
• 完全持久化的版本是一棵树，两个版本可能不可比较。DSST 用版本树的先序列表加上顺序维护结构（order maintenance，Dietz & Sleator，STOC 1987）来比较版本先后。
• 汇合持久化的版本图是 DAG，一个版本可以有两个父版本。难点在于合并后逻辑规模可以指数增长：把一个长度为 \(n\) 的列表与自身拼接 \(k\) 次，得到长度 \(2^k n\) 的列表，只能靠共享才能用多项式空间表示。

函数式语言里常说的纯函数式数据结构（purely functional data structure）是一种实现约束：节点一旦构造就不再修改。满足这个约束的结构自动是完全持久化的；如果操作本身接受两个结构作参数（比如拼接），也就自然支持汇合式的使用，但代价界要单独分析。

二、路径复制：复制搜索路径

机制

路径复制（path copying）是最直接的做法：修改一个节点时，把从根到它的整条路径复制一遍，路径之外的子树直接共享。DSST 第 4 节把这种方法归于 Myers（“AVL dags”，1982；POPL 1984）、Krijnen 与 Meertens、Reps、Teitelbaum 与 Demers，以及 Swart 的独立工作，并不是 DSST 自己提出的。

图里的 v1 由 4 个新节点组成：3 个路径副本加 1 个新叶子。20’ 的左子树、30’ 的右子树都是 v0 中原有的节点。v0 的任何节点都没有被写过，所以读 v0 的线程不需要加锁，也看不到”改了一半”的状态。

对平衡树，旋转只涉及路径上的节点和它们的兄弟，所以每次更新新增 \(O(\log n)\) 个节点。下面是 reproduce/pavl.c 中插入与再平衡的核心部分（省略了引用计数的定义和删除）。每个返回 Node * 的函数都返回一个”自有引用”，与旧版本共享的子树用 retain() 加一次引用计数：

/* reproduce/pavl.c：持久化 AVL 的插入，节选 */
static Node *balance(int key, Node *l, Node *r)   /* takes ownership of l, r */
{
    int hl = height(l), hr = height(r);
    if (hl > hr + 1) {
        Node *res;
        if (height(l->left) >= height(l->right)) {       /* single right rotation */
            res = mk(l->key, retain(l->left), mk(key, retain(l->right), r));
        } else {                                          /* left-right */
            Node *lr = l->right;
            res = mk(lr->key, mk(l->key, retain(l->left), retain(lr->left)),
                     mk(key, retain(lr->right), r));
        }
        release(l);
        return res;
    }
    /* hr > hl + 1 is symmetric */
    ...
    return mk(key, l, r);
}

static Node *ins(const Node *t, int key)
{
    if (!t) return mk(key, NULL, NULL);
    if (key < t->key) return balance(t->key, ins(t->left, key), retain(t->right));
    return balance(t->key, retain(t->left), ins(t->right, key));
}

旋转时原先的 l 往往是这次刚复制出来的节点，release(l) 会立刻释放它，所以”分配的节点数”略多于”新版本实际保留的节点数”。

实测：每次更新新增多少节点

实验环境（本文所有自测数据相同）：Intel Core i9-12900K，WSL2 内核 6.6.87.2，GCC 16.1.1，Python 3.14.5。pavl measure 先按随机顺序插入 \(n\) 个偶数键，再在这个基础版本上各做 20,000 次”插入一个不存在的奇数键”和”删除一个存在的键”，每次操作后立即释放新版本。计数与时钟无关，固定种子下重复运行输出逐字节一致。

每次插入保留的节点数约为 \(\log_2 n + 1.3\)，与一条从根到插入点的路径长度相当。插入引起的旋转只重排路径上已经复制过的节点，不增加副本；删除引起的旋转发生在另一侧，要额外复制兄弟节点；但被删节点本身不再出现在新版本里，插入则要多出一个新叶子，所以删除保留的节点反而比插入少约 1.7 个。pavl.c 中每个节点 32 字节，\(n = 2^{20}\) 时一个新版本约多占 \(21.36 \times 32 \approx 684\) 字节。

pavl test 做了另一件事：从 4000 个版本里随机挑一个旧版本继续插入或删除（完全持久化的用法），所有版本一直保留，最后逐个版本、逐个键与朴素的位图副本对照，共 8,192,000 次成员查询全部一致；随后释放所有版本，存活节点数回到 0。编译参数为 -O2 -Wall -Wextra，另用 -fsanitize=address,undefined 跑过一遍。

路径复制的前提

路径复制要求”从根能走到每个节点，且路径唯一”。有父指针的结构不适用：改一个叶子，就要改它父亲的子指针，而父亲又被所有孩子的父指针指着，复制会沿父指针扩散到整棵树。双向链表、带父指针的红黑树（例如 Linux rbtree 的 __rb_parent_color）都属于这种情况，要么改写成不带父指针的递归版本，要么换用下一节的节点复制。

三、DSST 1989：胖节点、节点复制与节点分裂

DSST 的目标是一个通用变换：给定任意链式（pointer-based）短暂结构，把它的每一步访问和修改模拟到一个持久化结构上，理想情况下每个更新步只多花 \(O(1)\) 空间，每个访问步只慢常数倍。论文给出三种方法，前两种见下图：

胖节点

胖节点（fat node）方法让每个节点保存每个字段的全部历史取值，每个取值带一个版本戳。修改不覆盖旧值，只追加一条记录；读版本 \(i\) 的字段时，取版本戳不超过 \(i\) 的最新记录。

• 每个更新步只追加一条记录，最坏情况 \(O(1)\) 空间（不是均摊）；
• 每个字段的记录按版本戳放在一棵搜索树里，每个访问步和更新步要 \(O(\log m)\) 时间，\(m\) 是更新次数（DSST 第 2.2 节）；
• 适用于任何链式结构；做完全持久化时，版本戳之间要用版本树的顺序比较，界不变（第 3.2 节）。

代价是对数级的访问减速，以及”节点大小不固定”：胖节点在实现上要拆成若干固定大小节点的链表。

节点复制

节点复制（node copying）去掉了这两个缺点，前提是短暂结构中每个节点的入度有常数上界 \(p\)（任一版本中指向它的指针不超过 \(p\) 个）。设节点有 \(d\) 个指针字段，每个持久化节点有 \(d + p + e + 1\) 个指针槽位：\(d\) 个原始字段，\(p\) 个逆指针（记录谁指向自己），\(e\) 个带版本戳的额外槽位，1 个指向自己副本的 copy 指针（论文第 2.3.1 节）。

修改指针字段时，如果节点还有空的额外槽位，就把”字段名、版本戳、新值”写进去；槽位满了，就复制出一个只含最新值的新节点，并通过逆指针找到所有前驱，在前驱里记下指向新副本的指针。前驱的额外槽位也可能满了，于是复制会级联。

级联复制为什么只摊到 \(O(1)\)？DSST 取势函数

\[ \Phi = \frac{e}{e-p+1}\, L \;-\; \frac{1}{e-p+1}\, U, \]

其中 \(L\) 是存活节点数，\(U\) 是存活节点中空闲额外槽位的总数。复制一个节点，满节点死去、新节点槽位全空，势能下降 \(\frac{e}{e-p+1}\)；往额外槽位里写一个指针，势能上升 \(\frac{1}{e-p+1}\)。一次更新操作开始级联时有 \(t\) 个待处理的已复制节点，级联中又复制了 \(k\) 个，每个被处理的节点最多往前驱写 \(p\) 个指针，其中至少 \(k\) 个写进了新副本的原始字段而不占额外槽位。于是级联阶段的均摊空间为

\[ k + \frac{p(t+k) - k}{e-p+1} - \frac{k\,e}{e-p+1} = \frac{p\,t}{e-p+1} = O(t), \]

\(k\) 被完全抵消。只要取 \(e \ge p\)，每个更新步的均摊时间和空间都是 \(O(1)\)，每个访问步是最坏 \(O(1)\)（论文第 2.3.4 节）。

节点分裂与平衡树

完全持久化下，一个节点的修改记录属于版本树的不同分支，不能简单地”复制最新值”。DSST 第 3.3 节的节点分裂（node splitting）借鉴了 B 树的分裂：节点溢出时，按版本树把记录分成两半放进两个节点。结论与节点复制相同：入度有界时，每个更新步均摊 \(O(1)\) 时间与空间，每个访问步最坏 \(O(1)\)。

把这些方法用到红黑树上，关键在于红黑树的一次插入最多两次旋转、一次删除最多三次旋转，重新着色的均摊次数是 \(O(1)\)；搜索路径上的节点只被访问，不被修改。DSST 第 4.1 节的部分持久化红黑树只给每个节点一个额外指针（\(e = 1\)）；由于每个节点只有一条访问路径，连逆指针都不需要；颜色不参与访问，旧颜色可以直接覆盖。结果是每次插入或删除最坏 \(O(\log n)\) 时间，\(m\) 次更新共 \(O(m)\) 空间。

完全持久化时出现了一个与第四节同源的问题：重新着色只是均摊 \(O(1)\)，而同一个旧版本可以被反复更新，均摊不再成立，节点分裂需要的是每次更新最坏 \(O(1)\) 次修改。第 4.2 节借用 Tsakalidis 的延迟重新着色（lazy recoloring）满足了这一点，得到均摊 \(O(1)\) 空间的完全持久化红黑树；第 5 节再用”位移存储”（displaced storage）把空间界改成最坏 \(O(1)\)。论文明确对比：路径复制每次插入或删除最坏需要 \(O(\log n)\) 空间，他们的方法”节省了一个对数因子”。

最后一行回答了 DSST 开放问题 (i) 的部分持久化情形：Brodal 用 Dietz 和 Raman 的双人卵石博弈策略，把节点复制的更新代价从均摊 \(O(1)\) 改进为指针机模型下的最坏 \(O(1)\)。

部分持久化最早的杀手级应用是平面点定位。Sarnak 和 Tarjan（CACM 1986）用一条竖直扫描线从左到右扫过平面剖分，扫描线与线段的上下顺序存在一棵搜索树里，每经过一个端点就在最新版本上插入或删除一条线段；查询点 \((x, y)\) 时，先按 \(x\) 找到对应版本，再在该版本里按 \(y\) 查找。用 \(O(1)\) 均摊空间的持久化搜索树，得到 \(O(\log n)\) 查询、\(O(n)\) 空间、\(O(n \log n)\) 预处理。站内 线段树与树状数组 第九节的选型表把”查询历史版本”交给可持久化线段树，它就是对线段树做路径复制：每次单点修改复制根到叶的 \(O(\log n)\) 个节点。

四、纯函数式实现：Okasaki 与持久化下的均摊

不修改节点，持久化自动成立

在 Haskell、ML 这类语言里，构造器只能新建节点，不能改写已有节点，路径复制是语言的默认行为。Okasaki 在 JFP 1999 的函数式珍珠（Functional Pearl）“Red-black trees in a functional setting” 中把红黑树插入的四种失衡情况合并成一个 balance 函数。下面的 Haskell 片段按论文整理，本站没有编译运行：

data Color = R | B
data Tree a = E | T Color (Tree a) a (Tree a)

balance :: Color -> Tree a -> a -> Tree a -> Tree a
balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance color a x b = T color a x b

模式匹配右侧的每个 T 都是一次新节点分配，左侧匹配到的子树 a、b、c、d 原样共享，这就是路径复制。删除要难得多，Okasaki 的珍珠没有给出；Kahrs（JFP 2001）给出了带类型不变量的删除，Germane 和 Might（JFP 2014）的 “Deletion: The curse of the red-black tree” 用临时的”双黑”颜色给出了另一种写法。

均摊分析在持久化下失效

均摊界假设操作序列是线性的：昂贵操作的代价由之前的廉价操作”预付”。持久化打破了这个假设，同一个旧版本可以被反复使用，预付的钱只能花一次，昂贵操作却可以执行很多次。

经典例子是两个列表实现的批量队列（batched queue）：前端列表 \(f\) 出队，后端列表 \(r\) 入队，\(f\) 空时把 \(r\) 翻转成新的 \(f\)。短暂使用时每次操作均摊 \(O(1)\)。持久化使用时，构造一个”\(f\) 只剩一个元素、\(r\) 有 \(n-1\) 个元素”的版本，然后对同一个版本反复出队，每次都要重新翻转 \(r\)。

reproduce/queue_amort.py 用抽象步数计量（新建一个 cons 单元或求值一个挂起计算记 1 步），\(n = 100{,}000\)：

批量队列在短暂使用下每次操作平均 1 步，符合均摊 \(O(1)\)；换成持久化用法后，1000 次出队花了 \(1000 \times (n-1)\) 步。\(n = 1000\)、\(10{,}000\) 的结果规律相同，见 reproduce/results/queue_amort.txt。

惰性求值与调度

Okasaki 的解决办法有两层。第一层是惰性求值加记忆化：把昂贵的翻转包成一个挂起计算（suspension），第一次求值后缓存结果。同一个旧版本被反复使用时，共享的是同一个挂起计算，翻转只真正执行一次，均摊界得以恢复。他的书用”借记”（debit）而不是”信用”（credit）来做这类分析：只要证明每个挂起计算在被强制求值之前，其代价已经分摊到足够多的操作上。

第二层是把均摊界变成最坏界：实时队列（Okasaki，JFP 1995）。它把 \(f\) 做成惰性流，维护一个指向 \(f\) 内部的指针 \(s\)，每次操作顺手强制求值 \(s\) 的一个单元，不变量是 \(|s| = |f| - |r|\)。当 \(s\) 走到头，恰好 \(|r| = |f| + 1\)，此时启动一次惰性的 rotate，把 “\(f\) 接上 \(r\) 的逆序” 表示成逐单元求值的流。Hood 和 Melville（IPL 1981）更早给出过纯 Lisp 的实时队列，用的是显式的增量翻转；Okasaki 的版本靠惰性求值把这套簿记隐藏起来。复现程序中的核心部分如下：

# reproduce/queue_amort.py：Okasaki 实时队列，节选
def rotate(f, r, a):
    """lazy f ++ reverse r ++ a, one step per forced cell; requires |r| = |f| + 1"""
    def step():
        tick()
        fv = f.force()
        y, r2 = r
        if fv is None:
            return (y, a)
        x, f2 = fv
        return (x, rotate(f2, r2, Susp(val=(y, a), done=True)))
    return Susp(step)


def rq_exec(f, r, s):
    sv = s.force()                 # pay for one suspended step
    if sv is not None:
        return (f, r, sv[1])
    f2 = rotate(f, r, NIL)         # |r| = |f| + 1: start a new rotation
    return (f2, None, f2)

上表里实时队列单次操作最多 2 步，与版本如何被复用无关；持久化出队 1000 次总共 0 步（\(n = 10{,}000\) 时是 1 步），是因为构造这个版本的过程中 \(f\) 的首个单元通常已经被 \(s\) 求值过，之后只是读缓存；即使没有，也只在第一次出队时求值一次，其余 999 次共享记忆化的结果。两种队列都通过了随机持久化用法的对照测试：20,000 次操作各自随机挑一个旧版本入队或出队，与 Python deque 副本逐一比较。

同一思路推到更复杂的结构，Kaplan 和 Tarjan（JACM 1999）用”递归减速”（recursive slow-down）得到了纯函数式、支持拼接、所有操作最坏 \(O(1)\) 的双端队列。

五、宽分支 trie：Clojure 的 PersistentVector

结构

二叉树上的路径复制每次要复制约 \(\log_2 n\) 个节点，读一个元素也要走 \(\log_2 n\) 步指针。Clojure 的 PersistentVector 把分支因子加大到 32：它是一棵按下标的二进制位切分的 trie（bit-partitioned trie），每层消耗下标的 5 位。它不是 HAMT，里面没有哈希，HAMT 是 PersistentHashMap 的结构（第六节）。clojure.org 的数据结构文档对复杂度的表述是”access to items by index in log32N hops”。

以 Clojure 1.12.6 的 src/jvm/clojure/lang/PersistentVector.java 为准，一个向量由四个字段组成：元素个数 cnt、根所在层的位移 shift、根节点 root、以及单独存放的尾数组 tail。内部节点 Node 就是一个 32 格的 Object[] 加一个 edit 标记（transient 用，见下文）。空向量的 shift 是 5。

• tailoff() 是 tail 之前的元素个数，等于 ((cnt - 1) >>> 5) << 5。图中 \(\mathrm{tailoff} = 1088\)，下标不小于它的元素直接在 tail 里，不走树。
• 下标 \(i\) 在第 level 层的槽位是 (i >>> level) & 0x1f，level 从 shift 每次减 5 直到 0。\(1000 = 00000\,11111\,01000_2\)，所以路径是 0、31、8。
• 根只有在装满时才长高：cons 里的判断是 (cnt >>> 5) > (1 << shift)，此时新建一个根，旧根放进 0 号槽，1 号槽挂一条新路径。

查找与更新的源码（Clojure 1.12.6，PersistentVector.java，未删减）：

final int tailoff(){
    if(cnt < 32)
        return 0;
    return ((cnt - 1) >>> 5) << 5;
}

public Object[] arrayFor(int i){
    if(i >= 0 && i < cnt)
        {
        if(i >= tailoff())
            return tail;
        Node node = root;
        for(int level = shift; level > 0; level -= 5)
            node = (Node) node.array[(i >>> level) & 0x01f];
        return node.array;
        }
    throw new IndexOutOfBoundsException();
}

private static Node doAssoc(int level, Node node, int i, Object val){
    Node ret = new Node(node.edit,node.array.clone());
    if(level == 0)
        {
        ret.array[i & 0x01f] = val;
        }
    else
        {
        int subidx = (i >>> level) & 0x01f;
        ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
        }
    return ret;
}

doAssoc 就是第二节的路径复制，每层 clone() 一个 32 格数组。

“实际上是常数”的真实含义

树高是 \(\lceil \log_{32} n \rceil\) 量级，不是常数。它看上去像常数，是因为 Java 的下标是 32 位 int：\(32^6 = 2^{30} \approx 1.07 \times 10^9\)，所以 10 亿个元素的向量有 6 层，int 能表示的最大向量也只需要 7 层。每次 assocN 复制的是”层数 \(\times\) 32 个引用”，这是 \(O(\log n)\) 乘上一个不小的常数。

tail 与追加

持久化的 cons（追加）有两种情况：

1. tail 未满（cnt - tailoff() < 32）：新建一个长度加 1 的数组，把旧 tail 整个复制过去再写入新元素。持久化版本每次追加都复制 tail，不是”在 tail 末尾写一格”。
2. tail 已满：旧 tail 原样变成一个叶子，由 pushTail 复制最右侧路径挂进树里；新 tail 是只含新元素的 1 格数组。

所以追加 32 个元素要复制 \(1 + 2 + \cdots + 32 = 528\) 个引用，外加一次最右路径复制。tail 的好处是不碰树：31/32 的追加只分配一个小数组，而且最近追加的元素读取时不用走树。

“在 tail 末尾原地写一格”是 TransientVector 的行为。(transient v) 生成一个带新 edit 令牌的可变视图：conj 直接写 32 格的 tail，ensureEditable(node) 只在节点的 edit 不是自己的令牌时才克隆，于是同一个 transient 内的连续修改不会反复复制同一个节点；persistent! 把令牌置空，此后再修改该 transient 会抛 IllegalAccessError，并把 tail 裁剪到实际长度。1.12.6 的 persistent() 里，检查调用线程是否为所有者的代码已被注释掉。

实测：分支因子的取舍

reproduce/pvec.c 按 Clojure 的布局实现了同样的 trie（含 tail、pushTail、根溢出），但分支因子 \(W = 2^B\) 可调。节点大小为 8 字节头加 \(W\) 个 8 字节槽，tail 按实际长度分配。\(n = 2^{20}\) 个 8 字节元素，整份数组是 8,388,608 字节：

每次 assoc 的字节数严格等于”层数 \(\times (8 + 8W)\)“，例如 \(W = 32\) 时 \(4 \times 264 = 1056\)。更新代价的最小值在 \(W = 4\)，\(W = 32\) 是它的 2.6 倍；但 \(W = 32\) 的整体空间开销只有 6.5%（8.52 字节存一个 8 字节元素），\(W = 2\) 要 3 倍。追加的平均代价在 \(W = 8\) 最低，\(W = 32\) 时主要花在 tail 的逐次复制上：每 32 次追加复制 528 个槽，约 \(528 \times 8 / 32 = 132\) 字节，再加上 tail 数组头和每 32 次一次的最右路径复制，与实测的 164.5 字节一致。

读的一侧用随机下标读 \(10^7\) 次计时，taskset -c 15 绑核，每次运行取 5 轮中位数，共独立运行 3 次。机器上同时有其他负载，同一配置在三次运行之间相差可达 2 倍，所以下图右侧只看趋势：

三次运行各自的中位数落在这些区间：\(W = 2\) 时 135 到 266 ns，\(W = 4\) 时 44 到 77 ns，\(W = 32\) 时 12 到 22 ns，\(W = 64\) 时 13 到 23 ns；同一数据放在连续数组里只要 1.7 到 2.7 ns。读延迟由层数决定，\(W\) 从 2 增到 32，层数从 20 降到 4，读快了约一个数量级；从 32 到 64，\(n = 2^{20}\) 时层数都是 4，读几乎不变，更新代价却翻倍。这组数据只在本机、本规模下成立，但它说明了为什么 32 是一个合理的折中：它接近”读已经不再明显变快、写还没有贵到不可接受”的拐点，而且 32 个引用的节点在 JVM 上正好是一个 int 位图能覆盖的宽度，这一点对下一节的 HAMT 更重要。

六、HAMT、CHAMP 与 RRB：哈希映射和可拼接向量

Bagwell 的 HAMT 本身不是持久化结构

Bagwell 2001 年的技术报告 “Ideal Hash Trees” 提出了 HAMT（Hash Array Mapped Trie）：把键的哈希值每 5 位一段，逐层作为 32 路 trie 的下标。每个节点用一个 32 位位图（bitmap）标记哪些分支存在，后面只存放存在的分支，第 \(k\) 个分支在压缩数组中的位置是位图中低于第 \(k\) 位的 1 的个数，用 CTPOP（population count）指令一步算出。报告描述的是一个可原地修改的哈希表替代品，顶层还有一个可扩容的根哈希表，全文没有讨论持久化。Clojure 的 PersistentHashMap 去掉了根表，让根也是一个 trie 节点，再用路径复制做更新，这才得到持久化的哈希映射。

Clojure 的 PersistentHashMap

Clojure 1.12.6 PersistentHashMap.java 中的关键实现：

static int mask(int hash, int shift){
    //return ((hash << shift) >>> 27);// & 0x01f;
    return (hash >>> shift) & 0x01f;
}

private static int bitpos(int hash, int shift){
    return 1 << mask(hash, shift);
}

/* inside final static class BitmapIndexedNode */
    final int index(int bit){
        return Integer.bitCount(bitmap & (bit - 1));
    }

• 哈希从低位开始消耗，每层 5 位，shift 从 0 开始；
• BitmapIndexedNode 的数组里键和值交错存放：array[2*idx] 是键，array[2*idx+1] 是值；键槽为 null 时，值槽放的是子节点；
• 节点里已有 16 个条目、还要再插入时，assoc 把它换成 ArrayNode：一个直接按 5 位分段下标寻址的 32 格子节点数组，不再需要位图；ArrayNode 在孩子数不超过 8 时再失去一个孩子，pack() 就把它压回 BitmapIndexedNode；
• 32 位哈希全部相同的键放进 HashCollisionNode，线性查找。

路径复制发生在 cloneAndSet() 与 new BitmapIndexedNode(null, bitmap, ...) 这几处：沿哈希路径的每个节点复制一次，每次复制的是压缩后的数组，平均比 32 格小。

CHAMP：两个位图与规范形式

Steindorfer 和 Vinju（OOPSLA 2015）的 CHAMP（Compressed Hash-Array Mapped Prefix-tree）针对的是 HAMT 在 JVM 上的两个弱点：迭代和相等比较。Clojure 式的节点里，键值和子节点交错存放，迭代时要逐格判断”这是值还是子节点”；删除后节点也可能留在”只有一个子节点”的非规范状态，两个内容相同的映射可能结构不同，相等比较就不能逐节点短路。CHAMP 的做法是：

• 用 dataMap 和 nodeMap 两个位图分别标记”这一位是键值”和”这一位是子节点”，数组里不再需要 null 占位；
• 键值集中在数组前部，子节点集中在后部，迭代时先顺序扫一段键值，再递归子节点；
• 删除后立即把树压缩成规范形式（canonical form），相同内容的映射有相同的结构。

论文报告（未在本站复现）：与 Scala 相比，映射内存占用减少 64%，集合的中位数减少 52%；与 Clojure 相比，映射中位数减少 15%、集合减少 31%；迭代快 1.3 到 6.7 倍，相等比较快 3 到 25.4 倍；查找、插入、删除的性能与 HAMT 持平。Scala 2.13 的 immutable.HashMap 采用了 CHAMP：2.13.18 的 HashMap.scala 文档注释写明 “Compressed Hash-Array Mapped Prefix-tree” 并引用了这篇论文，节点类 BitmapIndexedMapNode 的字段是 dataMap、nodeMap、content、originalHashes 等，子节点用 content(content.length - 1 - index) 从数组末尾取。Clojure 1.12.6 仍是交错布局。

Scala 的 Vector 与 RRB 树

Scala 的 immutable.Vector 也是宽度 32 的 trie，但 2.13.2 起是一份全新实现（Stefan Zeiger，PR #8534，2020 年 3 月合入）。2.13.18 Vector.scala 的文档注释说它是 “radix-balanced finger trees of width 32”：为每个高度（0 到 6）各定义一个子类，两端各有一组固定的”手指”（prefix1、suffix1 等切片），前插只动前缀、追加只动后缀；注释给出的复杂度是随机访问与更新 \(O(\log n)\)，前插、追加、tail、init 均摊 \(O(1)\)、最坏 \(O(\log n)\)。

这两种向量里只有靠近两端的节点可以不满，其余节点都是满的，所以下标可以纯靠移位计算。代价是拼接和切片：两个向量拼接时，一方的元素要按另一方的对齐方式重新排布，代价与该向量的长度成正比。RRB 树（Relaxed Radix Balanced tree，Bagwell & Rompf，EPFL 技术报告 2011）放松了这一条：允许节点不满，不满的节点额外带一个累计大小表，查找时在这个节点里先按大小表定位，再继续移位；换来的是 \(O(\log n)\) 的拼接与切片。Stucki、Rompf、Ureche、Bagwell（ICFP 2015）给出了 Scala 上的完整实现与评测；Puente（ICFP 2017）的 C++ 库 immer 实现了 RRB 向量，论文摘要把它概括为”有效常数时间的查找与更新、对数时间的拼接与切片”。

Scala 标准库没有采用 RRB。Zeiger 在 PR #8534 的说明里写得很直接：新 Vector 和旧 Vector 一样”does not use a relaxed radix-balanced tree”，他的目标是做一个”不在任何操作上做性能妥协”的旧 Vector 替代品。这一取舍在第九节再讨论。

七、Git 的对象模型：同构与差异

Git 仓库里有四类对象：blob（文件内容，不含文件名）、tree（目录：文件名、模式、指向 blob 或子 tree 的对象 ID）、commit（指向一个根 tree、零到多个父 commit，以及作者信息）和附注 tag。对象 ID 是对象内容的哈希，默认 SHA-1；git init --object-format=sha256 可以建 SHA-256 仓库，git-init 文档注明两种仓库之间目前不能互操作（Git 2.54.0）。

reproduce/git_path_copy.sh 建一个有 README.md、Makefile、src/main.c、src/util.c 的仓库，提交 A；只改 src/main.c，提交 B。作者和时间固定，所以对象 ID 可复现。以下是实际输出：

objects after A: 7
objects after B: 11
$ git cat-file -p HEAD
tree 235c86d6daeb5e595663b781fe4ab476a9c379ad
parent 16510ce2fabbc24ceaf4c0ef159830c7de36b630
author demo <demo@example.com> 1767225600 +0000
committer demo <demo@example.com> 1767225600 +0000

B
$ git ls-tree -r -t HEAD~1
100644 blob 1263948fb882b8c4fd639b01e17969c825e79619    Makefile
100644 blob fc72a5c1094e203eefcd1c710f060957ebbbaac4    README.md
040000 tree 6ad4892865f47712e87eaf04559b4af8d8bccec2    src
100644 blob f7e582f82533be28c5813e8ea91918eb7fa61cdc    src/main.c
100644 blob 3baf3842041c30efe6be70e87bfa7399b6ea436f    src/util.c
$ git ls-tree -r -t HEAD
100644 blob 1263948fb882b8c4fd639b01e17969c825e79619    Makefile
100644 blob fc72a5c1094e203eefcd1c710f060957ebbbaac4    README.md
040000 tree c2d7ba62b08ae9d63a6f53d4b59d40f90ac5d4e4    src
100644 blob 7424aad076a63f3b6196bd24229e2eeca2fb70ae    src/main.c
100644 blob 3baf3842041c30efe6be70e87bfa7399b6ea436f    src/util.c

同构的部分：把目录树看成一棵以路径分量为边的树，提交 B 新增的恰好是”被改文件 + 它到根的每一层目录 + 一个 commit”，即 \(1 + 2 + 1 = 4\) 个对象，从 7 个变成 11 个。这就是路径复制：复制路径，共享其余子树，旧版本一个字节都没动。

不同的部分，至少有四处：

1. 按内容共享，而不只是按”没改过”共享。 路径复制只共享这次没碰到的子树；两次独立构造出的相同子树在内存里是两份。Git 的对象 ID 就是内容哈希，任何位置、任何提交里内容相同的文件或目录都是同一个对象，相当于对整个版本集合做了哈希合并（hash-consing）。这也让每个 tree 和 commit 的 ID 承诺了其下的全部内容，是一种 Merkle DAG，见站内 Merkle 树与认证数据结构。
2. 版本图是 DAG。 合并提交有多个父提交，版本图的形状与汇合持久化一样；但 Git 的”合并”是先用三方合并在内容层面算出结果，再把结果作为一个新快照存下来，数据结构本身没有提供带复杂度保证的合并操作。Demaine、Langerman、Price（Algorithmica 2010）的 “Confluently Persistent Tries for Efficient Version Control” 研究的正是如何让这种合并在数据结构层面也高效。
3. 逻辑上是快照，物理上可能是增量。 对象模型里每个 blob 都是完整内容；打包（packfile）时 Git 会把相似对象存成 OFS_DELTA / REF_DELTA 增量。这是存储层的压缩，与持久化的逻辑模型无关。
4. 回收靠可达性。 不再被任何引用（分支、tag、reflog）可达的对象由 git gc 清理，相当于对版本集合做追踪式垃圾回收；内存中的持久化结构在无 GC 的语言里只能靠引用计数（第八节）。

八、工程问题：回收、批量构建与并发

没有 GC 时怎么回收

结构共享意味着一个节点可能属于任意多个版本，“释放某个版本”不能递归 free 整棵树。reproduce/pavl.c 用引用计数：每个版本持有根的一个引用，复制节点时对共享的子树 retain()，释放版本时 release() 沿计数归零的节点向下走。这样做有两个工程细节：

• 释放一个大版本的最后一个引用，会在当前调用里释放整棵树，时间与规模成正比。pavl.c 的 release() 对右孩子用循环、只对左孩子递归，以免退化成长链时栈溢出。
• 计数本身是共享可变状态。多线程共享版本时要用原子计数（Rust 的 Arc、C++ 的 std::shared_ptr），每次 retain/release 都是一次原子读改写。

用 arena 分配、所有版本用完后整体释放，只适用于版本同生共死的场景：只要某个旧版本比新版本活得久，arena 就无法单独回收新版本。

引用计数还带来一个优化机会：计数为 1 时，说明没有别的版本能看到这个节点，可以原地修改而不复制。Rust 标准库的 Rc::make_mut 就是这样：只有存在其他 Rc 指向同一分配时才克隆内部值（文档称为 clone-on-write）。Puente（ICFP 2017）的 immer 把这一点做成了 C++ 的”transient”：用移动语义和引用计数判断独占，独占时原地更新。

批量构建要用 transient 或 builder

第五节的表里，\(W = 32\) 时逐个追加平均每个元素分配 164.5 字节，而元素本身只有 8 字节，这些中间版本随即成为垃圾。批量构建时应当用可变的构建器：Clojure 的 (persistent! (reduce conj! (transient []) xs))，PersistentVector.create 内部也是这么做的；Scala 的 Vector.newBuilder。它们在构建期间原地写，结束时一次性”冻结”成持久化版本。

并发：快照读免锁，写靠 CAS 重试

Clojure 的 atom 持有一个指向不可变值的引用。swap! 的实现（1.12.6 Atom.java，未删减）：

public Object swap(IFn f) {
    for(; ;)
        {
        Object v = deref();
        Object newv = f.invoke(v);
        validate(newv);
        if(state.compareAndSet(v, newv))
            {
            notifyWatches(v, newv);
            return newv;
            }
        }
}

读者 deref 拿到的是某个完整版本，永远不会看到”改了一半”的状态，也不需要锁。写者用持久化更新算出新版本，再用 CAS 发布；CAS 失败就用最新值重算。所以传给 swap! 的函数可能执行多次，必须没有副作用；写竞争激烈时，重算的持久化更新本身就是浪费的分配。

常见问题

九、争论与开放问题

争论一：均摊 \(O(1)\) 空间的通用变换为什么没有进入生产库

DSST 证明节点复制比路径复制省一个对数因子的空间，Brodal 进一步做到最坏 \(O(1)\)。但 Clojure、Scala 的集合和 Haskell containers（0.8 的 Data.Map 基于 Adams 的大小平衡树，Data.Sequence 基于 Hinze–Paterson 的 2-3 finger tree）都用路径复制或纯函数式构造。下面是本文的工程判断，依据是 DSST 第 2.3.2 节对更新过程的描述：

• 节点复制要写入已有节点：往旧节点的额外槽位里记新指针，维护逆指针。旧版本在物理上不再是只读的，并发读者需要同步，纯函数式语言里也无法表达。DSST 第 6 节给出过”除访问指针外只写一次”（write-once）的变体，写入次数有界，但写入依然发生在共享节点上。
• 它要求入度有常数上界并维护逆指针，而路径复制对树形结构什么都不要求。
• 宽分支让”省下的对数因子”变小：\(W = 32\)、\(n = 2^{20}\) 时路径只有 4 层，节点复制要付出的是每个节点 \(p + e + 1\) 个额外槽位和版本戳。

纯函数式到底要付多少代价，理论上有两方面的结果。DSST 第 6 节指出，节点复制可以改成除访问指针外只写一次，由此任何入度有常数上界、用 rplaca/rplacd 构造的结构，都能只用 cons、car、cdr 在线性时间内模拟。另一方面，Pippenger（POPL 1996）构造了一个在线问题，允许修改的 Lisp 能在 \(O(n)\) 时间内解决，而任何严格求值的纯 Lisp 程序都需要 \(\Omega(n \log n)\)。DSST 的模拟只覆盖入度有常数上界的结构，与这个下界并不冲突。Bird、Jones、de Moor（JFP 1997）随后指出，在惰性求值下，同一问题可以在 \(O(n)\) 内解决，下界并不适用于惰性语言。这与第四节 Okasaki 的结论一致，惰性求值和记忆化本身就是一种受控的”修改”。

争论二：要不要放松平衡

RRB 一派（Bagwell & Rompf 2011；Stucki 等 2015；Puente 2017）认为，可拼接、可切片是通用不可变序列的基本能力，值得为不满的节点付出大小表的查找开销；immer 与 Clojure 的独立库 core.rrb-vector 都实现了 RRB 向量。Scala 2.13 的 Vector 重写选择了另一条路：保持严格的 radix-balanced 结构，用两端的手指把前插、追加做到均摊 \(O(1)\)，目标是不在任何已有操作上变慢。两种选择的评测都来自各自作者，面向的负载也不同，本站没有做交叉对比。

争论三：哈希 trie 的节点布局

CHAMP 论文报告的迭代与相等比较提速来自两点：键值与子节点分区存放，以及删除后维持规范形式。Scala 2.13 采纳了它，Clojure 1.12.6 仍是交错布局加 ArrayNode。这类差异只影响常数，但对”把大映射当作值来比较、来遍历”的程序（论文的例子是不动点迭代的程序分析）影响很大；论文中这类程序的端到端加速是 9.9 到 28.1 倍。

开放问题

• 完全持久化的最坏 \(O(1)\)。 DSST 开放问题 (i) 要求把每个更新步的 \(O(1)\) 从均摊改成最坏。Brodal 解决了部分持久化的情形；MIT 6.851（Demaine，2021 春）第 1 讲的课程页面把完全持久化的版本列为仍然开放。它的实际意义在于延迟敏感的系统：均摊界允许偶发的长级联复制。
• 汇合持久化的通用变换。 Fiat 和 Kaplan（2003）给出每次操作 \(O(e(v))\) 的通用变换，其中 \(e(v) = 1 + \log(\text{从根到 } v \text{ 的路径数})\)，衡量版本 DAG 偏离树的程度；Collette、Iacono、Langerman（SODA 2012）对只合并互不共享节点的版本（disjoint）这一情形做到 \(O(\log n)\)。6.851 的课程页面写明，一般情形下每次操作 \(O(\log n)\) 或更低的代价仍是开放问题。版本控制系统里的合并就是这种操作。
• 无界入度。 DSST 开放问题 (iv)：入度无界时节点复制与节点分裂完全失效，只剩胖节点，访问要多付 \(O(\log m)\)。一般图结构的持久化至今没有常数因子开销的通用方法。

十、参考资料

源码与文档

• Clojure 1.12.6：src/jvm/clojure/lang/PersistentVector.java（tailoff、arrayFor、assocN、doAssoc、cons、pushTail、TransientVector）、PersistentHashMap.java（mask、bitpos、BitmapIndexedNode、ArrayNode、HashCollisionNode）、Atom.java（swap）。
• Clojure 官方文档：Data Structures，clojure.org/reference/data_structures。
• Scala 2.13.18：src/library/scala/collection/immutable/Vector.scala、HashMap.scala（BitmapIndexedMapNode）、ChampCommon.scala；scala/scala PR #8534 “Rewrite Vector (now radix-balanced finger tree vectors), for performance”，Scala 2.13.2 发布说明。
• Haskell containers 0.8：Data.Map.Strict、Data.Sequence 模块文档。
• Git 2.54.0：git-init（--object-format）文档；pack 格式文档中的 OFS_DELTA / REF_DELTA。
• Rust 标准库文档：std::rc::Rc::make_mut。

核心论文

• J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan, “Making Data Structures Persistent”, Journal of Computer and System Sciences 38(1): 86–124, 1989（初版 STOC 1986）。
• N. Sarnak, R. E. Tarjan, “Planar Point Location Using Persistent Search Trees”, CACM 29(7): 669–679, 1986.
• C. Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998.
• P. Bagwell, “Ideal Hash Trees”, EPFL Technical Report, 2001.
• M. J. Steindorfer, J. J. Vinju, “Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections”, OOPSLA 2015.
• N. Stucki, T. Rompf, V. Ureche, P. Bagwell, “RRB Vector: A Practical General Purpose Immutable Sequence”, ICFP 2015.
• A. Fiat, H. Kaplan, “Making Data Structures Confluently Persistent”, Journal of Algorithms 48(1): 16–58, 2003.

其他论文

• E. W. Myers, “Efficient Applicative Data Types”, POPL 1984.
• P. Dietz, D. Sleator, “Two Algorithms for Maintaining Order in a List”, STOC 1987.
• G. S. Brodal, “Partially Persistent Data Structures of Bounded Degree with Constant Update Time”, BRICS Report RS-94-35, 1994；期刊版 Nordic Journal of Computing 3(3), 1996.
• J. R. Driscoll, D. D. Sleator, R. E. Tarjan, “Fully Persistent Lists with Catenation”, JACM 41(5): 943–959, 1994.
• R. Hood, R. Melville, “Real-Time Queue Operations in Pure LISP”, Information Processing Letters 13(2): 50–54, 1981.
• C. Okasaki, “Simple and Efficient Purely Functional Queues and Deques”, Journal of Functional Programming 5(4): 583–592, 1995.
• C. Okasaki, “Red-Black Trees in a Functional Setting”, Journal of Functional Programming 9(4): 471–477, 1999.
• S. Kahrs, “Red-Black Trees with Types”, Journal of Functional Programming 11(4): 425–432, 2001.
• K. Germane, M. Might, “Deletion: The Curse of the Red-Black Tree”, Journal of Functional Programming 24(4): 423–433, 2014.
• H. Kaplan, R. E. Tarjan, “Purely Functional, Real-Time Deques with Catenation”, JACM 46(5): 577–603, 1999.
• S. Adams, “Efficient Sets—A Balancing Act”, Journal of Functional Programming 3(4): 553–561, 1993.
• R. Hinze, R. Paterson, “Finger Trees: A Simple General-Purpose Data Structure”, Journal of Functional Programming 16(2): 197–217, 2006.
• N. Pippenger, “Pure versus Impure Lisp”, POPL 1996.
• R. Bird, G. Jones, O. de Moor, “More Haste, Less Speed: Lazy versus Eager Evaluation”, Journal of Functional Programming 7(5): 541–547, 1997.
• E. D. Demaine, S. Langerman, E. Price, “Confluently Persistent Tries for Efficient Version Control”, Algorithmica 57(3): 462–483, 2010.
• S. Collette, J. Iacono, S. Langerman, “Confluent Persistence Revisited”, SODA 2012.
• P. Bagwell, T. Rompf, “RRB-Trees: Efficient Immutable Vectors”, EPFL Technical Report, 2011.
• J. P. Bolívar Puente, “Persistence for the Masses: RRB-Vectors in a Systems Language”, Proceedings of the ACM on Programming Languages 1(ICFP), 2017.

课程资料

• E. D. Demaine, MIT 6.851 Advanced Data Structures（Spring 2021），L01 “Temporal” 课程页面，courses.csail.mit.edu/6.851/spring21/lectures/。

实验

• reproduce/pavl.c：持久化 AVL（路径复制 + 引用计数），第二节数据。
• reproduce/pvec.c：可调分支因子的位切分向量 trie，第五节数据；reproduce/plot_branching.py 生成 branching-tradeoff.svg。
• reproduce/queue_amort.py：批量队列与实时队列，第四节数据。
• reproduce/git_path_copy.sh：第七节的 Git 输出。
• reproduce/gen_hamt_svg.py：生成 hamt-node.svg。
• reproduce/results/：上述程序的原始输出。

复现命令：

cd reproduce
gcc -O2 -Wall -Wextra -o pavl pavl.c && ./pavl demo && ./pavl test && ./pavl measure
gcc -O2 -Wall -Wextra -o pvec pvec.c && ./pvec test && ./pvec measure
for r in 1 2 3; do taskset -c 15 ./pvec time 1048576 5; done
python3 queue_amort.py
bash git_path_copy.sh
python3 plot_branching.py      # 需要 matplotlib，读取 results/ 重画 ../branching-tradeoff.svg

系列导航： - 上一篇：线段树与树状数组 - 下一篇：Van Emde Boas 树

相关阅读： - 记录历史：持久化数据结构（节点复制的逐步推演） - Merkle 树与认证数据结构 - 红黑树 vs AVL - MVCC 实现变体