Java

多年前，我造过一个轮子，也是多级缓存框架，名字也叫做 Xcache。 多年后，本着重复造轮子的精神，我又造了个新轮子：https://github.com/patricklaux/xcache 因为是新造的轮子，所以看起来似乎更圆了一些，跑起来似乎也更顺滑了一些。 非要自夸一下的话，那就是这么些年的编程生涯，在踩过许多坑之后，编码质量更好了点，架构设计更合理了些。 1. 整体架构 说明： Cache API：缓存接口。 Cache Annotation：缓存注解。 Cache：缓存对象。 Store：缓存数据存储，每个缓存对象实例最多可支持三级缓存数据存储。 Codec：数据编解码（序列化与反序列化）。 Compressor：数据压缩。 CacheLoader：数据加载，用于从数据源读取数据。 CacheRefresh：缓存数据刷新，定时通过 CacheLoader 加载并刷新缓存数据。 CacheSync：缓存数据同步，用于维护各实例间私有缓存数据的一致性。 CacheMetrics：缓存指标采集，用于记录缓存调用次数及命中率等指标。 MetricsSystem：缓存指标信息的存储、计算与展示。 MQ：消息队列，用于转发数据同步消息（已有实现采用 Redis Stream）。 DataSource：数据源。 Redis or Other……：缓存数据存储仓库。 2. 框架特性 支持多级缓存：一级缓存采用 Caffeine，二级缓存采用 Redis，最多可支持三级缓存。 缓存数据同步：通过缓存事件广播，多个应用实例的缓存数据保持一致。 缓存指标统计：支持调用次数、命中次数等指标，数据呈现可自由扩展。 缓存数据刷新：定时自动刷新缓存数据，避免慢查询导致应用响应缓慢。 随机存活时间：可选择使用随机存活时间，避免大量数据集中过期，导致数据源压力过大。 数据回源加锁：同一个键同一时刻仅允许一个线程回源查询，减轻数据源压力。 数据存在断言：可选择实现数据存在断言接口，譬如 Bloom Filter，减少无效回源查询。 支持缓存空值：可选择缓存空值，减少无效回源查询。 缓存数据压缩：可选择数据压缩，降低内存(磁盘)消耗。 支持缓存注解：Cacheable，CacheableAll，CachePut，CachePutAll，…… ，CacheClear 适配 Spring Cache 注解：如希望使用 Spring Cache 注解，可依赖 Xcache 适配项目，即可解锁更多功能。 3. 缓存流程 原则：数据查询顺序从一级缓存到三级缓存，数据写入、删除顺序从三级缓存到一级缓存。 实际应用中，可能只有一级缓存或两级缓存，并不一定有全部三级缓存，这是可配置的。 3.1. 数据查询 流程：按照一级缓存 → 二级缓存 → 三级缓存的顺序依次查询。 图示： 3.2. 数据写入 流程：按照三级缓存 → 二级缓存 → 一级缓存的顺序依次写入。 图示： 3.3. 数据删除 流程：按照三级缓存 → 二级缓存 → 一级缓存的顺序依次删除。 ...

1. 前言 红黑树是一种自平衡二叉查找树（Self-balancing binary search tree）。 如前文所述，根据红黑树的定义去理解其设计思想是非常困难的，但借助 B 树我们却可以更好地理解它，因为红黑树本就是由4阶B树推导而来。 全文较长，但为了完整的阅读体验，所以没有拆分为多篇文章，读者可以根据导图挑选阅读感兴趣的章节。 代码仓库：https://github.com/patricklaux/perfect-code 2. 由来 了解红黑树的由来和变体，有助于更好地理解。 (1) 1972 年，Rudolf Bayer 提出了 “symmetric binary B-tree”，这是B 树的 4 阶情形，也就是 2-3-4树（或称为 2-4 树）1。 (2) 1978 年，Leonidas J. Guibas 和 Robert Sedgewick 从 “symmetric binary B-tree” 推导出红黑树2。 (3) 1993 年，Arne Andersson 引入 “right leaning tree(右倾树)” 的概念来简化插入和删除操作3。 (4) 1999 年，Chris Okasaki 展示了如何使插入操作成为纯函数，只需处理 4 种失衡类型和 1 种默认平衡类型4。 (5) 2001 年，Cormen 等人将原算法的 8 个失衡类型减少为 6 个失衡类型5。 (6) 2008 年，Sedgewick 根据 Andersson 的思想，提出了 “Left leaning red black tree(左倾红黑树)”，这是 2-3 树的等价转换6。 ...

1. 前言 红黑树的实现并不困难，但仅根据其定义去理解背后的设计思想却是相当不容易的。 相比较而言，B树是非常直观且容易理解的，了解B树之后，再去看红黑树，就会发现红黑树其实是4阶B树的一种等价实现，红黑树的查找、插入、删除、着色和旋转都可以在4阶B树中一一找到对应关系。 另外，B树及其变体也广泛地运用于数据库系统，譬如 MySQL、MongoDB……等。 这篇文章中，我会先介绍 B树的由来，接着介绍其定义和概念，然后通过图例和流程图来说明相关操作，最后会给出其代码实现。 代码仓库：https://github.com/patricklaux/perfect-code 2. 由来 B 树是由 Rudolf Bayer 和 Edward McCreight 在波音实验室工作期间提出的，论文 “Organization and maintenance of large ordered indices1” 发表于1972年。 B 树是多叉查找树的一种实现，而多叉查找树是二叉查找树的推广。 与内存相比，磁盘具有持久性、大容量和单位存储价格便宜等优点。 但磁盘相对于内存而言是非常缓慢的，二叉树这种内存数据结构并不能很好地应用于磁盘存储。 磁盘读写以页为单位，分页大小为 4KB 时，读取 1B 数据与 4KB 数据均需一次磁盘I/O，耗时几乎相等。 另外，磁盘顺序读写比随机读写的性能要好得多，当读写连续的数据页时，通常都会有不错的性能表现。 因此，根据磁盘数据读写的这些特点，为减少磁盘I/O，很自然的一个想法就是将多个数据项合并存入到一个节点，节点大小恰好是页大小的整数倍。 如下图所示，多个二叉树节点合并成一个节点，这样二叉查找树就变成了多叉查找树 (M-ary search tree)。 图2.1：节点合并(图片来源于参考资料[2]) 一棵完全二叉树 (complete binary tree) 的层数大约为 \( log_2n \)，一棵完全多叉树 (complete M-ary tree) 的层数大约为 \( log_mn \)，n 为数据记录数。 这意味着，如果有 100万条数据记录，当以二叉树的形式存储到磁盘，搜索一条数据记录约需 20次磁盘I/O： \( log_21000000≈20 \)； 如图2.1 所示，通过将 7个节点合并成一个数据页存储到磁盘，变成一棵 8叉搜索树，那么搜索一条数据记录仅需约 7次磁盘I/O： ...

时隔多年又重新实现了一遍 AVL树，并且进行了深度优化，所以有些心得。 首先，我会介绍6种失衡类型和4种旋转； 然后，重点描述插入和删除的优化实现，并将给出严谨的分析和证明，解释为什么可以这么优化； 最后，我会用 AVL 树与 Java 的 TreeMap (红黑树)进行性能对比，以验证优化结果。 代码仓库：https://github.com/patricklaux/perfect-code 1. 简介 AVL 树是一种自平衡二叉查找树（Self-balancing binary search tree），得名于其两位作者的首字母1： Georgy Adelson-Velsky 和 Evgenii Landis。 相比于二叉查找树最坏情况下时间复杂度为 \( O(n) \)，AVL树查找、插入和删除的平均时间复杂度和最坏时间复杂度均为 \( O(log_2n) \)，其中 n 为树的节点数。 2. 高度与平衡因子 AVL树的平衡性质：其任意节点的左子树和右子树的高度差的绝对值小于等于1。 2.1. AVL节点 private class AvlNode<K, V> { K key; // 键 V val; // 值 byte height; // 高度 AvlNode<K, V> left; // 左孩子 AvlNode<K, V> right; //右孩子 } 2.2. 获取高度 // 空树的高度定义为 -1。 private byte height(AvlNode<K, V> node) { return (node == null) ? -1 : node.height; } 2.3. 更新高度 // 取左右子树的高度的大者再加1，即为父节点的高度 private void updateHeight(AvlNode<K, V> parent) { parent.height = (byte) (Math.max(height(parent.left), height(parent.right)) + 1); } 2.4. 平衡因子 二叉查找树的平衡因子 BF (Balance Factor) 的定义为两棵子树的高度之差。 ...

1. 概述 IDDFS (Iterative deepening depth-first search)：迭代加深搜索，是一种状态空间/图的搜索策略。 其空间复杂度仅为 \( O(d) \)，相比用队列实现层序遍历所需的 \( O(b^d) \) 空间复杂度，极大地节约了空间开销，b 为分支因子，d 为深度。 从三个维度来分析，空间开销、时间性能和求解路径的代价，IDDFS 都接近最优，是一个非常优秀的算法。 本文主要介绍用 IDDFS 算法实现二叉树的层序遍历，如对其它方面的搜索运用感兴趣，可阅读参考资料1。 代码仓库：https://github.com/patricklaux/perfect-code 2. 使用队列实现层序遍历 层序遍历：即为按层顺序访问，所有深度为 d 的节点在深度为 d+1 的节点之前访问——（d, b, f, a, c, e, g）。 使用队列实现层序遍历并不复杂，代码如下： public void levelOrderTraversal(List<Tuple2<K, V>> kvs) { if (root == null) { return; } ArrayDeque<Node<K, V>> queue = new ArrayDeque<>(size.get() / 2); queue.push(root); while (!queue.isEmpty()) { Node<K, V> p = queue.poll(); kvs.add(Tuples.of(p.key, p.val)); if (p.left != null) { queue.offer(p.left); } if (p.right != null) { queue.offer(p.right); } } } 常见的算法书在介绍层序遍历时都采用队列来实现，这种算法被称为标准 BFS。 ...

1. 概述 前一篇文章介绍了深度优先遍历的递归实现和迭代实现，这两种方式的时间复杂度都是 \( O(n) \)，空间复杂度都是 \( O(h) \)，本文将要介绍的 Morris 遍历的时间复杂度依然为 \( O(n) \)，但空间复杂度仅为 \( O(1) \)，其中 n 为节点数，h 为树的高度。 算法来历 1968年，《计算机程序设计艺术》的作者 Knuth 提出了一个问题：设计一个无需堆栈和额外标志域的非递归的中序遍历算法，且当遍历结束时树结构不变。此后，诞生了许多解决方案，而Morris 遍历是其中最优雅的一种（见参考资料1）1。 此算法由 Joseph M. MORRIS 在1979年的论文 “Traversing Binary Trees Simply and Cheaply2” 中首次提出。顺便再说一句，这个 MORRIS 正是大名鼎鼎的 KMP 算法的作者之一。 代码仓库：https://github.com/patricklaux/perfect-code 2. 算法解析 线索二叉树 如果了解线索二叉树的话，肯定对前驱和后继非常熟悉。 通过在二叉树节点增加前驱和后继指针，可以非常方便地进行向前查找、向后查找和遍历等线性化操作，相当于是二叉树和链表的结合。这其中指向前驱和后继的指针称之为线索，而包含线索的二叉树则称之为线索二叉树(Threaded Binary Tree)3。 譬如 Java 的 HashMap 中的 红黑树节点，就增加了 prev 和 next 指针，其节点结构类似如下： class TreeNode<K,V> { TreeNode<K,V> parent; // 父节点 TreeNode<K,V> left; // 左孩子 TreeNode<K,V> right; // 右孩子 TreeNode<K,V> prev; // 前驱 TreeNode<K,V> next; // 后继 boolean red; // 颜色 } 这种方式需要额外内存来保存前驱和后继指针，那么是不是有一些其它方式来避免这个问题呢？ ...

1. 概述 图1：二叉树遍历 遍历二叉树，即按照某条搜索路径巡访树中的每个结点，使得每个节点均被访问一次，而且仅被访问一次1。 深度优先遍历，常见的有递归方式和用栈实现的迭代方式， Morris 遍历虽然空间复杂度很好，但因需在遍历期间改变树结构而不常用。 广度优先遍历，常见的是用队列实现的迭代方式，但需耗费大量内存，而 IDDFS 算法则更节省内存空间。 本文将主要讲述深度优先遍历的递归和迭代的实现方式，其它见后续文章。 代码仓库：https://github.com/patricklaux/perfect-code 2. 递归 先序遍历、中序遍历和后序遍历的过程完全相同，都是从根到左子树再到右子树，差别仅在于何时访问值。 看后面的代码实现，会发现三段递归程序几乎完全相同，仅仅是调整了访问值的次序。 2.1. 先序遍历 先序遍历 (pre-order traversal)：根，左，右 图2：先序遍历 代码实现 private void preorderTraversalR(List<Tuple2<K, V>> kvs, Node<K, V> p) { // visit，添加到结果集 kvs.add(Tuples.of(p.key, p.val)); if (p.left != null) { preorderTraversalR(kvs, p.left); } if (p.right != null) { preorderTraversalR(kvs, p.right); } } 2.2. 中序遍历 中序遍历(in-order traversal)：左，根，右 中序遍历正好是按键的大小排序。 图3：中序遍历 ...

前文实现了 Patricia Trie，但用的是字符比较，而原论文则采用的是二进制位比较。 然后，我们心里可能会有疑问：二进制位比较是如何推广到字符比较的呢？二进制位比较相比于字符比较，又有哪些优点或缺点呢？ 相关代码：https://github.com/patricklaux/perfect-code 1. 基数 让我们先从基数说起吧。 1.1. 基数(radix) 基数(radix)，在定位数系(positional numeral system) 中表示不重复编码(digit) 的数量。 譬如在10进制中，有 {0, 1, 2, … ,8, 9} 共 10 个编码，那么基数就是 10； 譬如在16进制中，有 {0, 1, 2, … ,e, f} 共 16 个编码，那么基数就是 16； ………… 如果我们用 EASCII 字符编码来作为集合，那么其基数就是 256； 如果我们用 UTF-16 字符编码来作为集合，那么其基数就是 65536； ………… 如果我们用小写英文字母 {a, b, c, … , y, z} 来作为集合，那么其基数就是26。 也就是说，我们可以根据需要定义一套编码集，而基数就是这套编码集的元素数量。 注：基数(radix) 也可以看作是集合论中的基数(cardinal)，而编码集是有限良序集。 1.2. 基数树(radix tree) 基数概念推广到树中，那么这个基数就是 R 的大小。 我们在前两篇文章的节点定义就有一个 R，用来指定数组容量。类似于如下定义： class RadixNode{ // 值 V val; // 子节点数组 RadixNode<V>[] table; // R为数组容量 public RadixNode(int R) { this.table = new RadixNode[R]; } } 这棵树会有 R 个分支，又因为编码集是有限良序集，所以可将数组索引映射为唯一编码。 ...

这篇文章我将介绍 StandardTrie 的简单变体： PatriciaTrie1。 PatriciaTrie 或 PatriciaTree， 在一些论文中又被称为 CompactTrie（紧凑 trie）或 CompressedTrie（压缩 trie）。 相关代码：https://github.com/patricklaux/perfect-code 1. 导引 PatriciaTrie 的显著优化是合并单路分支：如果一个非根无值节点有且仅有一个子节点，则将其子节点与该节点合并。 文字描述稍有点抽象，还是看图： 节点合并 图1：节点合并 节点分裂 如果需要添加键 “da”，该如何来处理哪？我们需要将 “dad” 分裂成两个节点，效果见下图： 图2：节点分裂 相信，这两张图已足以说明一切😀 同时，我们也可以看到合并后节点数变少，因此减少了可能的内存消耗。 2. 代码实现 依照惯例，还是写代码来实现它。 2.1. 节点定义 package com.igeeksky.perfect.nlp.trie; private static class PatriciaNode<V> { // key 的子串 String subKey; // 值（支持泛型，可以是非字符串） V val; // 子节点 PatriciaNode<V>[] table; public PatriciaNode(int R) { this.table = new PatriciaNode[R]; } public PatriciaNode(int R, String subKey) { this.subKey = subKey; this.table = new PatriciaNode[R]; } public PatriciaNode(String subKey, V value) { this.subKey = subKey; this.val = value; } public PatriciaNode(int R, String subKey, V value) { this.subKey = subKey; this.val = value; this.table = new PatriciaNode[R]; } } 对比前文的 StandardNode，多了一个 String 类型的 subKey 字段，该字段用于存储节点合并之后的字符串，其它无变化。 ...

这篇文章将介绍最简单的 Trie 结构，即 StandardTrie，常被称为 标准 Trie，或朴素 Trie。 相关代码：https://github.com/patricklaux/perfect-code 1. 导引 假设有一个关键词集，其中有 6 个单词：bad, bade, bed, ca, cad, dad。 当输入 “b” 时，输出以 “b” 为前缀的所有单词； 输入一段文本，输出文本中存在这六个单词的哪几个，以及单词出现的起止位置…… 我们可以建立如下图所示的树形结构。 图1：字典树示例 每个字符一个节点，节点之间用边相连； 有特殊标记（有值）则代表一个完整的关键词。 2. 基本性质与操作 通过观察 ”图1：字典树示例“，我们可以发现一些性质和规律。 基本性质 根节点无字符； 兄弟节点的字符互异； 非根节点有且仅有一个字符； 非根节点有且仅有一个父节点； 根节点到其它节点的每条路径代表一个唯一的字符串。 根据以上性质，我们又可以得到一个有意思的推论：6. 兄弟节点都具有同一前缀； 键查找 从根节点沿着序列路径递归查找子节点，最后一个字符对应节点如果有特殊标记，则命中。 譬如要查找 bad，root → b → a → d，命中，返回 bad；譬如查找 cup，root → c → NULL，未命中，返回空。 前缀匹配 先找到前缀节点，然后遍历其子节点。 譬如查找以 b 为前缀的关键词：1. 先找到 b 对应的节点，root → b，找到 b 节点；2. 遍历 b 节点的所有子节点。 ...

Trie1 通常被称为字典树（或前缀树、单词搜索树），是一种用于存储和检索字符串的树型数据结构。 Trie 是英文单词 retrieval 的一部分，名称最早由 E. Fredkin2 提出，发音同 “try”。 图1：关键词推荐列表 典型的应用场景是搜索引擎的输入框：譬如当输入 “trie” 时，会列出以 “trie” 为前缀的关键词推荐列表。 此外，还有诸如拼写检查、词典分词、词频统计、数据压缩、倒排索引、字符串排序、关键词过滤……等等众多应用场景。 技术演化 由于字典树相关算法的应用广泛，所以演化出大量的数据结构和优化技术，其进化史就是一个脑洞大开的过程。 我之前画过一张复杂的演进图，现在看来并无必要，事实上只要了解关键脉络即可。删繁就简，最终留下了这张比较简单的图。 图2：技术演化 文章目录 字典树之旅01：开篇（本文） 字典树之旅02：Trie 的标准实现 字典树之旅03：Patricia Trie(一) 字典树之旅04：Patricia Trie(二) 未完待续…… 参考资料 https://en.wikipedia.org/wiki/Trie ↩︎ Fredkin, E. . “Trie memory.” Communications of the Acm 3(1960). ↩︎