戴老师的博客 - 算法与数据结构
type: channel
link: https://1diff.fun/tag/%E7%AE%97%E6%B3%95%E4%B8%8E%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/
items: 持久化数据结构简介
items: 数据类型与 JSON 格式：轻松掌握数据处理的基石
items: Vector Trie 的实现
items: H2的MVStore
items: 回溯算法详解
items: Transient 及持久化
items: HAMT 简介
items: 分治法详解
items: Java算法题类型及解法
items: Java 动态规划算法分析

持久化数据结构简介
type: item
date: 2026-03-30T09:39:03+00:00
description: 这篇文章是系列文章的一部分，如果还没有浏览过文章的其它部分，请参考：持久化数据结构简介（本文）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 改变总是从一个最初的状态衍生而来的一系列状态，在对前后两个状态进行递归的比较时，如果两个对象的引用是一样的，那么它们一定是一个不可变的对象；如果两个对象的引用不一致，那…

数据类型与 JSON 格式：轻松掌握数据处理的基石
type: item
date: 2026-03-30T09:38:15+00:00
description: 在当今数字化时代，数据的高效处理和交换至关重要。无论是构建强大的应用程序，还是实现系统之间的无缝通信，对数据类型和数据格式的深入理解都是关键。本文将探索数据类型的核心奥秘以及 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]) 时，两种情况下的运行结果竟然是相同的！这让我不禁思考，数据集合并没有规定一定要用数组或对象，那么到底该如何选择呢？后来我才明白，数组表示有序数据的集合，就像排队一样，每个元素都有固定的位置；而对象表示无序数据的集合，更像是一个装满物品的袋子，元素之间没有特定的顺序。如果数据的顺序很重要，比如记录学生的考试成绩排名，就用数组；否则，像存储用户的个人信息，用对象会更加合适。（二）数据名称的差异数…

Vector Trie 的实现
type: item
date: 2026-03-30T09:35:23+00:00
description: 这篇文章是系列文章的一部分，如果还没有浏览过文章的其它部分，请参考：持久化数据结构简介Vector Trie 的实现 (本文)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) MASK = NODE_SIZE - 1 )其中，NODE_SIZE 是 List 内部节点的宽度。这里我们选用了通用的 $2^5$，也就是 32 作为 Trie 树节点的宽度。这意味着每个 Trie 树节点最多将有 32 个子节点。SHIFT 和 MASK 这两个常数将在我们实现 Trie 树的过程中被用到。我们将要完成的 List 在 Golang 下的接口定义如下：type List interface { Get(n int) (interface{}, bool) Set(n int, value interface{}) PushBack(value interface{}) 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), } }可以看到目前为止我们的内部节点非常简单，结构体只包含一个数组用来保存子节点。我们要将 List 的值元素保存在 Trie 树最底层的叶子节点，因此使用了 interface{} 这种通用类型的数组。这样我们就既可以使用它指向子节点，又可以用来保存值元素。在这里我为 trieNode 编写了两个方便的工具函数来分别获取子节点和值：func (node *trieNode) getChildNode(index int) *trieNode { if child := node.children[index]; child != nil { return child.(*trieNode) } else { return nil } } func (node *trieNode) getChildValue(index int) 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 结构示意图为了简便起见，图中的 T…

H2的MVStore
type: item
date: 2026-03-30T09:34:17+00:00
description: 概述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) MVStore s = MVStore.open(fileName); // create/get the map named "data" MVMap<Integer, String> map = s.openMap("data"); // add and read some data map.put(1, "Hello World"); System.out.println(map.get(1)); // close the store (this will persist changes) s.close();下面的代码展示了如何使用这些工具构建 Store。Store BuilderMVStore.Builder 提供了一个流畅优美的接口，可通过可选配置项构造 Store。示例用法：MVStore s = new MVStore.Builder(). fileName(fileName). encryptionKey("007".toCharArray()). 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); // 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) // then the min x, max x, min y, max y r.add(new SpatialKey(0, -3f, -2f, 2f, 3f), "left"); r.add(new SpatialKey(1, 3f, 4f, 4f, 5f), "right"); // iterate over the intersecting keys Iterator<SpatialKey> it = r.findIntersectingKeys(new SpatialKey(0, 0f, 9f, 3f, 6f)); for (SpatialKey k; it.hasNext();) { k = it.next(); System.out.println(k + ": " + r.get(k)); } s.close();默认维度是 2，可以通过 new MVRTreeMap.Builder<String>().dimensions(3) 设置不同的维度数。维度的取值最大值是 3…

回溯算法详解
type: item
date: 2026-03-30T09:33:29+00:00
description: 回溯算法（Backtracking）是一种基于深度优先搜索（DFS）的算法策略，旨在通过遍历问题的所有可能解空间，找到满足特定条件的解。在搜索过程中，当发现当前的选择无法得到有效解时，算法会“回溯”到上一步，撤销当前选择，然后尝试其他可能的选项，直到找到所有符合条件的解或遍历完整个解空间。基本思想回溯算法的核心思想可以概括为“尝试所有可能，不行就回头”。其执行过程通常包含以下三个关键步骤：选择（Choose）：在每一步中，从所有可能的选项列表中做出一个选择。递归（Explore）：在做出选择后，递归地继续处理剩余的问题子空间。撤销选择（Unchoose）：如果当前的选择无法得到有效解（或已完成当前分支的搜索），则撤销这个选择，回到上一步状态，尝试列表中的其他选择。适用场景回溯算法通常适用于以下类型的问题：组合问题：从给定的元素集合中选取若干个元素，组成满足特定条件的组合。例如，从 n 个不同元素中选取 k 个元素的所有组合。排列问题：对给定的元素集合进行全排列，找出所有可能的排列方式。例如，生成 n 个不同元素的全排列。子集问题：找出给定元素集合的所有子集。棋盘问题：如八皇后问题，在一个 8×8 的棋盘上放置八个皇后，使得它们互不攻击。路径搜索问题：在图或迷宫中寻找满足特定条件的路径。算法框架回溯算法的一般代码框架如下所示。该框架清晰地展示了“做选择 - 递归 - 撤销选择”的逻辑闭环：// 用于存储最终结果 List<SolutionType> result = new ArrayList<>(); public void backtrack(路径，选择列表) { if (满足结束条件) { result.add(路径); return; } for (选择 : 选择列表) { // 做选择 路径.add(选择); // 进入下一层决策树 backtrack(路径，新的选择列表); // 撤销选择 路径.remove(选择); } }示例分析全排列问题问题描述：给定一个不含重复数字的数组 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) { // 用于存储当前排列路径 List<Integer> path = new ArrayList<>(); // 标记元素是否已经使用 boolean[] used = new boolean[nums.length]; backtrack(nums, path, used); return result; } private void backtrack(int[] nums, List<Integer> path, boolean[] used) { // 满足结束条件：当前排列的长度等于数组的长度 if (path.size() == nums.length) { // 注意：需要添加路径的拷贝，而非引用 result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { // 如果元素已经使用过，则跳过 if (used[i]) continue; // 做选择 path.add(nums[i]); used[i] = true; // 进入下一层决策树 backtrack(nums, path, used); // 撤销选择 path.remove(path.size() - 1); used[i] = false; } } public static void main(String[] args) { Permutations permutations = new Permutations(); int[] nums = {1, 2, 3}; List<List<Integer>> result = permutations.permute(nums); for (List<Integer> permutation : result) { System.out.println(permutation); } } }代码解释result：用于存储最终生成的所有全排列结果。path：用于存储当前递归层级正在构建的排列路径。used：一个布尔数组，用于标记数组中的元素是否已经在当前路径中被使用，避免重复选择。backtrac…

Transient 及持久化
type: item
date: 2026-03-30T09:32:39+00:00
description: 引言本文是系列文章的最后一部分，主要介绍如何实现持久化 List 的最后一步：实现 Transient（临时可变）及持久化功能。如果您尚未浏览过本系列的前序文章，建议先参考以下内容以建立背景知识：持久化数据结构简介Vector Trie 的实现Transient 及持久化 (本文)在前文中，我们已经了解了如何实现一个 Vector Trie，以及如何利用它来构建共享数据结构的持久化 List。其核心思路是：在每次修改时，复制从根节点到被修改节点路径上的所有节点，并使用新的 Root 节点构造一个新的 List HEAD 数据结构。这样，通过新的 HEAD 可以访问新数据，而旧的 HEAD 仍能保留旧数据的状态。基于这一思路，我们需要调整 List 的接口设计。对于每一个会修改 List 元素的操作，都必须返回一个新的 List 对象，而非在原对象上直接修改。例如：type List interface { Get(n int) (interface{}, bool) Set(n int, value interface{}) (List, bool) PushBack(value interface{}) List RemoveBack() (List, interface{}) 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 节点和一份新的叶子节点，效率较低。下方（使用 Transien…

HAMT 简介
type: item
date: 2026-03-30T09:32:34+00:00
description: 简介在此前的系列文章中，我们从基本原理出发，一步步实现了基于 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) 到 255 (11 11 11 11)。此时 Hash Table 当中只有两个元素，其中一个 Has…

分治法详解
type: item
date: 2026-03-30T09:31:02+00:00
description: 分治法详解分治法（Divide and Conquer）是一种核心的算法设计策略。其核心逻辑是将一个复杂的问题分解为多个规模较小、相互独立且结构与原问题相似的子问题，递归地解决这些子问题，最后将子问题的解合并，从而得到原问题的解。基本思想分治法的核心思想可概括为“分而治之”，主要包含以下三个步骤：分解（Divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。解决（Conquer）：若子问题规模较小且易于解决，则直接求解；否则，递归地解各个子问题。合并（Combine）：将各个子问题的解合并为原问题的解。适用场景分治法通常适用于满足以下条件的问题：问题可分解：原问题能够被分解为多个规模较小的子问题，且这些子问题的结构与原问题相似。子问题独立：子问题之间没有依赖关系，可以独立求解。解可合并：子问题的解能够通过某种方式合并，从而得到原问题的解。常见的应用场景包括排序算法（如归并排序、快速排序）、矩阵乘法、最近点对问题等。算法框架以下是分治法的一般代码框架（Java 示例）：public class DivideAndConquer { public static ResultType divideAndConquer(ProblemType problem) { // 分解问题 if (isSmallProblem(problem)) { // 若问题规模小，直接求解 return solveSmallProblem(problem); } // 分解问题为子问题 List<ProblemType> subproblems = divideProblem(problem); List<ResultType> subresults = new ArrayList<>(); for (ProblemType subproblem : subproblems) { // 递归求解子问题 ResultType subresult = divideAndConquer(subproblem); subresults.add(subresult); } // 合并子问题的解 return combineResults(subresults); } private static boolean isSmallProblem(ProblemType problem) { // 判断问题是否为小规模问题 return false; } private static ResultType solveSmallProblem(ProblemType problem) { // 直接求解小规模问题 return null; } private static List<ProblemType> divideProblem(ProblemType problem) { // 分解问题为子问题 return null; } private static ResultType combineResults(List<ResultType> subresults) { // 合并子问题的解 return null; } static class ProblemType { // 问题类型的定义 } static class ResultType { // 结果类型的定义 } }示例分析归并排序归并排序（Merge Sort）是分治法的一个经典应用。它将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个有序的数组。public class MergeSort { public static void mergeSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } int[] temp = new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); } private static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { // 分解：将数组分成两个子数组 int mid = left + (right - left) / 2; // 递归求解子问题 mergeSort(arr, left, mid, temp); mergeSort(arr, mid + 1, right, temp); // 合并子问题的解 merge(arr, left, mid, right, temp); } } private static void merge(int[] a…

Java算法题类型及解法
type: item
date: 2026-03-30T09:29:16+00:00
description: 本文详细介绍算法题常见的解法类型及其核心思想，并提供相应的 Java 代码示例，帮助读者理解不同算法策略的应用场景与实现方式。1. 暴力解法 (Brute Force)核心思想 暴力解法是一种直接求解问题的方法。它通常通过枚举所有可能的解，然后逐一检查这些解是否满足问题的条件。这种方法逻辑简单直接，但在处理大规模数据时，时间复杂度较高，效率可能较低。适用场景 适用于问题规模较小，且可能的解空间有限的情况。常用于验证算法正确性或作为优化算法的基准对比。示例问题 给定一个整数数组和一个目标值，找出数组中两个数的和等于目标值的所有组合（索引对）。代码实现import java.util.ArrayList; import java.util.List; public class TwoSumBruteForce { public static List<int[]> twoSum(int[] nums, int target) { List<int[]> result = new ArrayList<>(); // 双重循环枚举所有可能的组合 for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { result.add(new int[]{i, j}); } } } return result; } public static void main(String[] args) { int[] nums = {2, 7, 11, 15}; int target = 9; List<int[]> pairs = twoSum(nums, target); for (int[] pair : pairs) { System.out.println("Indices: " + pair[0] + ", " + pair[1]); } } }2. 分治法 (Divide and Conquer)核心思想 分治法将一个复杂的问题分解为多个结构相似且相互独立的子问题，然后递归地解决这些子问题，最后将子问题的解合并得到原问题的解。适用场景 适用于问题可以分解为多个相互独立且结构与原问题相似的情况，常见于排序（如归并排序、快速排序）、搜索及大规模数据处理。示例问题 使用分治法实现归并排序（Merge Sort）。代码实现public class MergeSort { public static void mergeSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } int[] temp = new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); } private static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = left + (right - left) / 2; // 递归分解左半部分 mergeSort(arr, left, mid, temp); // 递归分解右半部分 mergeSort(arr, mid + 1, right, temp); // 合并有序子数组 merge(arr, left, mid, right, temp); } } private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; int j = mid + 1; int k = left; // 比较两个子数组的元素，按顺序放入临时数组 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 复制剩余元素 while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } // 将临时数组内容拷回原数组 for (i = left; i <= right; i++) { arr[i] = temp[i]; } } public static void main(String[] args) …

Java 动态规划算法分析
type: item
date: 2026-03-30T09:26:19+00:00
description: 动态规划（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])其中 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++) { dp[i] = 1; }4. 计算最终结果在完成状态定义、状态转移方程的确定和状态的初始化后，我们可以根据状态转移方程逐步计算出所有子问题的解，最终得到原问题的解。示例：最长递增子序列（LIS）问题我们需要遍历数组，根据状态转移方程更新 dp 数组的值，最后在 dp 数组中找到最大值，即为最长递增子序列的长度。计算最终结果的代码：public class LongestIncreasingSubsequence { public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int n = nums.length; int[] dp = new int[n]; // 初始化状态 for (int i = 0; i < n; i++) { dp[i] = 1; } int maxLength = 1; // 根据状态转移方程计算 dp 数组 for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[j] + 1, dp[i]); } } // 更新最长递增子序列的长度 maxLength = Math.max(maxLength, dp[i]); } return maxLength; } public static void main(String[] args) { LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence(); int[] nums = {10, 9, 2, 5, 3, 7, 101, 18}; int result = lis.lengthOfLIS(nums); System.out.println("最长递增子序列的长度是：" + result); } }复杂度分析时间复杂度：由于使用了两层嵌套循环，时间复杂度为 O(n^2)，其中 n 是数组的长度。空间复杂度：使用了一个长度为 n 的数组 dp 来保存子问题的解，空间复杂度为 O(n)。通过以上四个步骤，我们可以使用动态规划解决最长递增子序列问题。对于其他动态规划问题，也可以按照类似的思路进行分析和求解。