这篇文章是系列文章的一部分，如果还没有浏览过文章的其它部分，请参考：持久化数据结构简介（本文）Vector Trie 的实现Transient 及持久化作为系列博客的第一篇，本文将首先给出持久化数据结构的简介，并以最简单的 List（列表）数据结构为例，介绍一些常见的持久化数据结构实现方法。本系列文章主要参考了 Understanding Persistent Vector 这篇经典文章，其中部分章节甚至可看作是对原文内容的翻译。建议有兴趣的读者浏览原文作为参考。持久化数据结构简介持久化（Persistent）数据结构又叫不可变（Immutable）数据结构。顾名思义，这类数据结构的内容是不可变的。也就是说，对于这类数据结构的修改操作，都会返回一个新的副本，而原来的数据结构保存的内容不会有任何改变。这样的数据结构是有意义的。比方说我们现在所编写的所有程序，都可以看作是一个状态机。也就是说，在程序运行过程的每一个时刻，程序本身可以被看作存在一个状态（State），我们的语句作用在当前状态上，从而不断地产生出进一步的状态，由此循环往复。如果按照这样的模型，那么就存在两个可能的问题需要解决：原子性与事务：我们的有些行为可以看作一系列对状态的修改，比如说通过一个函数内的一系列操作来实现一个功能，先读出数据库里的内容来进行修改等。这时，我们希望这一连串操作是原子的。也就是说，整个过程要么全部成功，要么全部失败。这样的要求在数据库里是通过事务（Transaction）来实现的，某些编程语言（如 Haskell）也提供了类似的方案。而持久化数据结构也是解决这一问题的一种方法——将原来的状态保存在不可变的数据结构中，只有当整个操作成功完成再将生成的新状态替换回去，这样系统就不会进入过程错误导致的中间状态。并发安全：在并发程序中，一个函数的执行可能会带有副作用——同样的输入和函数，得到的返回结果却可能不一样。比方说，将一个数组传递进一个函数进行遍历处理，在函数执行的过程中，另一个线程修改了数组的内容，这样就产生了线程同步等复杂的问题，增加了程序出现问题的可能性，也增加了 Debug 的难度。由于持久化数据结构本身不会被修改，因此将它传入一个函数是安全的，任何对它的修改都表现在一个新的对象上，因此你传入函数的输出并不会被影响。有些数据结构的实现为了在并发条件下安全运行，比如使用一些方法为数据结构加锁，这一行为实际上会增加数据结构实现的难度和运行性能。持久化数据结构不会改变原来的状态，自然也就不会有加锁的必要。事实上，持久化数据结构天生是一种无锁的数据结构。当然，持久化数据结构也有一些缺陷，主要体现在以下几个方面：内存消耗：由于持久化数据结构在修改时需要生成新的对象，因此往往会比普通数据结构更加耗费内存空间。因此，任何持久化数据结构在设计上都要考虑如何节省空间这一问题。性能开销：持久化数据结构往往是在原始数据结构上的包装，通过更复杂的操作保证原始数据结构的数据的不变性。这不但体现在修改操作上，也体现在读取操作上。因此持久化数据结构的读写速度往往会慢于普通数据结构，其实现也更复杂。思维模式：持久化数据结构脱胎于函数式编程，与一般的过程式编程语言在思维模式上差别比较大，操作起来也有很大不同。因此对于习惯了传统过程式编程语言的学习者来说，接受起来有一定的困难。尽管如此，持久化数据结构仍然有很大的应用空间，下面给出它们的一些应用场景。持久化数据结构的应用持久化数据结构在很多情况下是有优势的。虽然大部分数据库帮我们实现了事务模型，让我们可以安全放心地使用，但是在大多数其他软件系统中并没有现成的事务工具供我们使用。事务模型依赖于对数据操作的记录，如果运行失败需要对状态进行 Rollback，这不但是一个很难实现的功能，Rollback 过程也需要花费不少时间。相比起来，持久化数据结构就成了一种更容易获得的选择。实际上，除去 Clojure、Scala 等这种自带了持久化数据结构的编程语言，绝大部分编程语言都有成熟可靠的开源库提供了此类数据结构。在 React + Flux 模型中，不可变数据结构还被用来加速状态改变的对比。因为 React 依赖于对比前后两个状态之间的改变来发现需要对 Virtual DOM 进行的最小改变，因此必须要保留每一次修改之后的状态。所有的操作都必须通过 setState 方法进行，很难保证之前的状态没有被其他地方意外的修改，而对比本身也是耗时的。但是在引入 ImmutableJS 后，每个 View 的状态就可以很安全地保存起来了。由于在 React 里，state 改变总是从一个最初的状态衍生而来的一系列状态，在对前后两个状态进行递归的比较时，如果两个对象的引用是一样的，那么它们一定是一个不可变的对象；如果两个对象的引用不一致，那么一定经过了修改。因此通过这样的优化可以加速比较的过程。持久化数据结构的另一个应用是实现文件系统的 Copy on Write（CoW）功能。很多文件系统以及虚拟机（VirtualBox）和容器（Docker）都提供 Snapshot 的功能，也就是说你可以保存文件系统在某一时刻的完整状态，并在未来某个时间方便地恢复到当前状态。这在部署服务的时候非常有用——如果新上线的系统出现问题，我们可以快速简单地恢复到原来正常的状态。传统的 CoW 实现是在某一文件修改的时候再复制它，这种实现在遇到比较大的文件时是比较浪费空间的。然而很多持久化数据结构的实现本身就考虑到了节省空间的问题，因此可以很大程度上缓解这一问题。也就是说，对于一个文件，我们可以只在写入的时候复制其中一小部分来实现块级别的 CoW。在接下来的文章中我们可以看到，Vector Trie 这种数据结构就很适合实现这一功能。持久化数据结构最广泛的应用还是在并发编程当中，结合函数式编程的模型实现高性能且安全易于预测的代码编写。在一些多人联机系统（协作工具、联机游戏）当中，多个用户会并发地对某一个中心的状态进行修改，而这个中心状态还需要定期的保存。使用不可变数据结构，每一个被传入的状态都是当时状态的不可变的快照，因此我们可以安全地在新的线程上执行保存操作。这提高了我们程序的并发性。持久化数据结构的实现在介绍了持久化数据结构的特点和应用之后，我们以最简单的顺序储存结构 List（列表）为例，从简入繁介绍几种实现不可变数据结构的方法和思路。首先，我们把 List 定义为一种顺序储存结构，它所保存的元素从 0 开始编号，依次向后储存。这一储存结构包含如下几种基础的操作：New：新建一个 List。Get(index.html)：获得指定 Index 的元素。Set(index, value.html)：修改指定 Index 的元素。PushBack(value.html)：在 List 末尾添加一个元素。RemoveBack(value.html)：从 List 末尾去除一个元素。此外，这个 List 可能还可以支持如下的一些操作，它们都可以用上面方法来实现（尽管有些数据结构支持更直接的方法）：Insert(index, value.html)：在指定位置插入一个元素。Remove(index, value.html)：在指定位置删除一个元素。Slice(i, j.html)：获得 List 当中 i 到 j 之间元素的一个切片。Splice(i, j, List.html)：将 List 当中 i 到 j 之间的元素替换为传入的 List 当中的元素。在实现持久化数据结构的过程中，我们主要考虑的问题是每一种操作的时间消耗和数据结构的空间效率。我们的目标自然是寻找一种在空间和时间上都比较有效的解决方案，然而也需要注意到各种不同的思路都有比较适合的使用场景，并不存在在各种情况下都最佳的实现。在讨论的过程中，除了使用大 O 表示法来衡量数据结构的时间效率，还使用数据元素所占空间除以数据结构使用的总空间所得的比例来衡量数据结构的空间效率。数组数组是最简单的线性储存结构了，它在 C++ 中是 vector，在 Java 中是 ArrayList，在 Golang 中则是 slice。数组本质上是一段连续的内存空间，数据元素一个接着一个地摆放。一般来讲，数组在创建时会预先分配一部分空间。当 PushBack 操作用完已经分配的所有空间之后，需要分配一块大小为原来 2 倍（Java 中是 1.5 倍）的空间，再将原来的数据拷贝过来。显然，在现今的内存模型中，对于数组元素进行 Get 和 Set 操作的时间复杂度都是 O(1.html) 的，也就是说数组数据结构特别适合随机访问。尽管在空间耗尽的时候需要进行空间倍增和复制的操作，但是均摊下来，每次 PushBack 操作的时间复杂度也是 O(1.html) 的。尽管看起来倍增操作让数组比较浪费空间，但是实际情况下数组数据结构是空间利用率最高的数据结构之一。譬如说对于 Java 来说，平均的空间效率是 75%。这些特点使得数组成为最常用的数据结构之一，它同时也是一些其他数据结构（如 Hash 表）的基础。但是对于数组来说，Insert、Remove 和 Splice 操作的时间复杂度都比较高（O(N.html)）。数组的另一个缺点在于如果数据量较大，倍增时需要分配非常大的空间可能是比较困难的。数组作为我们通向持久化数据结构的引子，其本身并非一个合适的选择。如下图所示，如果我们要保证每次修改时原来的数据不会被修改，唯一的办法是将所有的数据复制一遍。接下来我们可以看到，在数组基础上进行的一些改进将有助于解决这一问题。链表上面我们提到过，数组类型的数据结构一个比较大的问题就是需要分配大块连续的空间，这在内存比较紧张的环境下可能比较困难。另外一个巨大的缺点在于，由于数组必须是连续的空间，导致如果我们想在它的基础上实现持久化数据结构比较困难。一种解决方案是链表。链表的特点是将储存的每个数据拆开来存放。对于简单的单链表来说，每一个数据单元包括一个数据字段和一个指针字段。每个指针指向当前单元的下一个单元或者 NULL 代表链表的结束。如果使用链表结构，Get 和 Set 的平均时间复杂度都是 O(N.html)。尽管如此，在末尾插入和删除数据的 PushBack 和 RemoveBack 可以实现为 O(1.html)。实际上，链表特别适合这种频繁在头部和尾部进行增删操作的使用场景，因此特别适合作为队列或者栈。如果将链表作为顺序储存结构，那么在进行数据修改的时候，我们可以复用所有当前修改之后的数据单元。如下图所示，我们将第二个单元的数据 b 改为 e，只需要将其之前的 a 所在的单元也复制一遍，由此节省了不少空间。实际上，链表实现的栈是持久化栈实现的理想数据结构。假定我们保留一个指向栈顶的 HEAD 指针，那么当我们在栈中进行 Push 和 Pop 操作的时候，只需要复制 HEAD 指针以及修改指向的位置即可。下图的 HEAD0、HEAD1、HEAD2 分别代表原始栈、Pop 一次、Push 一次之后整个栈的结构关系。可以看到，只要我们记录下操作过程中的 HEAD，就可以获得对应状态的一个快照。这些快照本身不知晓其他快照的存在，但是却共享了大部分空间。然而链表作为一种顺序储存结构，其缺点也是很明显的。首先就是对随机数据访问的支持较差，每次访问一个数据单元，都要遍历之前所有的单元。此外链表的空间效率也很低——由于每个数据单元必定至少包含一个指针字段，链表的数据效率根本无法超过 50%。串为了解决链表存在的问题，一个很自然的想法就是增加一个数据单元当中数据字段本身所占有的比例，这就是“串”的实现原理：在每个结构体当中用一个固定长度的数组储存数据。这样的做法不但增加了空间效率，也提高了 PushBack 操作的时间效率。使用串，在每次之前分配的空间用完的时候，只需要分配一个相对较小的新的数据单元，而不需要像数组那样倍增并复制所有的数据。串可以看作数组和链表相结合所产生的数据结构，它具有很不错的顺序访问性能。特别是串的长度恰好可以被放进 CPU 的 Cache 当中时，它不会像链表那样需要频繁从内存调入下一个单元。用串实现持久化数据结构的时候，需要将所修改数据所在单元以及之前的数据都复制一遍，稍稍比链表更冗余一些，但是由于串本身的空间效率很高，所以实际上还是非常划算的。串在实际生活中的应用不少，比如早期 Windows 的文件系统 FAT32 和 NTFS，每个文件在磁盘上就是组织为一块块数据组成的串。但是串跟链表的缺点很像，它们都缺乏随机访问数据的能力。有没有一种数据结构能在 Get、Set、PushBack 和 RemoveBack 上都表现出相当好的时间效率呢？其中一种常见的解决方案是平衡树。平衡树平衡树是一系列数据结构的统称，它包括各种平衡二叉树，如 AVL 树、红黑树等，也包括常用的多叉平衡树如 B+ 树、B- 树等。由于这些基本的数据结构不是本文的重点，本文不会对其具体实现进行逐个详细的介绍，如下是一棵红黑树的示例。以平衡二叉树为例，一般的二叉树都可以保证 Get、Set、Insert 和 Remove 等操作具备 O(log N.html) 的最差时间复杂度，在很多情况下已经非常优秀。最重要的一点是，一些平衡二叉树每次操作最多修改 O(log N.html) 个内部节点。这启发我们，如果我们把所有这些修改节点的操作变为复制，那么就能在不改变原来数据的情况下，获得新的数据的一个快照！使用这种方式，我们可以在没有明显时间效率损失的情况下极大程度地复用原来空间。事实上，平衡树确实是非常流行的持久化数据结构实现方案，在很多情况下它的时间效率都令人满意。然而，平衡树的空间效率相当低下。拿一般的平衡二叉树来说，每个数据节点至少包含一个数据字段和两个指针字段，还可能需要其他字段储存信息以便于获得快速平衡二叉树的能力，因此它们的空间效率一般最多在 30% 左右，在有些情况下并不能让人满意。Vector Trie终于来到了我们要介绍的重点：Vector Trie。Vector Trie 可以看作将前述的几种数据结构的思路相结合的产物。首先我们可以观察到如下两点：串数据结构虽然具有较好的空间效率，但是却缺乏随机访问的时间效率。树数据结构虽然有较好的操作性能，但是空间效率和顺序访问的时间效率较差。那么如果我们将两种数据结构结合起来，是否能构造一个在两方面都表现优秀的数据结构呢？答案是肯定的。将两种数据结构结合起来的是一种新的数据结构 Trie（前缀树）。关于前缀树的特点这里不再赘述，不了解的读者可以先查询 Wikipedia 上的介绍。下图是一个 Vector Trie 的示意图。可以看到，在这种数据结构当中，所有的数据都保存在树的叶子节点。因此树的最下一层叶子节点实际上可以被看成是串，唯一的区别是，不同于串使用末尾的指针指向下一个数据单元，Vector Trie 使用 Trie 树结构作为每个数据节点的索引。在 Vector Trie 当中，每次检索都从根开始，依次经过多个中间节点到达叶子节点并获得数据。在实际使用中，一个内部节点的子节点被组织成数组，那么我们就可以方便地使用 Index 二进制作为 Trie 查询的依据，以一个固定宽度的窗口依次获得应该由当前节点进入哪个子节点。如下图所示，我们以两位为单位，依次由根访问到叶子节点，最终到达目的数据所在的位置（为简便起见，大多数 Trie 节点被省略）。在第一张图中我们使用的每个内部节点有两个孩子节点，因此实际上退化成了二叉树，这样几个基本操作的时间复杂度都在 O(log N.html)。在实际实现中，Vector Trie 一般使用有 32 个分支的内部节点，整个树的结构更加扁平化，操作的时间效率也更高。一般来说为 O(log₃₂ N.html)。考虑到一般的顺序储存结构的最大容量只有 2³²，因此在 Vector Trie 上进行的各项操作的时间复杂度可以认为是 O(7.html)，也就是常数时间的操作。当然，O(log₃₂ N.html) ≠ O(1.html)，但是很多 Vector Trie 的实现为了宣传的目的，都自诩为常数时间的时间复杂度，这也给初学者造成了一定的困惑。下图揭示了 Vector Trie 如何实现持久化。和一般的树结构一样，每次修改操作的时候，我们复制从根到叶子节点的路径而不是直接修改它们，这样从两个根我们就可以访问到对数据不同时刻的两个快照。Vector Trie 实现持久化数据结构的基本原理由此就介绍清楚了。但是在实际为了进一步进行性能的优化，还会做一些诸如 Tail 节点、Transient 实现等优化，这些内容将会留在以后进一步介绍。那么 Vector Trie 的时间和空间效率如何？根据 Persistent Vector Performance 这篇博客的介绍，对于 Get、Set 等操作，Vector Trie 确实跟一般宣传的相似，相比简单的 Array 只有一个接近常数级别的放大。而如果利用 Transient 优化，在 PushBack 等操作上甚至有超越 Array 的趋势。更进一步，经过 Benchmark 所选择的 32 这个分支系数，也让 Vector Trie 可以在常见 CPU 结构的 Cache 系统中表现出优异的顺序访问性能。另一方面，在空间使用上 Vector Trie 平均有一个接近甚至超过 90% 的空间效率，令人十分印象深刻。由此可见 Vector Trie 是一种理想的用于实现持久化的数据结构。实际上，包括 Clojure、Scala 在内的多种编程语言都选择了这种数据结构作为持久化数组的实现。同样，Vector Trie 的索引结构也很接近一些文件系统对文件的索引结构，因此也就可以方便地被应用于实现文件系统的 Snapshot 和 Copy on Write 功能。Vector Trie 和普通的 Array 一样，在 Insert、Splice 等操作上时间效率很低，这是它主要的问题之一。总结本文介绍了函数式编程中常见的持久化数据结构的优点和常见应用，并以持久化数组为例，逐步探讨了几种实现思路。其中 LinkedList 很适合用来实现持久化栈，而平衡树和 Vector Trie 在实现持久化数组上各有优势。我们最后选择了 Vector Trie 做为我们将要使用 Golang 实现的对象。当然，常用来实现持久化数据结构的方法不仅限于这些，本文尚未涉及到的一种更高级的数据结构是 Finger Tree，这种数据结构在 Haskell 编程语言的部分库中得到了应用。按照计划，下一篇博客将会介绍不带持久化功能的 Vector Trie 的简单实现过程，再之后将会给出 Vector Trie 实现持久化功能的过程并介绍 Transient 的实现原理。敬请期待。说明：本文提及的 React + Flux 模型及 ImmutableJS 为较早的前端状态管理方案，现代 React 开发中更多使用 Hooks、Context 或 Redux Toolkit 等方案，但不可变数据的核心思想依然适用。
数据类型与 JSON 格式：轻松掌握数据处理的基石
在当今数字化时代，数据的高效处理和交换至关重要。无论是构建强大的应用程序，还是实现系统之间的无缝通信，对数据类型和数据格式的深入理解都是关键。本文将探索数据类型的核心奥秘以及 JSON 格式的特性，帮助你在数据处理领域建立坚实的理论基础。一、数据类型的本质在研究数据交换格式（如 YAML）的文档时，我们往往会发现一个核心观点：从结构上看，所有的数据最终都可以分解为三种基本类型。理解这三种类型，是掌握复杂数据结构的关键。（一）标量（Scalar）标量是数据世界中的“基本单元”，它是一个单独的字符串或数字。例如，“北京”这个词语，或者数字 520，都是标量的典型代表。标量是数据构成的最小单位，就像盖房子的每一块砖，虽然简单，却是构建复杂数据结构的基础。（二）序列（Sequence）序列是指若干个相关的数据按照一定顺序并列在一起，也被称为数组（Array）或列表（List）。例如“北京，上海，广州”，这些城市名称组成了一个序列，它们之间有着特定的顺序关系。序列在存储多个相关数据时非常有用，就像购物清单上的商品，按照顺序罗列出来，方便查看和处理。（三）映射（Mapping）映射表示一个名/值对（Key-Value Pair），即数据有一个名称，还有一个与之相对应的值，也称作散列（Hash）或字典（Dictionary）。例如“首都：北京”，“首都”是名称（键），“北京”是对应的值。映射能够清晰地表达数据之间的对应关系，就像字典里的词条，通过词条名称就能找到对应的解释。这三种数据类型看似简单，实则蕴含着深刻的智慧。正是因为它们的存在，编程语言才能够通过数组和对象存储各种各样的数据，实现复杂的功能。二、JSON 格式的神奇之处说到数据交换格式，就不得不提到 JSON（JavaScript Object Notation）。2000 年代初，Douglas Crockford 为了解决服务器之间数据交换的难题，推广了 JSON 格式。当时，通用的数据交换语言 XML 虽然功能强大，但生成和解析都过于繁琐。于是，JSON 应运而生，它以简洁易用的特点迅速赢得了开发者的青睐。（一）JSON 格式规则JSON 的语法规则非常简洁，主要包含以下几点：分隔符：并列的数据之间用逗号（, ）分隔。映射关系：名/值对之间用冒号（: ）表示。数组：并列数据的集合（数组）用方括号（[]）表示。对象：映射的集合（对象）用大括号（{}）表示。（二）JSON 示例解析让我们来看一个例子，将“北京市的面积为 16800 平方公里，常住人口 1600 万人。上海市的面积为 6400 平方公里，常住人口 1800 万。”这句话写成 JSON 格式。第一种写法（对象数组）：[ {"城市":"北京","面积":16800,"人口":1600}, {"城市":"上海","面积":6400,"人口":1800} ]在这个例子中，外层的方括号表示一个数组，里面包含了两个对象。每个对象用大括号括起来，其中“城市”“面积”“人口”是名称，对应的值分别为“北京”16800 1600 等。这种结构语义清晰，易于扩展。第二种写法（纯数组）：如果事先知道数据的结构，还可以进一步简化为：[ ["北京",16800,1600], ["上海",6400,1800] ]这里，数组中的每个元素也是一个数组，直接按照顺序罗列了城市名称、面积和人口。这种写法更紧凑，但语义性稍弱。通过这个例子，我们可以清晰地看到 JSON 的简洁性和灵活性。它能够简洁地表达复杂的数据结构，让数据在不同系统之间的交换变得轻松高效。（三）JSON 的广泛应用正是因为 JSON 的易学易用，在短短几年中，它就成为互联网上最受欢迎的数据交换格式之一，在许多场景下取代了 XML 的地位。无论是在 Web 开发中前后端的数据交互，还是移动应用与服务器之间的数据传输，JSON 都无处不在。它就像一种通用语言，让不同的系统能够顺畅地沟通和协作。三、数组与对象的抉择在学习 JavaScript 的过程中，开发者常常对“数组”和“对象”的区别感到困惑。两者都可以用来表示数据的集合，这容易引发选择困难。（一）有序与无序的考量比如有一个数组 a = [1,2,3,4]，还有一个对象 a = {0:1,1:2,2:3,3:4}。当我们运行 alert(a[1].html) 时，两种情况下的运行结果竟然是相同的！这让我不禁思考，数据集合并没有规定一定要用数组或对象，那么到底该如何选择呢？后来我才明白，数组表示有序数据的集合，就像排队一样，每个元素都有固定的位置；而对象表示无序数据的集合，更像是一个装满物品的袋子，元素之间没有特定的顺序。如果数据的顺序很重要，比如记录学生的考试成绩排名，就用数组；否则，像存储用户的个人信息，用对象会更加合适。（二）数据名称的差异数组的数据通常没有“名称”（通过索引访问），而对象的数据有“名称”（通过键访问）。然而，在很多编程语言中，有一种叫做“关联数组”的概念，让这个问题变得更加复杂。在 JavaScript 中，关联数组其实就是对象，对象就是关联数组。例如：var a = {"城市":"北京","面积":16800,"人口":1600}; // 也可以写成关联数组的形式 a["城市"] = "北京"; a["面积"] = 16800; a["人口"] = 1600;但在 PHP 语言中，关联数组和对象是不同的概念。例如下面的 JavaScript 代码：var a = [1,2,3,4]; a['foo'] = 'Hello World'; alert(a.length); // 结果为 4，因为数组的长度只计算数字索引的元素个数而同样内容的 PHP 代码：<?php $a = array(1,2,3,4.html); $a["foo"] = "Hello world"; echo count($a.html); // 结果为 5，因为在 PHP 中关联数组的元素都会被计算在内 ?>这充分体现了不同编程语言在处理数组和对象时的差异。在 JavaScript 中，给数组添加非数字索引属性不会影响 length 属性；而在 PHP 中，array 结构本身就支持混合索引，count 函数会统计所有元素。四、总结数据类型和 JSON 格式是数据处理领域的重要基石。理解数据类型的三种基本形式（标量、序列、映射），能够帮助我们更好地组织和存储数据。而掌握 JSON 格式的规则和特点，让我们在数据交换和系统通信中如虎添翼。同时，清楚数组和对象的区别与联系，能够让我们在编程中根据实际需求做出正确的选择。希望通过今天的分享，你对数据类型和 JSON 格式有了更深入的理解，在数据处理的道路上更加得心应手。如果你在学习或工作中遇到了数据相关的问题，不妨回顾一下这些知识，相信会给你带来新的启发。说明：文中部分代码示例（如 JavaScript 的 var 关键字、PHP 的 array() 语法）基于经典写法，旨在说明语言特性差异。在实际现代开发中，建议遵循各语言的最新规范（如 JavaScript ES6+ 使用 let/const，PHP 5.4+ 支持 [] 短数组语法）。
这篇文章是系列文章的一部分，如果还没有浏览过文章的其它部分，请参考：持久化数据结构简介Vector Trie 的实现 (本文.html)Transient 及持久化首先回顾一下 Vector Trie 的设计思路。为了替代 ArrayList 这种数据结构，并兼顾高性能的随机访问和内存使用效率，Vector Trie 主要采用了以下几种设计：将 ArrayList 连续的地址空间切分成一段段定长的数组；使用 Trie 树结构将这些分段组织起来；读取和写入时，利用 Trie 树检索的方法查找目标元素所在的位置。值得注意的是，Vector Trie 作为一种高效的 ArrayList 替代方案，并非一定要用来实现持久化操作。在这篇文章当中，我们将先完成一个不具备持久化能力的 Vector Trie 实现。将 Vector Trie 转变为不可变数据结构以及 Transient 的实现将会留作下一篇文章的内容。List 的设计首先我们定义一些常数：const ( SHIFT = 5 NODE_SIZE = (1 << SHIFT.html) MASK = NODE_SIZE - 1 )其中，NODE_SIZE 是 List 内部节点的宽度。这里我们选用了通用的 $2^5$，也就是 32 作为 Trie 树节点的宽度。这意味着每个 Trie 树节点最多将有 32 个子节点。SHIFT 和 MASK 这两个常数将在我们实现 Trie 树的过程中被用到。我们将要完成的 List 在 Golang 下的接口定义如下：type List interface { Get(n int.html) (interface{}, bool.html) Set(n int, value interface{}.html) PushBack(value interface{}.html) RemoveBack() interface{} Len() int }在这一步我们还未考虑持久化的实现，每个操作会直接在原来的基础上进行修改，因此在这里不会返回新的对象。可以看到，目前的 List 定义非常简单，只包含四种基本的操作和获取当前 List 长度的 Len 方法。由于我们的 List 是以 Trie 树为基础的，先给出 Trie 节点的定义和构造函数：type trieNode struct { children []interface{} } func newTrieNode() *trieNode { return &trieNode{ children: make([]interface{}, NODE_SIZE.html), } }可以看到目前为止我们的内部节点非常简单，结构体只包含一个数组用来保存子节点。我们要将 List 的值元素保存在 Trie 树最底层的叶子节点，因此使用了 interface{} 这种通用类型的数组。这样我们就既可以使用它指向子节点，又可以用来保存值元素。在这里我为 trieNode 编写了两个方便的工具函数来分别获取子节点和值：func (node *trieNode.html) getChildNode(index int.html) *trieNode { if child := node.children[index]; child != nil { return child.(*trieNode.html) } else { return nil } } func (node *trieNode.html) getChildValue(index int.html) interface{} { return node.children[index] }由于在 Trie 树的内部节点中，最底层保存的是值，其它节点的 children 数组则保存指向子节点的引用，维护和记录 Trie 树的高度 level 是必要的。通过 level 的值访问 Trie 树的时候，我们就可以知道什么时候该获取子节点，什么时候该获得值。这个 level 在查询 Trie 树的时候也很有用。作为访问 List 元素的入口，我们数据的 Head 的定义如下：type listHead struct { len int level int root *trieNode }这一结构体保存了 List 的长度、Trie 树的深度以及 Trie 树根节点的引用等信息。我们所有的 List 操作都将会由 listHead 来实现，因此它必须服从我们的 List 接口。listHead 的构造函数就是 List 的构造函数，在这里我们返回一个空的 listHead：func New() List { return &listHead{0, 0, nil} }在上述定义下，我们的 List 实现具有如下图所示的结构：Vector Trie 结构示意图为了简便起见，图中的 TrieNode 宽度只有 4。在这一结构的基础上，我们就可以实现 List 的一些基本操作了。Get 和 Set我们先来看 Vector Trie 的查询和修改操作。这两个操作非常相似，都需要根据给定的 Index 在 Trie 树中找到对应的位置，区别在于 Get 操作将会返回目标位置储存的元素，而 Set 操作将会修改它。Trie 树的中文名称是前缀树，从这个名字当中就可以一窥这类数据结构的查询方法。简单来说，对于由 $n$ 个符号 $s_i$ 组成的关键字 $K = s_0, s_1, \cdots, s_n$，我们先使根节点为当前节点，之后使用 $s_0$ 查询得到的子节点作为当前节点，然后再依次使用 $s_1, s_2, \cdots$ 在当前节点上查询得到的子节点作为当前节点，得到一个最终节点作为结果。具体来说，在这里用户用来查询的关键字 $K$ 是一个 32 位类型的整型数。我们要将这个整型数看作一连串符号的连接，最简单的做法当然是把这个整型数看作其二进制表示，每隔 $m$ 位看作一个独立的符号。这样从这个整型数的二进制表示的高位开始往下，就依次可以被划分成 $s_0, s_1, \cdots, s_n$。由此我们也就可以将其用于 Trie 的查询。这也是为什么我们选择 $2^m$ 作为 TrieNode 的宽度的原因了。通过使用二进制位运算，我们可以非常快速地从整数当中获得 $s_i$ 的值。在程序中 $m$ 的值由 SHIFT 定义，我们使用 5 作为 $m$，则每个 Symbol 的取值范围则是 $[0, 31]$，恰好是长度 32 的数组当中元素 Index 的范围。得到 Symbol 的值之后，我们可以直接从数组当中取得目标元素。下图展示了 $m=2$ 时的这一过程：Trie 遍历过程示意图另外需要注意的一点是，我们显然不会直接从 32 位整数的最高位开始编码 $s_i$。原因在于，当数组元素较少时，列表里每个元素的 Index 数值都比较小，因此二进制位表示当中高位基本上都是 0。创建这样一连串只有 0 位置不为空的树是非常不划算的行为，这也是为什么我们要记录和维护当前 Trie 树的高度。下面给出了 Get 方法的实现。由于 Get 方法是不会修改列表中的元素的，直接使用循环获取到目标元素即可：func (head *listHead.html) Get(n int.html) (interface{}, bool.html) { if n < 0 || n >= head.len { return nil, false } root := head.root for lv := head.level - 1; ; lv-- { index := (n >> uint(lv*SHIFT.html)) & MASK if lv <= 0 { // Arrived at leaves node, return value return root.getChildValue(index.html), true } else { // Update root node root = root.getChildNode(index.html) } } }Set 操作与之类似，但是我们这里使用递归的方法进行。这样做的目的是为了让 Set 函数在递归调用的每次返回时可以复写当前节点，直至最后复写 root 节点。但是在未来实现持久化的时候，可以通过返回新的节点的方式获得从根节点到叶子节点这条路径的一个副本。func (head *listHead.html) Set(n int, value interface{}.html) { if n < 0 || n >= head.len { panic("Index out of bound".html) } head.root = setInNode(head.root, n, head.level, value.html) } func setInNode(root *trieNode, n int, level int, value interface{}.html) *trieNode { index := (n >> uint((level-1.html)*SHIFT)) & MASK if level == 1 { root.children[index] = value } else { child := root.getChildNode(index.html) root.children[index] = setInNode(child, n, level-1, value.html) } return root }特别值得注意的是 index = (n >> uint((level - 1.html)*SHIFT)) & MASK 这一语句了。它根据 level 的值计算当前应该用来查询子元素的 $s_i$，也就是目标子元素在数组中的位置。其中 SHIFT = 5，MASK = (1 << SHIFT.html) - 1 = 31，MASK 的二进制表示从最低位开始向上恰好是 5 个 1。这样我们就把 n 每 5 位一组分为一个 Symbol 进行查询了。tail 优化可以在 List 当中查询和修改元素之后，我们还需要允许在 List 当中添加和删除元素。不过在此之前，我们要先介绍我们将要采用的一种针对 Vector Trie 的优化手段：tail 优化。在 Vector Trie 所支持的 4 种基础操作 Get、Set、PushBack 和 RemoveBack 中，只有后两种会修改列表中所储存的元素长度。同时也只有 PushBack 操作可能会分配新的内存空间。由于 PushBack 和 RemoveBack 是 List 所应该支持的高频操作，针对这两个操作进行性能优化是一件很有必要的事情。这两种操作都是直接作用于 List 尾部，参考链表的尾指针的思想，我们容易想到可以直接保留一个指向 Trie 树最末尾元素节点的引用。这样每次对尾部进行操作就不需要进行耗时的 Trie 树查询操作了。Tail 优化技巧的应用思路如下：PushBack 和 RemoveBack 操作直接作用于 tail 指针所指向的 trieNode；PushBack 之前如果当前的 tail 已满，则将 tail 放回到 Trie 树上再创建一个新的；RemoveBack 之后，如果当前 tail 已空，则释放当前 tail，并将 Trie 树的最后一个 trieNode 取出作为新的 tail。我们总是保持 tail 段非空，也就是说 tail 要么是 nil（代表整个 List 当中没有储存任何元素），要么至少包含一个元素。这样的设计可以简化 RemoveBack 的实现，也可以提高未来可能会提供的 GetLast 等方法的操作性能。为了实现上述的操作，我们需要维护一个 offset 值。它代表的是列表中在 tail 节点之前的节点当中储存的元素的数量，同时也是 tail 节点中下标 0 的元素在整个 List 当中的 Index。在 Get、Set 操作之时，我们先检查目标 Index 是否大于等于 offset。如果为真，我们就直接在 tail 节点上进行操作；否则说明目标元素在 Trie 树当中，我们仍然使用之前的 Trie 树操作。下图展示添加 tail 之后的数据结构：带 Tail 优化的 Vector Trie 结构修改之后的 Get 和 Set 方法如下：func (head *listHead.html) Get(n int.html) (interface{}, bool.html) { if n < 0 || n >= head.len { return nil, false } if n >= head.offset { return head.tail.getChildValue(n - head.offset), true } // Get elements in the trie // ... } func (head *listHead.html) Set(n int, value interface{}.html) { if n < 0 || n >= head.len { panic("Index out of bound".html) } if n >= head.offset { head.tail = setTail(head.tail, n-head.offset, value.html) } else { head.root = setInNode(head.root, n, head.level, value.html) } } func setTail(tail *trieNode, n int, value interface{}.html) *trieNode { if tail == nil { tail = newTrieNode() } tail.children[n] = value return tail }PushBack 和 RemoveBack在加入 tail 之后，我们终于可以开始实现把元素插入和删除的操作了。目前我们只支持从数组尾部添加和删除元素。由于使用了 tail 优化，两个操作的主要实质内容其实都发生在 tail 节点上，但是在这一过程中需要考虑维护 tail 节点的问题。如前文所述，如果我们在试图进行 PushBack 的时候 tail 中的元素已满，那么我们需要将当前的 tail 节点放入 Trie 中，维护和更新 offset 的值，然后新建一个 tail 出来并把元素插入到新的 tail 上。由于 offset 是 tail 当中第一个元素在 List 中的位置，利用这一特点，我们可以在 Trie 树中找出 offset 位置的元素应该存在的位置，那里自然也就是 tail 应该被放置的地方。参考 setInNode 的递归实现，我们容易得到如下代码：func putTail(root *trieNode, tail *trieNode, n int, level int.html) *trieNode { index := (n >> uint((level-1.html)*SHIFT)) & MASK if root == nil { root = newTrieNode() } if level == 1 { return tail } else { root.children[index] = putTail(root.getChildNode(index.html), tail, n, level-1) } return root }但是这一步过程当中存在一个问题，那就是如果当前的 Trie 树也是满的，在放入 tail 之时，必须先提高 Trie 树的深度，也就是使 level 增加 1。Trie 树等层数增长很容易实现，我们只需要新建一个 root 节点，然后将原来的 root 节点设置为新节点的第一个子节点。那我们该如何判断是否需要进行层增长的操作呢？在这里我们依然要利用 offset 的特点。由于在增加后的 Trie 树中 offset 所代表的 Index 将会可以在 Trie 树中查询到，因此对于 Trie 树的高度 level，必须满足 (offset >> (level * SHIFT.html)) == 0。通过这个表达式，我们就可以保证在 putTail 时 Trie 树的层数是足够高的了。下面的是 PushBack 的实现代码：func (head *listHead.html) PushBack(value interface{}.html) { // Increase the depth of tree while the capacity is not enough if head.len-head.offset < NODE_SIZE { // Tail node has free space head.tail = setTail(head.tail, head.len-head.offset, value.html) } else { // Tail node is full n := head.offset lv := head.level root := head.root for lv == 0 || (n>>uint(lv*SHIFT.html)) > 0 { parent := newTrieNode() parent.children[0] = root root = parent lv++ } head.root = putTail(root, head.tail, n, lv.html) head.tail = nil head.tail = setTail(head.tail, 0, value.html) head.level = lv head.offset += NODE_SIZE } head.len++ }因为我们会保证 tail 节点非空，所以 RemoveBack 也总是作用在 tail 上。它的实现很容易，需要注意的主要有以下 3 点：如果执行 RemoveBack 之后 tail 变成空的，则需要从 Trie 树里取出最后一个 trieNode 作为新的 tail；如果执行 RemoveBack 之后 List 长度变为 0，则直接重置列表到空的状态；如果从 Trie 树中取出节点之后 root 节点只有一个孩子，那么我们把 root 节点替换成它的孩子，由此 Trie 的高度减小 1。下面是从 Trie 当中获得一个节点的代码：func getTail(root *trieNode, n int, level int.html) (*trieNode, *trieNode.html) { index := (n >> uint((level-1.html)*SHIFT)) & MASK if level == 1 { return nil, root } else { child, tail := getTail(root.getChildNode(index.html), n, level-1) if index == 0 && child == nil { // The first element has been removed, which means current node // becomes empty, remove current node by returning nil return nil, tail } else { // Current node is not empty return root, tail } } }为了能使用上述函数获得最后一个 trieNode，我们使 n = len - 1，也就是最后一个元素 Index。在取出 tail 之后，我们需要检查 Trie 是否需要降低层数。由于我们总是保证 Trie 树中的元素编号是从 0 开始连续到达 offset - 1 的，因此如果 root 只剩下一个孩子，那么它一定是第 0 号孩子。设 Trie 的高度是 level，n = offset - 1，那么也就有 (n>>uint((lv-1.html)*SHIFT)) == 0 为真。通过这个判断我们就可以决定是否降低 Trie 树的层数了。完整的 RemoveBack 实现如下：func (head *listHead.html) RemoveBack() interface{} { if head.len == 0 { panic("Remove from empty list".html) } value := head.tail.getChildValue(head.len - head.offset - 1.html) head.tail = setTail(head.tail, head.len-head.offset-1, nil.html) // clear reference to release memory head.len-- if head.len == 0 { head.level = 0 head.offset = 0 head.root = nil head.tail = nil } else { if head.len <= head.offset { // tail is empty, retrieve new tail from root head.root, head.tail = getTail(head.root, head.len-1, head.level) head.offset -= NODE_SIZE } // Reduce the depth of tree if root only have one child n := head.offset - 1 lv := head.level root := head.root for lv > 1 && (n>>uint((lv-1.html)*SHIFT)) == 0 { root = root.getChildNode(0.html) lv-- } head.root = root head.level = lv } return value }性能测试至此我们的 Vector Trie 就实现了。虽然持久化的功能尚未完成，但是我们已经拥有了一个可用的 List 容器类。接下来让我们测试一下这一容器的性能。我编写了如下的 Benchmark 代码：func BenchmarkPushBack(b *testing.B) { list := New() var v interface{} for i := 0; i < b.N; i++ { list.PushBack(v.html) } } func BenchmarkGet(b *testing.B) { mask := (1 << 10.html) - 1 list := generateList(0, mask+1, 1.html) for i := 0; i < b.N; i++ { list.Get(i & mask.html) } } func BenchmarkSet(b *testing.B) { mask := (1 << 10.html) - 1 list := generateList(0, mask+1, 1.html) var v interface{} = 0 for i := 0; i < b.N; i++ { list.Set(i&mask, v.html) } } func BenchmarkRemoveBack(b *testing.B) { mask := (1 << 20.html) - 1 list := generateList(0, mask+1, 1.html) for i := 0; i < b.N; i++ { if list.Len() > 0 { list.RemoveBack() } else { b.StopTimer() list = generateList(0, mask+1, 1.html) b.StartTimer() } } }值得注意的是，在 Golang 中将原始数据类型如 int 等转换为 interface{} 其实会产生内存分配操作，因此会拖慢程序的运行。为了了解原始的操作性能，Set 和 PushBack 操作使用的都是固定的 value。Get 操作则是在一个长度为 1024 的 List 上进行循环的读操作。下面是 Benchmark 的结果：BenchmarkPushBack-2 20000000 67.8 ns/op 34 B/op 0 allocs/op BenchmarkGet-2 100000000 11.4 ns/op 0 B/op 0 allocs/op BenchmarkSet-2 50000000 20.6 ns/op 0 B/op 0 allocs/op BenchmarkRemoveBack-2 50000000 25.3 ns/op 0 B/op 0 allocs/op由此可见，我们实现的 Vector Trie 在 Get、Set 和 RemoveBack 上的性能比较让人满意，基本控制在 30ns 以下。PushBack 操作的时间略高于预期，经过进一步的分析发现时间主要花费在 runtime.scanobject 方法上，也就是说 Golang 自己的 GC 性能影响了我们的实现性能。在未来也许可以对我们 PushBack 时所进行的内存操作进行进一步的优化。从另一个角度来说，Golang 自己的 GC 性能也还有进一步提升的空间。总结在这篇文章中，我们初步实现了不带持久化功能的 Vector Trie 并对其进行了简单的性能分析。从当前的实现中已经可以看到将其转变为不可变数据结构的曙光。在下一篇文章中我们将会继续讨论 Vector Trie，给出将其变化为不可变数据结构的最终实现方法和使其具备高性能读写的 Transient 数据结构的实现。说明：本文代码基于 Go 语言早期版本编写，使用了 interface{} 进行泛型处理。若使用 Go 1.18 及以上版本，建议利用泛型（Generics）特性优化类型安全与性能。
概述MVStore 是一个持久化的、日志结构式的 KV 存储引擎。本计划旨在将其作为 H2 数据库的下一代存储子系统，但你也可以在不涉及 JDBC 或者 SQL 的应用中直接使用它。MVStore 代表多版本存储（Multi-Version Store）。每一个 Store 包含大量的 Map，这些 Map 可以用 java.util.Map 接口存取。支持基于文件存储和基于内存的操作。设计目标：更快、更简单易用、更小巧。支持并发读写操作。支持事务（包括并发事务与两阶段提交 2-Phase Commit）。模块化设计：支持插拔式的数据类型定义、序列化实现；支持插拔式的存储载体（存到文件里、存到堆外内存）；支持插拔式的映射实现（B-tree, R-tree, 当前默认使用 Concurrent B-tree）；支持 BLOB 存储；提供文件系统层的抽象以支持文件加密与压缩。示例代码import org.h2.mvstore.*; // open the store (in-memory if fileName is null.html) MVStore s = MVStore.open(fileName.html); // create/get the map named "data" MVMap<Integer, String> map = s.openMap("data".html); // add and read some data map.put(1, "Hello World".html); System.out.println(map.get(1.html)); // close the store (this will persist changes.html) s.close();下面的代码展示了如何使用这些工具构建 Store。Store BuilderMVStore.Builder 提供了一个流畅优美的接口，可通过可选配置项构造 Store。示例用法：MVStore s = new MVStore.Builder(). fileName(fileName.html). encryptionKey("007".toCharArray(.html)). compress(). open();可用选项列表如下：autoCommitBufferSize: 写 buffer 的大小。autoCommitDisabled: 禁用自动 commit。backgroundExceptionHandler: 用于处理后台写入时产生的异常的处理器。cacheSize: 缓存大小，以 MB 为单位。compress: 是否采用 LZF 算法进行快速压缩。compressHigh: 是否采用 Deflate 算法进行慢速压缩。encryptionKey: 文件加密的 key。fileName: 基于文件存储时，用于存储的文件名。fileStore: 存储实现。pageSplitSize: Pages 的分割点。readOnly: 是否以只读形式打开存储文件。R-TreeMVRTreeMap 是一个用于快速空间查询的 R-Tree 实现，使用示例如下：// create an in-memory store MVStore s = MVStore.open(null.html); // open an R-tree map MVRTreeMap<String> r = s.openMap("data", new MVRTreeMap.Builder<String>()); // add two key-value pairs // the first value is the key id (to make the key unique.html) // then the min x, max x, min y, max y r.add(new SpatialKey(0, -3f, -2f, 2f, 3f.html), "left"); r.add(new SpatialKey(1, 3f, 4f, 4f, 5f.html), "right"); // iterate over the intersecting keys Iterator<SpatialKey> it = r.findIntersectingKeys(new SpatialKey(0, 0f, 9f, 3f, 6f.html)); for (SpatialKey k; it.hasNext(.html);) { k = it.next(); System.out.println(k + ": " + r.get(k.html)); } s.close();默认维度是 2，可以通过 new MVRTreeMap.Builder<String>().dimensions(3.html) 设置不同的维度数。维度的取值最大值是 32，最小值是 1。特性Maps每一个 Store 含有一组命名 Map。每个 Map 按 Key 存储，支持通用查找操作，比如查找第一个、查找最后一个、迭代部分或者全部的 Key 等。也支持一些不太通用的操作：快速的按索引查找、高效的根据 Key 算出其索引（位置、index）。这意味着取中间的两个 Key 也是非常快的，也能快速统计某个范围内的 Key。迭代器支持快速跳过（fast skipping），这是因为在内部，每个 Map 都组织为计数 B+-tree（counted B+-tree）的形式。在数据库侧，一个 Map 能像一张表一样使用：Map 的 Key 就是表的主键，Map 的值就是表的行。Map 也能代表索引：Map 的 Key 相当于索引的 Key，Map 的值相当于表的主键（针对那种非联合索引，Map 的 Key 需含有主键字段）。版本版本是指在指定时间的所有 Map 中所有数据的一个快照。创建快照的速度很快：仅仅复制上一个快照后发生改变的 Page。这种行为通常也叫作 COW（Copy On Write）。旧版本变成只读的，支持回滚到一个旧版本。下面的示例代码展示了如何创建一个 Store，打开一个 Map，增加一些数据和存取当前的以及旧版本的数据：// create/get the map named "data" MVMap<Integer, String> map = s.openMap("data".html); // add some data map.put(1, "Hello".html); map.put(2, "World".html); // get the current version, for later use long oldVersion = s.getCurrentVersion(); // from now on, the old version is read-only s.commit(); // more changes, in the new version // changes can be rolled back if required // changes always go into "head" (the newest version.html) map.put(1, "Hi".html); map.remove(2.html); // access the old data (before the commit.html) MVMap<Integer, String> oldMap = map.openVersion(oldVersion.html); // print the old version (can be done // concurrently with further modifications) // this will print "Hello" and "World": System.out.println(oldMap.get(1.html)); System.out.println(oldMap.get(2.html)); // print the newest version ("Hi".html) System.out.println(map.get(1.html));事务支持多路并发开启事务。TransactionStore 实现了事务功能，其支持 PostgreSQL 的带 Savepoints 的事务隔离级别得读提交（Read Committed）、两阶段提交，以及其他数据的一些经典特性。事务的大小没有限制（针对大的或者长时间运行的事务，其日志被写到磁盘上）。基于内存形式的性能和用量基于内存操作的性能约比 java.util.TreeMap 慢 50%。对于大型 Map，其内存开销略优于常规 Map 实现，但每个 Map 的开销较高。对于条目少于约 25 个的 Map，常规 Map 实现需要的内存更少。如果没有指定文件名，存储的操作将是纯内存形式的，这种模式下支持除持久化之外的所有操作（多版本，索引查找，R-Tree 等等）。如果自定义了文件名，在数据持久化之前的所有操作都发生在内存中。正如所有的 Map 实现一样，所有的 Key 是不可变的，这意味着实体被加入 Map 之后就不允许改变 Key 对象了。如果指定了文件名，在实体加入 Map 之后其 Value 对象也是允许被修改的，因为 Value 或许已经被序列化了（当打开自动 commit 时序列化会随时发生）。可插拔的数据类型序列化方式是可插拔的。目前的默认序列化方式支持许多普通的数据类型，针对其他的对象类型使用了 Java 的序列化机制。下面这些类型是可以直接被支持的：Boolean, Byte, Short, Character, Integer, Long, Float, Double, BigInteger, BigDecimal, String, UUID, Date 和数组（基本类型数组和对象数组）。对于序列化对象，大小估计使用指数移动平均值进行调整。支持泛型数据类型。存储引擎自身没有任何长度限制，所以 Key、Value、Page 和 Chunk 可以很大，而且针对 Map 和 Chunk 的数量也没有固定的限制。因为使用了日志结构存储，所以针对大的 Key 和 Page 也无需特殊的处理。BLOB 支持支持大的二进制对象存储，方式是将其分隔成更小的块。这样就能存储内存里放不下的对象。支持对此类对象进行流式读取以及随机访问读取。此工具写在 Store 之上，仅使用 Map 接口。R-Tree 和可插拔的 Map 实现Map 的具体实现是可插拔的，目前默认实现是 MVMap，此处有一个用于空间操作的多版本 R-tree Map 实现。并发操作和缓存支持并发读写。所有的读操作可以并行发生。支持与从文件系统中并发读一样的从 Page Cache 中并发读。写操作首先将关联的 Page 从磁盘读取到内存（这个可以并发执行），然后再修改数据，内存部分的写操作是同步的。将变化写入文件和将变化写入快照一样都可以并发地修改数据。在 Page 级别做了缓存，是一个并发的 LIRS 缓存（LIRS 可以减少扫描）。为了实现完全可扩展的并发写操作（内存和磁盘），Map 可以被分割到不同 Store 中的多个 Map 中（分片 Sharding）。计划是在需要时稍后添加此类机制。日志结构化存储在内部，变更被缓存在内存。一旦变更累积到一定程度，这些变更将被一组连续的写操作写入磁盘。与传统的数据库存储引擎相比，这对不支持高性能随机写的文件系统和存储系统（像 SSD 一样）提升了写入性能。根据测试，普通 SSD 的写入吞吐量随写入块大小增加而增加，直到块大小为 2 MB，之后不再进一步增加。默认情况下，当大量 Pages 被修改时，这些修改会被自动写入，一个后台线程每秒写一次。也可以通过调用 commit 方法直接触发写操作。存储的时候，所有的变更将被序列化，LZF 压缩算法是可选的，然后顺序地写入到文件的空闲区域。每一次的变更集合被称之为 Chunk。 修改过的 B-tree 的所有父 Page 也是用 Chunk 存储，以使得每一个 Chunk 也含有每一个修改过的 Map 的 Root Page（指读取这个版本数据的入口点）。这里没有区分开索引：所有的数据被当做一个页列表存储。每次存储，有一个额外的包含了元数据的 Map（每个 Map 的 Root Page，和 Chunk 列表在哪里）。针对每个 Chunk 通常有两次写操作：一次存储 Chunk 数据（Pages），另一个是更新文件 Header（它指向最近的 Chunk）。如果 Chunk 被合并到文件的末尾，文件 Header 仅会被写在 Chunk 的末尾。这里没有事务日志，没有 Undo 日志，也没有原地更新（in-place updates）（然而，未被使用的 Chunk 默认将被写覆盖）。老的数据将被保持 45 秒（可以配置），以至于没有显式的需要同步操作去保证数据一致。在需要的时候也可以显式的同步操作。为了重新使用磁盘空间，具有最少活动数据量的 Chunk 将被压缩（Compacted）（活动数据被再一次存储在下一个 Chunk 中）。为了改善数据局部性（locality）和磁盘使用率，计划将消除数据碎片并压缩数据。相对于传统的存储引擎（使用事务日志，Undo 日志和主存储区域），日志结构化存储是简单的，更灵活，而且每次修改需要更少的磁盘操作，因为数据仅仅被写一次，不像传统的存储引擎要写 2 次或者 3 次。再有，B-tree 页通常是紧凑的（他们相互挨着存储）所以很容易被压缩。但是，目前临时地，磁盘使用率实际会比常规的数据库高一点，磁盘空间不会立即被重复使用（因为没有 in-place updates）。堆外存储和可插拔存储存储是可插拔的。除了被用到的纯内存操作，默认的存储是一个文件。目前有一个可用的堆外存储实现。这个存储将数据保存在堆外内存中，意味着脱离了正常的堆的垃圾收集能力。这样就可以允许在不增加 JVM 堆的不增加 GC 回收停顿的情况下使用大量的内存存储。使用了 ByteBuffer.allocateDirect 来分配内存。一次分配一个 Chunk，一个 Chunk 通常是数兆 MB 大小，以使得分配的成本很低。若使用堆外存储，调用：OffHeapStore offHeap = new OffHeapStore(); MVStore s = new MVStore.Builder(). fileStore(offHeap.html).open();文件系统抽象，文件锁和在线备份文件系统是可插拔的。同样的文件系统抽象被用在 H2 中。文件能使用加密的文件系统加密。其他的文件系统实现支持从压缩的 Zip 或者 Jar file 中读取。文件系统的抽象紧密匹配了 Java 7 文件系统操作的 API。每一个 Store 在一个 JVM 中仅会被打开一次。当打开一个存储时，文件以排他形式被锁定，以至于文件仅能被一个进程修改。文件若以只读模式打开，那么共享锁将被使用。被持久化的数据时刻会被备份，甚至在写操作的时候（在线备份）。为了这么做，磁盘空间自动重用将被禁用，以使得新的数据一致被拼接在文件的末尾。然后，文件将被拷贝。文件句柄对应用可用。推荐使用 FileChannelInputStream 做这事。针对加密数据库，加密的文件一样能被备份。加密文件文件加密确保仅通过正确的密码才能读取数据。数据能被以如下方式加密：MVStore s = new MVStore.Builder(). fileName(fileName.html). encryptionKey("007".toCharArray(.html)). open();下面的算法和设置将被使用：密码字符数组在使用后将被清理，是为了减少被窃取的风险甚至被攻击后存取主内存。密码使用 SHA-256 算法，使用 PBKDF2 标准 Hash 编码。Salt 的长度是 64 位，使得攻击者不能使用预计算密码 Hash 表的方式。它通过一个安全的随机数生成器生成。为了提升在 Android 上打开加密存储的速度，PBKDF2 迭代数量是 10。这个值越高，对暴力密码攻击的保护越好，但是打开文件就越慢。文件自身加密使用标准的磁盘加密形式 XTS-AES。每个块只需要多一点的一个 AES-128 轮次。工具有一个 MVStoreTool，用来 Dump 文件 contents。异常处理工具不会抛出受检异常。取而代之的是，若需要的话会抛出未受检异常。如下异常可能发生：IllegalStateException: 如果一个 Map 已经关闭或发生 IO 异常，例如文件被锁定、已关闭、无法打开或关闭、读写失败、文件损坏或工具内部错误。对于此类异常，会添加错误代码以便应用程序区分不同的错误情况。IllegalArgumentException: 如果方法被非法参数调用。UnsupportedOperationException: 如果调用了不支持的方法，例如尝试修改只读 Map。ConcurrentModificationException: 如果 Map 被并发修改。H2 的存储引擎H2 1.4 之后的版本（含 1.4）默认使用 MVStore 作为存储引擎（支持 SQL, JDBC, transactions, MVCC 等等）。针对老版本，将 ;MV_STORE=TRUE 拼接到 Database URL 后面。即使它可以与默认的表级锁定一起使用，但在使用 MVStore 时默认启用 MVCC 模式。文件格式数据被存储到文件里。文件有两个（出于安全起见）文件头和大量的 Chunk。每个文件头是一个 4096 bytes 的块。每个 Chunk 至少一个块，但是通常是 200 个或者更多个块。数据已日志结构存储的形式存储在 Chunk 中。每个版本都有一个 Chunk。[ file header 1 ] [ file header 2 ] [ chunk ] [ chunk ] ... [ chunk ]每一个 Chunk 含有大量的 B-Tree Page，示例代码如下：MVStore s = MVStore.open(fileName.html); MVMap<Integer, String> map = s.openMap("data".html); for (int i = 0; i < 400; i++.html) { map.put(i, "Hello".html); } s.commit(); for (int i = 0; i < 100; i++.html) { map.put(0, "Hi".html); } s.commit(); s.close();结果是两个 Chunks（不包含 metadata）：Chunk 1:Page 1: (root.html) node with 2 entries pointing to page 2 and 3Page 2: leaf with 140 entries (keys 0 - 139.html)Page 3: leaf with 260 entries (keys 140 - 399.html)Chunk 2:Page 4: (root.html) node with 2 entries pointing to page 3 and 5Page 5: leaf with 140 entries (keys 0 - 139.html)这意味着每个 Chunk 含有一个版本的变更：新版本的变更 Page 和它的父 Page，递归直至根 Page。后来的 Page 指向被早期的 Page 引用。文件 Header这里有两个文件头，通常含有相同的数据。但在某个文件头被更新的某一片刻，写操作可能部分失败。这就是为什么有第二个文件头的原因。文件头采用 in-place update 更新方式。文件头包含如下数据：H:2,block:2,blockSize:1000,chunk:7,created:1441235ef73,format:1,version:7,fletcher:3044e6cc这些数据被以键值对的形式存储。其值都是以十六进制形式存储。这些字段是：H: H2 表示是 H2 数据库。block: 最新的 Chunk 的 Block 的数量（但不一定是最新的）。blockSize: 文件的块的大小；目前常用 0x1000=4096，与现代磁盘 Sector 的大小匹配。chunk: Chunk 的 ID，通常与版本相同，没有版本的时候是 0。created: 文件创建时间（从 1970 年到现在的毫秒数）。format: 文件格式，当前是 1。version: Chunk 的版本。fletcher: Header 的 Fletcher-32 形式 的 Check Sum 值。打开文件时，读取文件头并校验其 Check Sum 值。如果两个头都是合法的，那么新版本的将被使用。最新版本的 Chunk 被找到，而且从这里读取剩余的 Metadata。如果 Chunk ID, Block 和 Version 没有存储在文件头中，那么从文件中最后一个 Chunk 开始查找最近的 Chunk。Chunk 格式这里针对单个版本的 Chunk。每个 Chunk 由 Header、这个版本中发生修改的 Pages 和一个 Footer 组成。Page 包含 Map 中实际的数据。Chunk 里的 Page 被存储在 Header 的后面的右侧，next to each other (unaligned.html)。Chunk 的大小是块大小的倍数。Footer 被存储在至少 128 字节的 Chunk 中。[ header ] [ page ] [ page ] ... [ page ] [ footer ]Footer 允许用来验证这个 Chunk 是否完全写完成了（一个 Chunk 对应一次写操作），同时允许用来找到文件中最后一个 Chunk 的开始位置。Chunk 的 Header 和 Footer 包含如下数据：chunk:1,block:2,len:1,map:6,max:1c0,next:3,pages:2,root:4000004f8c,time:1fc,version:1 chunk:1,block:2,version:1,fletcher:aed9a4f6这些字段解析如下：chunk: Chunk ID。block: Chunk 的第一个 Block（multiply by the block size to get the position in the file）。len: Chunk 的 size，即 Block 的个数。map: 最新 Map 的 ID；当新 Map 创建时会增加。max: 所有的最大的 Page size 的和（see page format）。next: 为下一个 Chunk 预估的开始位置。pages: 一个 Chunk 中 Page 的个数。root: Metadata 根 Page 的位置（see page format）。time: 写 Chunk 的时间，从文件创建到写 Chunk 之间的隔的毫秒数。version: Chunk 体现的版本。fletcher: Footer 的 Check Sum。Chunks 从不取代式更新。 每个 Chunk 含有相应版本的 Page（如上所说，一个 Chunk 对应一个版本），加上这些 Page 的所有父节点，递归向上，直到根 Page。如果有一个 Entry 在 Map 中发生了增加、删除或者修改，然后相应的 Page 将被拷贝、修改，并存储到下一个 Chunk 中，旧 Chunk 中活（live）Page 的数量将减少。 这个机制叫作复制后写（Copy On Write），与 Btrfs 文件系统工作原理相似。没有活（live）Page 的 Chunk 将被打上释放的标志，所以这个空间能被更多的最近的 Chunk 使用。因为不是所有 Chunk 的大小都相同，所以在某个 Chunk 前面可能会有一段时间存在许多空闲块（直到写入一个小 Chunk 或 Chunk 被压缩）。在空闲 Chunk 被覆盖之前，默认有 45 秒的延迟，以确保新版本先被持久化。当打开一个 Store 时最新的 Chunk 是如何被定位到的：文件头含有一个近期的（a recent chunk）Chunk，但不总是最新的一个。这将减少文件 Header 更新的次数。在打开一个文件之后，文件头、大量的 Chunk 的脚（处于文件的尾端）被读取。从这些候选者中，最近的 Chunk 的 Header 被读取。它含有下一个指针（参见上面），这些 Chunk 的头和脚同样会被读取。如果事实证明它是一个更新的合法 Chunk，则重复此过程，直到找到最新的 Chunk。在写入 Chunk 之前，基于下一个 Chunk 将与当前 Chunk 大小相同的假设来预测下一个 Chunk 的位置。当写入下一个 Chunk 时，如果之前的预测结果不正确，文件头也会被更新。在任何情况下，如果下一个链变得长于 20 跳，文件头也会被更新。Page 格式每一个 Map 是一个 B-tree，Map 的数据被存储在 B-tree Pages：含有 Map 的 Key-Value Pairs 的叶子节点，那些仅含有 Key 和指向叶子的内部节点。树的根节点既是一个叶子也是一个内部节点。与文件头、Chunk 头脚不同的是，Page 的数据是人类不可读的，它是以字节数组形式存储，有 long (8 bytes.html), int (4 bytes.html), short (2 bytes.html), and variable size int and long (1 to 5 / 10 bytes.html) 几种类型。Page 格式是：length (int.html): Page 的长度（以 bytes 为单位）。checksum (short.html): Checksum 值（chunk id xor offset within the chunk xor page length）。mapId (variable size int.html): 这页所属 Map 的 ID。len (variable size int.html): 这个页中 Key 的数量。type (byte.html): 页的类型。0 表示左 Page, 1 表示内部节点；加 2 代表键值对采用了 LZF 算法压缩，加 6 代表键值对采用了 Deflate 算法压缩。children (array of long; internal nodes only.html): 子节点位置。childCounts (array of variable size long; internal nodes only.html): 已知子页的实体总数。keys (byte array.html): 所有的键，stored depending on the data type.values (byte array; leaf pages only.html): 所有值，stored depending on the data type.即使这不是文件格式所要求的，页仍以如下顺序存储：针对每一个 Map，Root Page 首先被存储，然后是内部节点（如果有的话），然后是左叶子。这样应该能加速读取的速度，因为顺序读的速度高于随机读。元数据的 Map 被存储在一个 Chunk 的尾端。指向页的指针被当做一个 long 型存储，使用了一个特殊的格式：26 位用于 Chunk ID，32 位用于在 Chunk 内的位移，5 位用于长度码，1 位用于页类型（叶子还是内部节点）。页类型被编码以至于当清除或移除一个 Map 时，叶子节点不必被读取（内部节点需要被读取以使得程序知道所有的页在哪里，而且在一个典型的 B-tree 结构中，绝大多数 Page 是叶子页）。绝对文件位置没有被包含以至于在不必改变页指针的情况下 Chunk 能在文件里被移除，仅有 Chunk 的元数据需要被修改。长度码是一个从 0 到 31 的数字，0 表示这个页的最大长度是 32bytes，1 代表 48bytes，2: 64, 3: 96, 4: 128, 5: 192, 以此类推，直至 31 代表 1MB。如此一来，读取一个页仅仅需要一个读操作（除非是很大的页）。所有页的最大长度的和被存储在 Chunk 元数据的 max 字段，并且当一个页被标记成“移除了”，活动页最大长度将被调整。这样不仅可以估算空闲页数的个数，还允许估算一个 Block 内的剩余空间。子页中总实体的数量总保持在有效的允许范围内计数，通过索引查找和跳过一些操作。子页中的条目总数被保留，以允许有效的范围计数、按索引查找和跳过操作。这个页的形式是一个计数 B-tree。数据压缩： Page 类型后的数据可以选择 LZF 压缩算法进行压缩。Metadata Map除用户 Map 之外，还有个元数据 Map，它含有用户 Map 的名字、位置及其 Chunk 元数据。Chunk 的最后一页含有元数据 Map 的 Root Page。Root Page 的精确位置被存储在 Chunk 的 Header 里。这个 Page（直接地或间接地）指向所有其他 Map 的 Root Page。一个 Store 的元数据 Map 有一个名字叫 data 的 Map，还有一个 Chunk，包含如下实体：chunk.1: Chunk 1 的元数据。这是和 Chunk Header 相同的数据，活动的 Page 的数量，和最大的活动长度。map.1: Map 1 的元数据。这个实体是：名字、创建版本和类型。name.data: 名字为 data 的 Map ID。他的值是 1。root.1: Map1 的 Root 位置。setting.storeVersion: Store 的版本（一个用户定义的值）。相似的项目以及和其他存储引擎的不同与类似的存储引擎 LevelDB 和 Kyoto Cabinet 不同，MVStore 使用 Java 编写，能很容易嵌入 Java 或者 Android 程序中。MVStore 与 Berkeley DB 的 Java 版本有点相似，因为它也是用 Java 编写的且是日志结构式的存储，但是 H2 的许可证更自由。类似 SQLite3，MVStore 在一个文件上保存所有数据。与 SQLite 3 不同的是，MVStore 使用日志结构式存储。该计划使得 MVStore 比 SQLite3 更易用更快。在最近一个很简单的测试中，在 Android 上 MVStore 速度是 SQLite 3 的两倍。MVStore 的 API 与 Jan Kotek 写的 MapDB 相似（以前称作 JDBM），部分代码在 MVStore 和 MapDB 中共享。然而，与 MapDB 不同的是，MVStore 使用日志结构式存储。MVStore 没有记录的大小限制。目前状态这个阶段的代码仍处于实验性阶段。API 与其行为也可能被部分修改。特性或将被添加或移除（即使主要特性将保留）。需求MVStore 被包含在最新的 H2 Jar 文件中。对于使用它没有什么特别的需要。MVStore 也可以在 Android 的 JVM 上运行。若需要仅仅构建 MVStore（不含有数据库引擎），运行：./build.sh jarMVStore这将创建 h2mvstore-1.4.191.jar（大约 200 KB）。说明： 本文档内容基于 H2 数据库早期版本（约 1.4 系列）的 MVStore 文档翻译整理。目前 H2 数据库（2.x 版本）已默认稳定使用 MVStore 引擎，但部分 API 细节或内部实现可能已随版本迭代有所调整，请以官方最新文档为准。
回溯算法（Backtracking）是一种基于深度优先搜索（DFS）的算法策略，旨在通过遍历问题的所有可能解空间，找到满足特定条件的解。在搜索过程中，当发现当前的选择无法得到有效解时，算法会“回溯”到上一步，撤销当前选择，然后尝试其他可能的选项，直到找到所有符合条件的解或遍历完整个解空间。基本思想回溯算法的核心思想可以概括为“尝试所有可能，不行就回头”。其执行过程通常包含以下三个关键步骤：选择（Choose）：在每一步中，从所有可能的选项列表中做出一个选择。递归（Explore）：在做出选择后，递归地继续处理剩余的问题子空间。撤销选择（Unchoose）：如果当前的选择无法得到有效解（或已完成当前分支的搜索），则撤销这个选择，回到上一步状态，尝试列表中的其他选择。适用场景回溯算法通常适用于以下类型的问题：组合问题：从给定的元素集合中选取若干个元素，组成满足特定条件的组合。例如，从 n 个不同元素中选取 k 个元素的所有组合。排列问题：对给定的元素集合进行全排列，找出所有可能的排列方式。例如，生成 n 个不同元素的全排列。子集问题：找出给定元素集合的所有子集。棋盘问题：如八皇后问题，在一个 8×8 的棋盘上放置八个皇后，使得它们互不攻击。路径搜索问题：在图或迷宫中寻找满足特定条件的路径。算法框架回溯算法的一般代码框架如下所示。该框架清晰地展示了“做选择 - 递归 - 撤销选择”的逻辑闭环：// 用于存储最终结果 List<SolutionType> result = new ArrayList<>(); public void backtrack(路径，选择列表.html) { if (满足结束条件.html) { result.add(路径.html); return; } for (选择 : 选择列表.html) { // 做选择 路径.add(选择.html); // 进入下一层决策树 backtrack(路径，新的选择列表.html); // 撤销选择 路径.remove(选择.html); } }示例分析全排列问题问题描述：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。代码实现：import java.util.ArrayList; import java.util.List; public class Permutations { // 存储最终结果 List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> permute(int[] nums.html) { // 用于存储当前排列路径 List<Integer> path = new ArrayList<>(); // 标记元素是否已经使用 boolean[] used = new boolean[nums.length]; backtrack(nums, path, used.html); return result; } private void backtrack(int[] nums, List<Integer> path, boolean[] used.html) { // 满足结束条件：当前排列的长度等于数组的长度 if (path.size(.html) == nums.length) { // 注意：需要添加路径的拷贝，而非引用 result.add(new ArrayList<>(path.html)); return; } for (int i = 0; i < nums.length; i++.html) { // 如果元素已经使用过，则跳过 if (used[i].html) continue; // 做选择 path.add(nums[i].html); used[i] = true; // 进入下一层决策树 backtrack(nums, path, used.html); // 撤销选择 path.remove(path.size(.html) - 1); used[i] = false; } } public static void main(String[] args.html) { Permutations permutations = new Permutations(); int[] nums = {1, 2, 3}; List<List<Integer>> result = permutations.permute(nums.html); for (List<Integer> permutation : result.html) { System.out.println(permutation.html); } } }代码解释result：用于存储最终生成的所有全排列结果。path：用于存储当前递归层级正在构建的排列路径。used：一个布尔数组，用于标记数组中的元素是否已经在当前路径中被使用，避免重复选择。backtrack 方法：结束条件：当 path 的长度等于数组长度时，说明已经得到一个完整的排列，将其拷贝后添加到 result 中。选择与递归：遍历数组中的每个元素，如果该元素未被使用，则将其添加到 path 中，标记为已使用，然后递归调用 backtrack 方法。撤销选择：递归返回后，必须撤销当前的选择（将元素从 path 中移除，并标记为未使用），以便后续分支可以使用该元素。复杂度分析时间复杂度：回溯算法的时间复杂度通常是指数级的，因为它需要遍历所有可能的解空间。对于全排列问题，时间复杂度为 $O(n!.html)$，其中 $n$ 是数组的长度。空间复杂度：主要用于存储路径变量和递归调用栈的空间。忽略存储结果的空间，空间复杂度为 $O(n.html)$，其中 $n$ 是数组的长度。
引言本文是系列文章的最后一部分，主要介绍如何实现持久化 List 的最后一步：实现 Transient（临时可变）及持久化功能。如果您尚未浏览过本系列的前序文章，建议先参考以下内容以建立背景知识：持久化数据结构简介Vector Trie 的实现Transient 及持久化 (本文.html)在前文中，我们已经了解了如何实现一个 Vector Trie，以及如何利用它来构建共享数据结构的持久化 List。其核心思路是：在每次修改时，复制从根节点到被修改节点路径上的所有节点，并使用新的 Root 节点构造一个新的 List HEAD 数据结构。这样，通过新的 HEAD 可以访问新数据，而旧的 HEAD 仍能保留旧数据的状态。基于这一思路，我们需要调整 List 的接口设计。对于每一个会修改 List 元素的操作，都必须返回一个新的 List 对象，而非在原对象上直接修改。例如：type List interface { Get(n int.html) (interface{}, bool.html) Set(n int, value interface{}.html) (List, bool.html) PushBack(value interface{}.html) List RemoveBack() (List, interface{}.html) Len() int }为了实现上述接口，我们主要有两种方案：直接返回新对象：对于 Set、PushBack 和 RemoveBack 函数，直接修改实现逻辑，使其返回新的 listHead。引入 Transient 机制：先实现 TransientList，对于修改操作，先将当前 List 转换为 TransientList 进行修改，最后将结果持久化返回。虽然基于之前的代码设计，两种方案的实现难度差别不大，但考虑到 Transient 支持对数据结构进行一连串高效操作，我们决定采用第二种方案。这不仅性能更优，也能使代码更简洁、复用程度更高。那么，什么是 Transient？下面我们将详细介绍其原理与实现。Transient 的原理前文提到，持久化数据结构的实现原理是“路径复制”（Path Copying）。在我们的设计中，每个节点的宽度为 32。如果连续修改几个相邻的元素，即使它们位于同一个叶子节点上，该节点也会被反复复制。这种行为在批量修改场景下是非常低效的。为了高效地进行一连串修改，一种解决方案是允许持久化数据结构临时转变为非持久化（Mutable）状态。在这一连串修改完成后，再将其转变回持久化状态。这样，中间的每次修改都可以在原地进行（In-place），从而极大地改善性能。这种临时产生的非持久化数据结构，就是我们所说的 Transient。风险与权衡使用 Transient 存在一定的风险：线程安全：作为一种可变数据结构，Transient 通常是非线程安全的。并发操作可能导致竞态条件（Race Condition）。持久性破坏：如果用户在将 Transient 转变为持久化对象后，仍然保留了对该 Transient 的引用并继续修改它，那么生成的持久化对象实际上也会被改变。这意味着引入 Transient 可能会导致持久化对象的不可变性被破坏。尽管存在风险，但考虑到性能上的显著提升，引入 Transient 仍然是值得的。其实现依赖于两个关键点：唯一 ID 标记：为每个 Transient 分配一个全局唯一的 id。当 Transient 修改内部结构时，确保所有修改过的节点都打上这个 id 作为标记。所有权检查：当 Transient 需要修改节点时，先检查目标节点的 id 是否与自身相同。如果相同：说明该节点是当前 Transient 之前已经修改或复制过的，可以直接在原节点上修改。如果不同：说明该节点可能属于之前的某个 Transient 或持久化对象。为了防止污染原有数据，必须先复制当前节点，再进行修改。这两条策略保证了我们可以安全地修改 Transient 而不会意外改变原来的数据。关键在于，通过为 Vector Trie 的节点打上 id 标志，Transient 可以判断节点的内存所有权。对于 id 不一致的节点，它们属于历史版本，不应直接修改；而 id 一致的节点，表明是当前 Transient 新近修改过的，可以再次修改。这一步基于一个假定：持久化过的 Transient 不再会被使用者修改。这也是为什么若 Transient 持久化后仍被修改，会导致持久化对象不可变性被破坏的原因。下图对比了持久化 List 和 Transient 在执行修改时的差异：上方（不使用 Transient）：右边三种不同颜色代表连续的三次修改。每次修改都会产生一个新的 Root 节点和一份新的叶子节点，效率较低。下方（使用 Transient）：每个节点包含一个 ID（图中紫色标记）。第一次修改时，为 Transient 分配新 ID b。检查发现目标节点 ID 为 a，与当前 ID 不同，因此需要复制。在接下来的两次修改中，由于 Transient 生命周期内 ID 不变，目标节点 ID 已与当前 Transient 一致，因此无需再复制，可直接进行原地更新。结构复用由上述原理可知，Transient 和持久化 List 可以共享一套底层数据结构，差别仅在于 Transient 拥有一个 ID 而 List 没有。为了区分这两种情况，我们为所有的 List HEAD 分配一个特殊的 ID（例如 0）。List 和 Transient 之间的转换可以通过以下手段实现：List 转 Transient：使用 ID 生成器生成一个唯一且不同于 List ID 的 ID（如正整数）并分配给 List。Transient 转 List：将 Transient 的 ID 重置为 List ID（如 0）。在 Go 语言中，得益于其特殊的类型设计，我们可以将 List 内部数据结构实现为 Transient 内部数据结构的一个衍生类型（基于相同底层结构），从而方便地进行类型转换。Transient 的实现Unique ID 生成器的实现对于 Transient 而言，如何为每次修改生成独一无二的 ID 至关重要。现实中存在多种唯一 ID 生成算法，有的适用于分布式，有的轻量级。在这里，我们选择最简单的方式：累计 uint64 类型的正整数。通过在单例情况下累计正整数，我们可以保证生成的 Unique ID 在当前进程中具有唯一性。其原理是通过 sync/atomic 包下的原子操作 AddUint64 来实现递增。这一操作既快速又线程安全。以下是实现这一功能的内部包 counter：package counter import "sync/atomic" var id uint64 = 0 func Next() uint64 { return atomic.AddUint64(&id, 1.html) }List 接口的更新前文提到，可以将 List 实现为基于 Transient 结构的类型。在这一步，我们将之前实现的 List 内部数据结构重命名为 tListHead，代表它是 Transient List 的 Head，之前实现的方法也一并转移过来。此外，我们需要在新的 tListHead 和内部的 Trie 树节点上都添加 ID 字段：// Transient List Head type tListHead struct { id uint64 len int level int offset int root *trieNode tail *trieNode } // Trie Node type trieNode struct { id uint64 children []interface{} }然后我们重新定义 List 的接口和实现方法：type List interface { Get(n int.html) (interface{}, bool.html) Set(n int, value interface{}.html) (List, bool.html) PushBack(value interface{}.html) List RemoveBack() (List, interface{}.html) TransientList() TransientList Len() int } type listHead tListHead新的接口不再是在原来的基础上进行修改，而是每次操作都返回新的 List 对象。我们还添加了一个方法 TransientList 用于将当前 List 转换为一个 Transient。注意到 listHead 只是基于 tListHead 定义的新类型，因此在 Go 语言中它们之间可以相互类型转换。接下来我们定义一个全局公共的 empty 变量代表空的 List。由于我们希望所有的空 List 都一样，且持久化 List 是不会被改变的，因此我们并不会在 New 时创建新的空对象，而是每次都返回这一个对象。这样也节约了新建 List 时的内存消耗。var empty = &listHead{0, 0, 0, 0, nil, nil} func New() List { return empty }List 的 Get 方法因为不会改变元素的值，我们直接通过类型转化的方法将 listHead 转换为 tListHead 并调用后者的对应方法获得结果：func (head *listHead.html) Get(n int.html) (interface{}, bool.html) { return (*tListHead.html)(head.html).Get(n.html) }对于其它修改操作，我们都先将其转换为 Transient，执行完修改操作之后再持久化回来，这样就可以获得新的 List 了。func (head *listHead.html) Set(n int, value interface{}.html) (List, bool.html) { t := head.TransientList() if t.Set(n, value.html) { return t.Persist(), true } else { return head, false } } func (head *listHead.html) PushBack(value interface{}.html) List { t := head.TransientList() t.PushBack(value.html) return t.Persist() } func (head *listHead.html) RemoveBack() (List, interface{}.html) { if head.len == 1 { value, _ := head.Get(0.html) return empty, value } else { t := head.TransientList() value := t.RemoveBack() return t.Persist(), value } }下面给出了 TransientList 方法的实现。由于 List 的不可变性质需要被保留，因此转化为 Transient 实际上需要新建立一个 tListHead，这样对于 Transient 的修改就不会影响到原来的 List。这里调用了之前实现的 counter 包来获得 Unique ID。func (head *listHead.html) TransientList() TransientList { id := counter.Next() return &tListHead{id, head.len, head.level, head.offset, head.root, head.tail} }Transient 修改操作的实现接下来还需要更新 Transient 修改操作的实现，以保证不会影响到其它 Transient 以及之前的持久化 List。之前的 List 在实现过程中已经部分考虑了这个问题，大部分操作被设计为递归执行，同时对 Trie 树的递归操作会赋值给原来节点。在这一基础上，我们首先为 trieNode 添加 clone 和 setChild 两个方法。clone 方法会将当前节点的内容复制一遍并返回新的节点，它接受一个 id 参数，新复制出来的节点的 id 属性会被设定为该参数。func (node *trieNode.html) clone(id uint64.html) *trieNode { children := make([]interface{}, NODE_SIZE.html) copy(children, node.children) return &trieNode{id, children} }setChild 则是方便实现修改节点功能的函数，它的第一个参数也是 id。如果传入的 id 与节点原来的 id 相同，则这一方法直接在原来的节点上进行修改并返回原来的节点；否则它将会 clone 节点并在新的节点上进行操作。func (node *trieNode.html) setChild(id uint64, n int, child interface{}.html) *trieNode { if node.id == id { node.children[n] = child return node } else { newNode := node.clone(id.html) newNode.children[n] = child return newNode } }之前 List 修改操作的各个内部函数也都被加上了 id 作为参数。除此之外，如果 Set 前后 List 包含值相同，我们希望实际效果是对象没有被修改，在这一步我们也做了一些小心操作来尽可能保证。具体的代码不再赘述，完整的代码请参考 这个文件。下面是将 Transient 转化为持久化的函数。由于我们预期用户在将 Transient 持久化之后不会再修改原来的 Transient（尽管无法从代码上强制保证），所以我们可以简单地使用类型转换来将 tListHead 转换为 listHead，并将 ID 重置。func (head *tListHead.html) Persist() List { persistHead := (*listHead.html)(head.html) persistHead.id = 0 return persistHead }总结本文介绍了 Transient 的实现原理和最终实现持久化 List 的方法。可以看出，Transient 是为了提高持久化 List 在连续修改操作下的效率而引进的数据结构，同时引入 Transient 也会简化持久化 List 实现的复杂度。但是，如果用户以不正确的方式使用 Transient（例如持久化后继续修改），可能会破坏持久化 List 的不可变性。在 Transient 存在的情况下，持久化 List 的修改操作被实现为：先转换为 Transient 并修改，最终将 Transient 持久化。
简介在此前的系列文章中，我们从基本原理出发，一步步实现了基于 Vector Trie 的持久化 List 数据结构。接下来，我们将研究如何使用 HAMT（Hash Array Mapped Trie）这一数据结构来实现持久化 Hash Table。在 持久化数据结构简介 这篇文章中，我们对比了各种可用于实现持久化数据结构的方案，详细介绍了 Vector Trie 及其在实现 List 时的优势。HAMT 的全称是 Hash Array Mapped Trie，它和 Vector Trie 一样，都利用了前缀树（Trie）作为底层数据结构。但由于 Map 和 List 性质的差别，HAMT 在很多方面进行了特别处理。接下来我们先从原始 Hash Table 数据结构谈起，逐步引出 HAMT 的设计原理。Hash TableHash Table 是利用对象的 Hash 值对所储存的键进行散列，从而实现快速插入、删除和访问的数据结构。Go 语言中的 map、Java 中的 HashTable 和 HashMap 以及 Python 当中的 dict 都是 Hash Table 的一种实现。其基本原理是通过某一 Hash 函数将对象映射在虚拟空间上的一个点，并以此为依据将对象保存在内存的固定位置上。当需要访问这一对象时，依然使用同一 Hash 函数计算出对象可能存在的位置，并尝试取出。关于 Hash 和 Hash Table 的概念不再赘述，在这里我们主要关注设计实现 Hash Table 所需要处理的几个关键问题：Hash 碰撞问题：由于 Hash 函数是通过将对象映射到某一数值的方式获得对对象的一个快速描摹，因此尽管我们可以断言 Hash 值不同的对象一定不同，但是并不能保证具有相同 Hash 值的对象一定相同。在实际应用中遇到 Hash 碰撞时，就需要进行处理。时间效率问题：对于所有数据结构来说，时间效率都是非常重要的考量因素。Hash Table 从理论上来说的均摊时间复杂度很好，但是仍然需要考虑在某些极端条件下的执行性能，以保证在各种情况下算法的时间效率不会退化。空间效率问题：一般来说，我们不能将 Hash 函数值域整个在内存中一次分配出来。一来这样做在存入元素很少的情况下非常浪费，二来我们构造的 Hash 函数值域范围很大，一般无法直接分配。因此需要一种方法将空间使用压缩到合理的范围，同时保持一定的空间效率。并发同步问题：和 List 一样，在现代多核盛行的计算环境内，Hash Table 实现的并发安全性也是一个重要的考虑因素。Hash Table 的插入、访问和删除操作往往包含好几步连续的操作，如果不能保证这些步骤原子地完成，就可能会产生无法预计的结果。以上四点在实现 Hash Table 的过程当中是互相联系的。比如说 Hash 碰撞问题就与时间效率和空间效率两个方面紧密相连。一般来说，Hash 碰撞越多，Hash Table 的时间效率越差。根据碰撞处理策略的不同，还有可能影响空间效率。反过来，如果空间分配得比较多，尽管空间效率下降，但是往往可以缓解 Hash 碰撞的概率，因此改善时间效率。并发同步问题也与上述问题紧密相连，譬如说有的 Hash Table 实现在空间不足时需要重新分配空间，这一操作既耗时，又包含很多的指令，对于并发安全提出了很高的要求。HAMT 在以上四个方面都给出了极佳的解决方案，很多学者将其称为理想（Ideal）的 Hash Table 实现。在接下来介绍 HAMT 的原理之前，我们先给出在本文中对 Hash 函数的一些假定：Hash 函数的值是 int32 类型。Hash 函数的值域是 int32 类型的范围。对于两个不同的对象，总可以找到一个 Hash 函数使二者 Hash 值不同。HAMT 原理简介之前介绍了 Vector Trie 实现的持久化 List，如果将这种 List 作为基础，直接套用传统 Hash Table 的实现方法，其实就可以实现持久化的 HashMap 了。但是这种解决方案在时间效率、空间效率上都比较差。Hash Table 和 List 的一个区别在于 Hash Table 当中保存的元素是散列和稀疏的，不像 List 那样从下标 0 一直排列到 n。然而只要把 List 当中下标必须连续的限制条件去掉，Vector Trie 本身就变成了一种相对传统 Array 更好的容器。下图表示的 Vector Trie 说明了这一点：由上图可见，在 Vector Trie 表示的 Hash Table 中，每个元素的 Hash 值的范围是 0 (00 00 00 00.html) 到 255 (11 11 11 11.html)。此时 Hash Table 当中只有两个元素，其中一个 Hash 值是 0，另一个为 255。在传统 Array 实现的 Hash Table 当中，我们需要分配一个长度 256 的数组来保存。而使用 Trie 只需要 7 个节点，共计 28 个单位的空间，其它位置因为没有元素存在，那些节点可以直接节省掉。这说明应用 Trie 树可以在节约空间效率方面具有很好的表现。事实上依靠 Trie 树我们可以直接把 0 到 2^32 - 1 (即 int32.html) 范围的空间表示出来而不用直接分配全部内存——只有存在元素的分支会被按需地分配出来。事实上，Trie 树是线性空间上稀疏数组的一种很好的表示形式。在引入 Trie 树作为数组的稀疏表示之后，我们已经大幅地提高空间效率并得到了不错的时间效率。尽管查询 Trie 树比直接访问数组更慢一些，但是由于我们表示的 Hash 空间足够宽广，在实际应用中遇见碰撞的概率极低，因此在时间效率上还是很有竞争力的。至此，在 Vector Trie 的基础上我们得到了通往 HAMT 的第一步：将元素的 Hash 值按位分割成固定宽度的序列，在 Trie 树上以这些序列按顺序查找元素应该存放的位置。然而 HAMT 并不止步于此，从图中容易看出，我们还有两种优化方案可以达到更好的空间时间效率：节约单个节点当中空间的浪费：许多 Trie 节点中仍然有非常多的空位，设法将这些空位清除可以节省很多空间。削减 Trie 树的高度：保存在树中的两个元素的 Hash 值从第一位开始就不相同，理论上只需要检查最前面的几位就可以区分。只使用 Hash 值中较高的比特位既可以节约空间，又可以提高时间效率。在这两个方向，HAMT 都提出了不错的优化方案。节点内部空间的压缩如果我们依然使用固定 32 个元素宽度的 Trie 树节点，那么必然可能出现由于存入的元素比较稀疏而存在大量空位的现象，为此我们要对节点内部空间进行压缩。压缩的方法是：为每一个节点添加一个 int32 类型的 Bit Map 字段，当这个字段某一比特位值为 1 代表在当前节点上对应的子节点出现了，否则则代表没有出现。我们保存子元素时不再保留空间的空闲位置，而是将所有的子元素一个挨一个地紧密放置，在存取时利用上一步添加的字段计算出所需的是哪一个子节点。为了更清楚地解释上述做法，下面的示意图描绘了进行节点内部压缩前后的节点内部结构：由上图可以看到，虽然压缩后的节点多增加了一个用于保存 Bit Map 的字段，但是由于省略了 6 个空置空间，所以整体的内存消耗大大降低了。要在压缩过的节点当中完成跟原来一样的查询逻辑，我们要建立压缩前后节点之间的对应关系。在未压缩的节点中，由于每个子节点就在它序号所指定的内存位置，所以我们可以直接用下标访问它；在压缩过的节点中这一性质不再有效，我们需要使用新增的 Bit Map 字段将节点的内存位置计算出来。由上图可以看到，压缩前后子元素的相对顺序并没有改变，仍然是按照从小到大的顺序排列起来的，这一点非常重要。根据这个性质，我们可以给出如下的算法：如果指定序号在 Bit Map 字段中对应的比特位为 0，表明并不存在给定序号的子元素，因此可以立刻返回空值。如果指定序号在 Bit Map 字段中对应比特位为 1，则元素存在且它在压缩后节点中的位置下标等于在其之前出现的子元素的数量。第二条其实很好理解，因为压缩后元素的相对顺序不变，只是将空余空间剔除，因此如果从零开始编号，设在所查询子元素之前出现的元素数量为 n，那么所查询子元素就是第 n+1 个元素，因此其下标恰好是 n。利用 Bit Map 和位运算我们可以快速地计算出 n 的值。譬如说，我们要查询在原节点中下标为 i 的元素，首先我们看一下 Bit Map 第 i 位的值是否为 1。方法是使用位运算 (B >> i.html) & 1，其中 B 是 Bit Map 字段的值。如果检查结果为 1，说明元素存在，我们进一步计算它的位置。显然，当前元素之前的元素数量 n，就等于 Bit Map 当中从 0 到 i - 1 (包含两端.html) 位比特位当中 1 的数量。我们首先用 B & ((1 << i.html) - 1) 将那些位单独取出来并将其他位置设为 0。其中，(1 << i.html) - 1 得到的是 0 到 i - 1 位全为 1，其他位全为 0 的一个整型值。得到这个结果之后，我们还需要把其中的 1 的数量计算出来。这一操作在计算机科学当中被称为 Pop Count，进行这样的计算所得到的值又称为 Hamming Weight。Pop Count 是一种非常常用的操作，因此存在很多相关研究，有的 CPU 指令集 (如 x86.html) 还添加了专门的指令用于执行这一操作。除了直接使用指令集或者简单地逐个计数，Hamming Weight 的快速计算有很多方法，下面的代码给出了在 int32 类型上快速计算 Pop Count 的一种实现方法：const uint32_t m1 = 0x55555555; //binary: 0101... const uint32_t m2 = 0x33333333; //binary: 00110011.. const uint32_t m4 = 0x0f0f0f0f; //binary: 4 zeros, 4 ones ... const uint32_t m8 = 0x00ff00ff; //binary: 8 zeros, 8 ones ... const uint32_t m16 = 0x0000ffff; //binary: 16 zeros, 16 ones ... //This uses fewer arithmetic operations than any other known //implementation on machines with slow multiplication. int popcount32(uint32_t x.html) { x -= (x >> 1.html) & m1; //put count of each 2 bits into those 2 bits x = (x & m2.html) + ((x >> 2.html) & m2); //put count of each 4 bits into those 4 bits x = (x + (x >> 4.html)) & m4; //put count of each 8 bits into those 8 bits x += x >> 8; //put count of each 16 bits into their lowest 8 bits x += x >> 16; //put count of each 32 bits into their lowest 8 bits return x & 0x7f; }关于 Pop Count 的计算本文不再赘述，相关内容可以参考 Wikipedia 上详细的介绍和计算方法的对比。由于在 HAMT 当中 Pop Count 是一个非常常用的操作，因此它的性能对最终实现的 Hash Table 的性能有显著的影响。在实现 HAMT 时，一定要根据目标平台的特点，选择合适的实现方法，可能的话应该直接使用 CPU 指令集支持的指令进行计算。在获得到子元素在压缩后节点的内存下标之后，我们就可以像原来一样对节点进行查询访问了。压缩 Trie 高度在节点内部空间之外另一个可以节省空间的地方是 Trie 树的高度。前面在利用这个 int32 宽的 Hash 值构造 Trie 树将我们的对象放置在内存中索引起来，那么一个容易想到的优化就是在不产生混淆的情况下，我们没有必要一定使用 Hash 值的每一个二进制位。也就是说，如果 Hash 值的较高的一部分二进制位已经可以在我们的 Hash Table 中唯一地标记这个对象了，我们就不再利用后面的比特位。下图展示了对 Trie 树高度的压缩。在左边的原始 Trie 树中存放了 Hash 值为 0 (00 00 00 00.html) 和 127 (01 11 11 11.html) 的两个对象，中间是压缩高度的 Trie 树。我们看到，由于当前 Hash Table 中只有两个元素，而这两个元素的 Hash 值从最开始就是不一样的，所以在压缩之后，从高位开始第二位之后的 Hash 值不再被使用。同理，在添加和删除新的对象的时候，我们还需要动态地维护树的高度，在合适的时候增加或者减少树的高度。最右边的图展示了在 Hash Table 中插入 79 (01 00 11 11.html) 之后 Trie 树的结构。可以看到，因为新的节点插入，最高位 01 两个比特位指代的对象出现了混淆，不能唯一地确定一个对象，因此我们要进一步地利用剩下的比特位来构造无混淆的树。由于对 Trie 的各种操作都是基于树上节点的访问，对 Trie 高度进行的压缩不单节约了内存空间，也提高了查询和访问的性能。基本操作的实现在熟悉了 HAMT 在原始的 Trie 表示上做了哪些优化之后，我们就可以给出在 HAMT 实现的 Hash Table 上进行各种操作的基本思路了。查询操作查询操作和在 Trie 上进行查询没有太大的改变，只是因为节点的空间被压缩之后，需要先通过 Bit Map 字段判断对应的位置是否存在子元素。如果存在，再通过 Pop Count 计算得到子元素所在的实际位置。在获得到子元素之后，鉴于 HAMT 对 Trie 的高度进行了压缩，我们要先判断这个子元素是 Trie 的子节点还是值元素本身。对于 Hash Table，我们将值包装成 <Key, Value> 这样的一个值节点存放进去。这样取出时就可以先判断 Key 的值是否相同，以此决定是否真的取到了对象。加入操作加入操作类似于查询操作，对于给定的键值对，我们先计算键的 Hash 值，然后从高位开始利用 Hash 值，沿着 Trie 树向下查找，此时存在四种情况：查找到一个位置，这个位置所保存的值对象代表的键和新插入的键相同，则用新插入的值代替原来的值。查找到一个子节点，这个子节点再向下目标对象应该所在的位置没有元素，此时只需申请一个新的宽度比当前子节点多 1 的节点，将原来子节点上的所有元素连带当前对象一一设置到新的子节点上，维护好元素的顺序和 Bit Map 的值即可。查找到一个子节点，这个子节点再向下目标对象所应该在的位置是一个值对象，这时，为这个值对象连带当前对象分配一个宽度为 2 的子节点，将原来的值对象和当前对象放置在新的节点中，最后用新的节点在当前子节点中替换掉对应位置。查找到一个子节点，这个节点再向下目标对象所应该在的位置是另一个子节点，则在那个子节点上递归进行上述操作。在以上几种情况外，还有一种情况即为出现 Hash 值碰撞。也就是说，当前想要插入的值和 Hash Table 当中某一个对象的 Hash 值完全一样，这样即使两个对象的 Hash 值全部用尽，也无法不混淆地存放两个对象。这时就需要进行碰撞处理。对于 HAMT 来说，常见的碰撞处理有些类似于加盐 Hash 的过程。理论上来说，一个良好设计的 Hash 函数本身的碰撞概率就极小，如果两个元素确实在某次计算中 Hash 碰撞，在两个元素上追加某段已知的固定数据，再进行 Hash 所得的结果极有可能不再碰撞。因此我们可以利用这一特点，当两个对象 Hash 值相同，我们追加一个值，再进行一次 Hash，利用得到的新 Hash 值接着在 Trie 上执行插入即可。如果出现了两个不同的对象，无论怎么 Hash，都得到一样的值，那么要么表明使用的 Hash 函数本身是有问题的，要么说明容器的实现存在问题。这时就应该直接报错了。删除操作删除操作是加入操作的逆运算，其基本原理也类似。在删除时，先在 Trie 中找到对应的对象，然后依次递归地删除。在从子节点删除一个元素时，我们也一样要分配一个新的子节点，这个子节点的宽度比原来少 1。之后将剩余的子元素按照规则放回新的子节点并维护 Bit Map 字段的值。最后用新的子节点替换原来的节点并递归向上进行。一般来讲，在递归时有如下几个情况：在子节点进行删除操作之后，子节点不再包含任何子元素，则删除当前子节点并返回空。当前子节点只剩下一个元素，且这个元素为值元素，则应该降低树的高度，直接返回值元素。当前子节点只剩下一个元素，且这个元素是子节点，则保留这个子节点，回到上一个节点。持久化 HAMT由于 HAMT 本质上还是 Trie，因此我们可以按照之前 Vector Trie 一样的策略来实现持久化。简单来说还是在需要修改节点时，不对原来的节点进行直接的修改，而是生成新节点并复制节点到根的路径。同样，通过在节点中添加 id 字段，我们也可以在 HAMT 上实现 Transient 以加快批量操作的速度。总结在按照上述介绍的空间压缩方法和 Trie 操作方法实现了 HAMT 之后，还有一些问题需要注意：从算法分析上来讲，HAMT 的各项操作时间复杂度都在常数级别内，但是如前文所提，仍需要注意 Pop Count 等操作的时间花费，尽量针对不同平台选用性能最高的实现方案。HAMT 不像传统的 Hash Table 那样集中地分配大量空间，而是在每次加入和删除时重新生成子节点并分配小块的空间，因此内存申请的时间花费在这里不可以被忽略。事实上，Benchmark 表明 HAMT 的一般实现当中内存管理花费的时间是最显著的。在这种情况下，由容器自己维护一个内存池是必要的。也就是说，在每次生成新的节点时，并不直接申请新的内存，而是先从内存池当中尝试获取一个目标宽度的子节点。同理，在释放一个子节点的时候也是将节点返回给这一内存池。线程安全的内存池的实现又是另外一个巨大的主题了，这里也不再赘述。HAMT 的设计是针对像 C 或 C++ 这样完全面向内存、可以细粒度控制数据结构在内存中布局的编程语言设计的，因此在 JVM 和 Golang 这种比较远离硬件的编程语言上进行实现，内存的痕迹和操作的性能均可能不能达到真正的理想状态。近期有一篇名为 Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections 的论文讨论了在 JVM 上优化 HAMT 的实现，有兴趣的读者可以进一步阅读。说明本文内容基于 HAMT 经典理论整理，文中引用的 JVM 优化论文发表于 2015 年（OOPSLA15）。虽然核心原理依然适用，但在具体语言版本（如 Java、Go）的最新特性上可能有所变化，实际实现时请参考对应语言的最新文档。
分治法详解分治法（Divide and Conquer）是一种核心的算法设计策略。其核心逻辑是将一个复杂的问题分解为多个规模较小、相互独立且结构与原问题相似的子问题，递归地解决这些子问题，最后将子问题的解合并，从而得到原问题的解。基本思想分治法的核心思想可概括为“分而治之”，主要包含以下三个步骤：分解（Divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。解决（Conquer）：若子问题规模较小且易于解决，则直接求解；否则，递归地解各个子问题。合并（Combine）：将各个子问题的解合并为原问题的解。适用场景分治法通常适用于满足以下条件的问题：问题可分解：原问题能够被分解为多个规模较小的子问题，且这些子问题的结构与原问题相似。子问题独立：子问题之间没有依赖关系，可以独立求解。解可合并：子问题的解能够通过某种方式合并，从而得到原问题的解。常见的应用场景包括排序算法（如归并排序、快速排序）、矩阵乘法、最近点对问题等。算法框架以下是分治法的一般代码框架（Java 示例）：public class DivideAndConquer { public static ResultType divideAndConquer(ProblemType problem.html) { // 分解问题 if (isSmallProblem(problem.html)) { // 若问题规模小，直接求解 return solveSmallProblem(problem.html); } // 分解问题为子问题 List<ProblemType> subproblems = divideProblem(problem.html); List<ResultType> subresults = new ArrayList<>(); for (ProblemType subproblem : subproblems.html) { // 递归求解子问题 ResultType subresult = divideAndConquer(subproblem.html); subresults.add(subresult.html); } // 合并子问题的解 return combineResults(subresults.html); } private static boolean isSmallProblem(ProblemType problem.html) { // 判断问题是否为小规模问题 return false; } private static ResultType solveSmallProblem(ProblemType problem.html) { // 直接求解小规模问题 return null; } private static List<ProblemType> divideProblem(ProblemType problem.html) { // 分解问题为子问题 return null; } private static ResultType combineResults(List<ResultType> subresults.html) { // 合并子问题的解 return null; } static class ProblemType { // 问题类型的定义 } static class ResultType { // 结果类型的定义 } }示例分析归并排序归并排序（Merge Sort）是分治法的一个经典应用。它将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个有序的数组。public class MergeSort { public static void mergeSort(int[] arr.html) { if (arr == null || arr.length <= 1.html) { return; } int[] temp = new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp.html); } private static void mergeSort(int[] arr, int left, int right, int[] temp.html) { if (left < right.html) { // 分解：将数组分成两个子数组 int mid = left + (right - left.html) / 2; // 递归求解子问题 mergeSort(arr, left, mid, temp.html); mergeSort(arr, mid + 1, right, temp.html); // 合并子问题的解 merge(arr, left, mid, right, temp.html); } } private static void merge(int[] arr, int left, int mid, int right, int[] temp.html) { int i = left; int j = mid + 1; int k = left; while (i <= mid && j <= right.html) { if (arr[i] <= arr[j].html) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid.html) { temp[k++] = arr[i++]; } while (j <= right.html) { temp[k++] = arr[j++]; } for (i = left; i <= right; i++.html) { arr[i] = temp[i]; } } public static void main(String[] args.html) { int[] arr = {5, 4, 3, 2, 1}; mergeSort(arr.html); for (int num : arr.html) { System.out.print(num + " ".html); } } }代码解释mergeSort 方法：首先判断数组是否为空或长度是否小于等于 1，若是则直接返回。调用递归方法，将数组不断分成两个子数组进行排序。merge 方法：负责将两个排好序的子数组合并成一个有序的数组。使用三个指针 i、j 和 k 分别指向左子数组、右子数组和临时数组的起始位置。比较 i 和 j 指向的元素，将较小的元素放入临时数组中，并移动相应的指针。处理剩余元素，将左子数组或右子数组中剩余的元素复制到临时数组中。最后将临时数组中的元素复制回原数组。复杂度分析时间复杂度：归并排序的时间复杂度为 $O(n \log n.html)$，其中 $n$ 是数组的长度。这是因为递归树的深度为 $O(\log n.html)$，而每一层递归中的合并操作总耗时为 $O(n.html)$。空间复杂度：归并排序的空间复杂度为 $O(n.html)$，主要用于临时数组的存储空间。
本文详细介绍算法题常见的解法类型及其核心思想，并提供相应的 Java 代码示例，帮助读者理解不同算法策略的应用场景与实现方式。1. 暴力解法 (Brute Force.html)核心思想 暴力解法是一种直接求解问题的方法。它通常通过枚举所有可能的解，然后逐一检查这些解是否满足问题的条件。这种方法逻辑简单直接，但在处理大规模数据时，时间复杂度较高，效率可能较低。适用场景 适用于问题规模较小，且可能的解空间有限的情况。常用于验证算法正确性或作为优化算法的基准对比。示例问题 给定一个整数数组和一个目标值，找出数组中两个数的和等于目标值的所有组合（索引对）。代码实现import java.util.ArrayList; import java.util.List; public class TwoSumBruteForce { public static List<int[]> twoSum(int[] nums, int target.html) { List<int[]> result = new ArrayList<>(); // 双重循环枚举所有可能的组合 for (int i = 0; i < nums.length; i++.html) { for (int j = i + 1; j < nums.length; j++.html) { if (nums[i] + nums[j] == target.html) { result.add(new int[]{i, j}.html); } } } return result; } public static void main(String[] args.html) { int[] nums = {2, 7, 11, 15}; int target = 9; List<int[]> pairs = twoSum(nums, target.html); for (int[] pair : pairs.html) { System.out.println("Indices: " + pair[0] + ", " + pair[1].html); } } }2. 分治法 (Divide and Conquer.html)核心思想 分治法将一个复杂的问题分解为多个结构相似且相互独立的子问题，然后递归地解决这些子问题，最后将子问题的解合并得到原问题的解。适用场景 适用于问题可以分解为多个相互独立且结构与原问题相似的情况，常见于排序（如归并排序、快速排序）、搜索及大规模数据处理。示例问题 使用分治法实现归并排序（Merge Sort）。代码实现public class MergeSort { public static void mergeSort(int[] arr.html) { if (arr == null || arr.length <= 1.html) { return; } int[] temp = new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp.html); } private static void mergeSort(int[] arr, int left, int right, int[] temp.html) { if (left < right.html) { int mid = left + (right - left.html) / 2; // 递归分解左半部分 mergeSort(arr, left, mid, temp.html); // 递归分解右半部分 mergeSort(arr, mid + 1, right, temp.html); // 合并有序子数组 merge(arr, left, mid, right, temp.html); } } private static void merge(int[] arr, int left, int mid, int right, int[] temp.html) { int i = left; int j = mid + 1; int k = left; // 比较两个子数组的元素，按顺序放入临时数组 while (i <= mid && j <= right.html) { if (arr[i] <= arr[j].html) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 复制剩余元素 while (i <= mid.html) { temp[k++] = arr[i++]; } while (j <= right.html) { temp[k++] = arr[j++]; } // 将临时数组内容拷回原数组 for (i = left; i <= right; i++.html) { arr[i] = temp[i]; } } public static void main(String[] args.html) { int[] arr = {5, 4, 3, 2, 1}; mergeSort(arr.html); for (int num : arr.html) { System.out.print(num + " ".html); } } }3. 动态规划 (Dynamic Programming.html)核心思想 动态规划通过将原问题分解为相对简单的子问题，并保存子问题的解（通常使用数组或表格）来避免重复计算，从而显著提高算法效率。适用场景 适用于具有「最优子结构」和「重叠子问题」性质的问题，如背包问题、最长公共子序列、最短路径等。示例问题 计算斐波那契数列（Fibonacci Sequence）的第 n 项。代码实现public class FibonacciDynamicProgramming { public static int fibonacci(int n.html) { if (n <= 1.html) { return n; } // 创建 dp 数组存储子问题的解 int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; // 自底向上计算 for (int i = 2; i <= n; i++.html) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } public static void main(String[] args.html) { int n = 5; System.out.println("Fibonacci number at position " + n + " is: " + fibonacci(n.html)); } }4. 贪心算法 (Greedy Algorithm.html)核心思想 贪心算法在每一步选择中都采取当前状态下最优的选择，希望通过局部最优解从而达到全局最优解。适用场景 适用于具有「贪心选择性质」和「最优子结构」的问题。注意：贪心策略并不保证对所有问题都能得到全局最优解（例如非标准硬币系统的找零问题），但在特定场景下效率极高，如活动选择问题、哈夫曼编码等。示例问题 给定特定面额的硬币（如标准货币系统）和一个总金额，计算最少需要多少个硬币来组成这个金额。代码实现import java.util.Arrays; public class CoinChangeGreedy { public static int coinChange(int[] coins, int amount.html) { // 先对硬币面额排序，以便从大到小选择 Arrays.sort(coins.html); int count = 0; // 从最大面额开始尝试 for (int i = coins.length - 1; i >= 0; i--.html) { while (amount >= coins[i].html) { amount -= coins[i]; count++; } } // 如果金额未完全凑齐，返回 -1 return amount == 0 ? count : -1; } public static void main(String[] args.html) { int[] coins = {1, 2, 5}; int amount = 11; System.out.println("Minimum number of coins: " + coinChange(coins, amount.html)); } }5. 回溯算法 (Backtracking.html)核心思想 回溯算法通过深度优先搜索（DFS）的方式遍历所有可能的解空间。当发现当前的解不满足问题的条件时，算法会「回溯」到上一步，尝试其他的选择，直到找到所有解或确定无解。适用场景 适用于求解组合、排列、子集等问题，如八皇后问题、全排列问题、数独求解等。示例问题 生成给定数组的所有全排列。代码实现import java.util.ArrayList; import java.util.List; public class Permutations { public static List<List<Integer>> permute(int[] nums.html) { List<List<Integer>> result = new ArrayList<>(); backtrack(result, new ArrayList<>(.html), nums); return result; } private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums.html) { // 当临时列表长度等于原数组长度时，找到一个完整排列 if (tempList.size(.html) == nums.length) { result.add(new ArrayList<>(tempList.html)); } else { for (int i = 0; i < nums.length; i++.html) { // 如果元素已存在，跳过（避免重复使用） if (tempList.contains(nums[i].html)) continue; tempList.add(nums[i].html); // 递归进入下一层 backtrack(result, tempList, nums.html); // 回溯：移除最后一个元素，尝试其他可能 tempList.remove(tempList.size(.html) - 1); } } } public static void main(String[] args.html) { int[] nums = {1, 2, 3}; List<List<Integer>> permutations = permute(nums.html); for (List<Integer> permutation : permutations.html) { System.out.println(permutation.html); } } }说明：本文代码示例基于 Java 标准库编写，适用于 JDK 8 及以上版本。算法逻辑侧重于展示核心思想，实际生产环境中可根据具体数据规模进行性能优化（如回溯算法中使用标记数组替代 contains 检查以提升效率）。
动态规划（Dynamic Programming，简称 DP）是解决多阶段决策过程最优化问题的常用算法思想。本文将结合经典的最长递增子序列（Longest Increasing Subsequence, LIS）问题，详细拆解动态规划解题的四个核心步骤。1. 定义状态定义状态是动态规划解题的基石。它要求明确问题的状态表示以及每个状态所代表的具体含义。通常，状态对应问题的一个子问题，通过对状态的精确定义，我们能将原问题拆解为一系列可求解的子问题。示例：最长递增子序列（LIS）问题问题描述：给定一个无序的整数数组，找到其中最长递增子序列的长度。状态定义：设 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。状态含义：只考虑数组前 i 个元素，且子序列必须以第 i 个元素结尾时的最长递增子序列长度。2. 确定状态转移方程状态转移方程描述了状态之间的递推关系，是动态规划的核心。通过该方程，我们可以从已知的子问题解推导出未知的子问题解。示例：最长递增子序列（LIS）问题对于 dp[i]，我们需要遍历数组中 i 之前的所有元素 j（0 <= j < i）。如果 nums[j] < nums[i]，说明可以将第 i 个元素添加到以第 j 个元素结尾的递增子序列后面，从而形成一个更长的递增子序列。状态转移方程：dp[i] = \max(dp[j] + 1, dp[i].html)其中 0 <= j < i 且 nums[j] < nums[i]。方程含义：对于每个满足条件的 j，计算 dp[j] + 1（即在以第 j 个元素结尾的最长递增子序列后面加上第 i 个元素），并取这些值中的最大值作为 dp[i]。3. 初始化状态初始化状态是为了确定问题的边界条件，即一些最简单子问题的解。这些初始状态将作为后续递推计算的基础。示例：最长递增子序列（LIS）问题由于每个元素自身都可以构成一个长度为 1 的递增子序列，因此初始时，我们将 dp 数组的每个元素都初始化为 1。初始化代码：int[] dp = new int[nums.length]; for (int i = 0; i < nums.length; i++.html) { dp[i] = 1; }4. 计算最终结果在完成状态定义、状态转移方程的确定和状态的初始化后，我们可以根据状态转移方程逐步计算出所有子问题的解，最终得到原问题的解。示例：最长递增子序列（LIS）问题我们需要遍历数组，根据状态转移方程更新 dp 数组的值，最后在 dp 数组中找到最大值，即为最长递增子序列的长度。计算最终结果的代码：public class LongestIncreasingSubsequence { public int lengthOfLIS(int[] nums.html) { if (nums == null || nums.length == 0.html) { return 0; } int n = nums.length; int[] dp = new int[n]; // 初始化状态 for (int i = 0; i < n; i++.html) { dp[i] = 1; } int maxLength = 1; // 根据状态转移方程计算 dp 数组 for (int i = 1; i < n; i++.html) { for (int j = 0; j < i; j++.html) { if (nums[j] < nums[i].html) { dp[i] = Math.max(dp[j] + 1, dp[i].html); } } // 更新最长递增子序列的长度 maxLength = Math.max(maxLength, dp[i].html); } return maxLength; } public static void main(String[] args.html) { LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence(); int[] nums = {10, 9, 2, 5, 3, 7, 101, 18}; int result = lis.lengthOfLIS(nums.html); System.out.println("最长递增子序列的长度是：" + result.html); } }复杂度分析时间复杂度：由于使用了两层嵌套循环，时间复杂度为 O(n^2.html)，其中 n 是数组的长度。空间复杂度：使用了一个长度为 n 的数组 dp 来保存子问题的解，空间复杂度为 O(n.html)。通过以上四个步骤，我们可以使用动态规划解决最长递增子序列问题。对于其他动态规划问题，也可以按照类似的思路进行分析和求解。