尼恩说在前面：
在40岁老架构师 尼恩的读者交流群(50+)中，最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、shein 希音、shopee、百度、网易的面试资格，遇到很多很重要的面试题：
- IM 敏感词过滤, 方案有哪些？
- 10万QPS下如何保证过滤延迟<50ms？
- 如何设计支持实时更新的敏感词服务？
- 10万QPS，如何设计敏感词服务，还要支持 实时更新的？
前几天 小伙伴面试阿里，遇到了这个问题。但是由于 没有回答好，导致面试挂了。
小伙伴面试完了之后，来求助尼恩。那么，遇到 这个问题，该如何才能回答得很漂亮，才能 让面试官刮目相看、口水直流。
所以，尼恩给大家做一下系统化、体系化的梳理，使得大家内力猛增，可以充分展示一下大家雄厚的 “技术肌肉”，让面试官爱到 “不能自已、口水直流”，然后实现”offer直提”。
当然，这道面试题，以及参考答案，也会收入咱们的 《尼恩Java面试宝典》V145版本PDF集群，供后面的小伙伴参考，提升大家的 3高 架构、设计、开发水平。
最新《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请关注本公众号【技术自由圈】获取，后台回复：领电子书
IM 敏感词过滤方案有哪些？
敏感词过滤功能在很多地方都会用到，理论上在Web应用中，只要涉及用户输入的地方，都需要进行文本校验，如：IM消息、XSS校验、SQL注入检验、敏感词过滤等。今天着重讲讲如何优雅高效地实现敏感词过滤。
敏感词过滤在IM消息、社区发帖、网站检索、短信发送等场景下是很常见的需求，尤其是在高并发场景下如何实现敏感词过滤，都对过滤算法提出了更高的性能要求，几种常见的敏感词过滤方案对比如下：
| 维度 | 暴力循环 | Trie树 | AC自动机 |
|---|---|---|---|
| 时间复杂度 | O(n×m) | O(L) | O(n) |
| 空间占用 | O(1) | 高(GB级) | 高(需失败指针) |
| 适用规模 | ≤100词 | ≤10万词 | ≥10万词 |
- 暴力循环 → Trie树：解决前缀共享问题
- Trie树 → AC自动机：通过状态转移消除回溯，引入失败指针实现多模式并行匹配
暴力匹配（BF）匹配算法
此方案使用BF 算法（Brute-Force算法），或蛮力算法，是一种基础的字符串匹配算法。
简单来说就是对于要进行检测的文本，遍历所有敏感词，逐个检测输入的文本中是否含有指定的敏感词。
先引入两个术语：主串和模式串。简单来说，我们要在字符串 A 中查找子串 B，那么 A 就是主串，B 就是模式串。
作为最简单、最暴力的字符串匹配算法，BF 算法的思想可以用一句话来概括，那就是，如果主串长度为 n，模式串长度为 m，我们在主串中检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。图示如下：
结合上图，具体来说，就是每次拿模式串和主串对齐，然后从左到右依次比较每个字符，如果出现不相等，则把模式串往后移一个位置，再次重复上述步骤，直到模式串每个字符与对应主串位置字符都相等，则返回主串对应下标，表示找到，否则返回 -1，表示没找到
这个算法很好理解，因为这就是我们正常都能想到的暴力匹配，BF 算法的时间复杂度最差是 O(n*m)（n为主串长度，m为模式串长度），意味着要模式串要移到主串 n-m 的位置上，并且模式串每个字符都要与子串比较。
尽管 BF 算法复杂度看起来很高，但是在日常开发中，如果主串和模式串规模不大的话，该算法依然比较常用，因为足够简单，实现起来容易，不容易出错。在规模不大的情况下，开销也可以接受，毕竟 O(n*m) 是最差的表现，大部分时候，执行效率比这个都要高。
但是对于对时间要求比较敏感，或者需要高频匹配，数据规模较大的情况下，比如编辑器中的匹配功能、敏感词匹配系统等，BF 算法就不适用了。
参考实现：
@Test
public void test1(){
Set<String> sensitiveWords=new HashSet<>();
sensitiveWords.add("shit");
sensitiveWords.add("傻蛋");
sensitiveWords.add("笨蛋");
String text="你是傻蛋啊";
for(String sensitiveWord:sensitiveWords){
if(text.contains(sensitiveWord)){
System.out.println("输入的文本存在敏感词。——" + sensitiveWord);
break;
}
}
}
暴力循环匹配 的不足
代码十分简单，也确实能够满足要求。但是这个方案有一个很大的问题是，随着敏感词数量的增多，敏感词检测的时间会呈线性增长。
由于之前的项目的敏感词数量只有几十个，所以使用这种方案不会存在太大的性能问题。但是如果项目中有成千上万个敏感词，使用这种方案就会很耗CPU了。
KMP算法(Knuth Morris Pratt 算法)
KMP 算法可以说是字符串匹配算法中最知名的算法了，KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。
与暴力匹配算法相比，KMP 算法在时间复杂度上有显著的优化，使得它在实际应用中得到了广泛的应用。
KMP 算法是一种基于 部分匹配表（next 数组） 的字符串匹配算法，通过预处理模式串的重复前后缀信息，避免主串指针回溯，将暴力匹配的最坏时间复杂度从 O(mn) 优化到 O(m+n)。
其核心思想是 利用已匹配信息跳过无效比较，通过 next 数组确定失配时的跳转位置
KMP 算法的核心思想
假设主串是 a，模式串是 b。
在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况，从而避免 BF 算法这种暴力匹配，提高算法性能。
举个例子，假设：
- 主串（文本）为：
"ABABABCABABABD" - 模式串（要找的词）为：
"ABABD"
普通暴力匹配（BF算法）：
(1) 主串和模式串从头开始对比： ABABA（主串） vs ABABD（模式串） ，发现 前4个字符ABAB匹配，但第5个字符A（主串）≠ D（模式串），所以，匹配失败。
(2) 暴力法会回退：主串从第2个字符B开始重新对比，模式串从头开始。
KMP的聪明做法：
1、发现前4个字符ABAB匹配，但第5个字符失败时，KMP会问：
已匹配的ABAB中，最长的相同 前后缀是什么？
ABAB的 前缀有： A 、AB、 ABA ；ABAB的 后缀有：B、AB、BAB最长 公共前后缀是
AB，长度=2
2、直接让模式串的 AB 对齐 主串已匹配部分的 AB , 跳过无效对比：
主串：ABABABCABABABD
↓ 模式串从第3个字符继续匹配（`ABABD`的第3个字符`A`对齐主串`C`的位置）
模式串： ABABD
- 主串指针不后退，模式串利用
next数组智能跳跃。
关键点：
next数组记录模式串的“自相似性”（比如ABAB中AB重复）。- 匹配失败时，模式串按
next值滑动，主串永不回退。
就像用尺子量布时，发现一段花纹重复，直接跳过已知重复部分继续量，省时高效
什么是 next指针
next指针就像"错题本"
假设你在背单词："ABABD"（模式串），背到第5个字母时卡壳了。next指针会告诉你：
(1) 前面背对的"ABAB"里，开头的"AB"和结尾的"AB"是重复的
(2) 下次直接从第3个字母"A"开始接着背（不用重头背！）
具体来说：
- 当匹配失败时，next值告诉你：
✓ 模式串该往右滑多远（比如next=2，就滑到模式串第3个字符继续比）
✓ 主串不用回退（像传送带一样只往前走）
关键操作：next数组的生成
- 预处理模式串生成
next数组（类似创建"跳转地图"） - 匹配失败时 根据
next数组跳转，主串指针不后退
以模式串ABCDABD为例，计算每个位置的next值：
| 位置 | 字符 | 前缀 | 后缀 | 最长公共前后缀长度 | next值 |
|---|---|---|---|---|---|
| 0 | A | 无 | 无 | 0 | -1 |
| 1 | B | A | B | 0 | 0 |
| 2 | C | A,AB | BC,C | 0 | 0 |
| 3 | D | A,AB,ABC | BCD,CD,D | 0 | 0 |
| 4 | A | A,AB,ABC,ABCD | BCDA,CDA,DA,A | 1（前缀A=后缀A） | 0 |
| 5 | B | A,AB,...,ABCDA | BCDAB,...,B | 前缀AB=后缀AB → 2 | 1 |
| 6 | D | A,...,ABCDAB | BCDABD,...,D | 0 | 2 |
最终next数组：[-1, 0, 0, 0, 0, 1, 2]
KMP匹配过程演示
回到最初的失败场景：
主串：ABCDABE...
模式：ABCDABD（前6字符匹配，第7字符不匹配，E≠D）
根据next数组，失败位置是模式串的第6位（索引6），对应的next[6]=2。
这意味着：
(1) 模式串右移位数 = 已匹配字符数 - next值 → 6 - 2 = 4位
(2) 模式串指针回退到 next[6]=2的位置（即模式串的第3个字符C）
移动后的对比：
主串：ABCDABE...
模式： ABCDABD（直接从模式串的第3 个字符 `C` 开始对比）
对比过程：
- 主串的
E继续和模式串的新位置 第3 个字符C对比（主串指针未回退！） - 模式串的
C与主串E不匹配 → 再次根据next[2]=0跳转
对比KMP和BF的效率
暴力匹配（BF）：
- 在第1次失败后，需要对比6次无效位置（模式串滑动1位后对比6次才能发现不匹配）
KMP算法：
- 直接跳过了4个位置，避免了这6次无效对比
- 主串指针始终向前（从位置6继续，无需回退到位置1）
把模式串想象成一个带弹簧的尺子：
(1) next数组像是弹簧的弹力系数
(2) 每当遇到不匹配，弹簧会根据next值自动收缩到合适长度
(3) 主串像传送带一样单向移动，无需倒退重走
最终效果：KMP的时间复杂度是O(n+m)，而暴力匹配是O(n×m)！
KMP 算法的应用场景
KMP 算法的预处理阶段时间复杂度为 O(m)，其中 m 是模式串的长度。
在匹配阶段，文本串和模式串的指针都只会单向移动，不会出现回溯的情况，因此匹配阶段的时间复杂度也是 O(n + m)，其中 n 是文本串的长度。这使得 KMP 算法在处理大规模数据时具有较高的效率，相比暴力匹配算法的 O(n * m) 时间复杂度，KMP 算法在大多数情况下能够提供更快的匹配速度。
KMP 算法广泛应用于文本编辑器中的查找和替换功能、搜索引擎中的关键词匹配、生物信息学中的 DNA 序列分析等领域。例如，在文本编辑器中，当用户使用查找功能时，KMP 算法能够快速定位到目标文本的位置，从而提高用户体验。
KMP 算法作为一种经典的字符串匹配算法，凭借其高效性和稳定性，在众多领域发挥着重要作用。理解 KMP 算法的原理和实现，有助于我们更好地解决实际问题中的字符串匹配需求。
智能索引 Trie树
什么是trie树
Trie 树，也叫“字典树”。
顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
我们有 6 个字符串，它们分别是：how，hi，her，hello，so，see。
我们希望在里面多次查找某个字符串是否存在。
如果使用BF算法，都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配，那效率就比较低，有没有更高效的方法呢？
这个时候，我们就可以先对这 6 个字符串做一下预处理，组织成 Trie 树的结构，之后每次查找，都是在 Trie 树中进行匹配查找。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。最后构造出来的就是下面这个图中的样子。
其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。
Trie 树是怎么构造出来的？
当我们在 Trie 树中查找一个字符串的时候，比如查找字符串“her”，那我们将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的路径
如果我们要查找的是字符串“he”呢？我们还用上面同样的方法，从根节点开始，沿着某条路径来匹配，如图所示，绿色的路径，是字符串“he”匹配的路径。但是，路径的最后一个节点“e”并不是红色的。也就是说，“he”是某个字符串的前缀子串，但并不能完全匹配任何字符串。
Trie树 与 暴力匹配（BF）的对比
相比于暴力匹配（BF）算法，Trie树的优势主要体现在以下方面：
（1）时间复杂度优化：BF算法每次匹配需完整遍历主串和模式串，时间复杂度为O(n×m)，而Trie树通过前缀共享将查询时间降至O(k)（k为模式串长度），适合高频查询场景（如搜索引擎关键词提示）
（2）多模式串处理能力：BF需对每个模式串单独匹配，而Trie树可一次性存储所有模式串，实现多模式串的并行匹配（如敏感词过滤），避免重复计算。
（3）功能扩展性：Trie树天然支持前缀匹配、最长前缀查找等功能，而BF仅支持完整匹配。例如输入法联想提示、路由表最长前缀匹配等场景必须依赖Trie结构。
（4）预处理优势：Trie树通过预先构建字符路径，牺牲空间换取查询效率，尤其适合静态词库（如字典）；而BF每次匹配均需从头计算，无法复用历史结果。
BF -> Trie树演进本质：Trie树通过空间换时间和结构化存储，解决了BF算法在处理多模式串、前缀匹配时的低效问题，是算法设计从“暴力遍历”到“智能索引”的典型演进。
Trie 树的实现敏感词过滤
Trie 树主要有两个操作
（1）将字符串集合构造成 Trie 树。这个过程分解开来的话，就是一个将字符串插入到 Trie 树的过程。
（2）然后是在 Trie 树中查询一个字符串。
trie树实现敏感词过滤参考代码：
/**
* 敏感词过滤器核心类，基于Trie树实现高效匹配
* 特点：支持中文敏感词检测，时间复杂度O(n)
*/
public class SensitiveWordFilter {
// Trie树根节点（空节点）
private final TrieNode root = new TrieNode();
// 敏感词替换字符串
private static final String REPLACEMENT = "***";
/**
* Trie树节点静态内部类
* 采用HashMap存储子节点实现动态扩展
*/
private static class TrieNode {
// 子节点映射表 <字符, 对应子节点>
Map<Character, TrieNode> children = new HashMap<>();
// 标记当前节点是否为某个敏感词的结尾
boolean isEnd;
}
/**
* 加载敏感词库构建Trie树
* @param keywords 敏感词集合
*/
public void loadKeywords(Set<String> keywords) {
for (String word : keywords) {
TrieNode node = root; // 从根节点开始构建
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
// 如果当前字符不存在于子节点，则新建分支
if (!node.children.containsKey(c)) {
node.children.put(c, new TrieNode());
}
// 移动到下一级节点
node = node.children.get(c);
}
// 标记敏感词结束位置
node.isEnd = true;
}
}
/**
* 执行敏感词过滤主方法
* @param text 待过滤文本
* @return 过滤后的安全文本
*/
public String filter(String text) {
StringBuilder result = new StringBuilder();
int start = 0; // 文本扫描起始位置
while (start < text.length()) {
// 检测从start位置开始的敏感词
int matchLength = checkSensitiveWord(text, start);
if (matchLength > 0) {
// 存在敏感词则替换
result.append(REPLACEMENT);
start += matchLength; // 跳过已检测部分
} else {
// 无敏感词则保留原字符
result.append(text.charAt(start++));
}
}
return result.toString();
}
/**
* 检查指定位置开始的敏感词
* @param text 待检测文本
* @param startIndex 检测起始位置
* @return 匹配到的敏感词长度（未匹配返回0）
*/
private int checkSensitiveWord(String text, int startIndex) {
TrieNode tempNode = root;
int matchLength = 0;
for (int i = startIndex; i < text.length(); i++) {
char c = text.charAt(i);
// 当前字符不匹配时终止检测
if (!tempNode.children.containsKey(c)) {
break;
}
// 移动到下一级节点
tempNode = tempNode.children.get(c);
matchLength++;
// 遇到结束标记说明匹配成功
if (tempNode.isEnd) {
return matchLength;
}
}
return 0; // 未匹配到完整敏感词
}
// 测试用例
public static void main(String[] args) {
SensitiveWordFilter filter = new SensitiveWordFilter();
// 模拟敏感词库
Set<String> sensitiveWords = new HashSet<>();
sensitiveWords.add("暴力");
sensitiveWords.add("敏感词");
sensitiveWords.add("测试");
// 构建Trie树
filter.loadKeywords(sensitiveWords);
// 测试过滤效果
String testText = "这是一段包含暴力内容和敏感词的测试文本";
System.out.println(filter.filter(testText));
// 输出：这是一段包含‌***内容和***‌的***文本
}
}
在 Trie 树中，查找某个字符串的时间复杂度是多少？
如果要在一组字符串中，频繁地查询某些字符串，用 Trie 树会非常高效。
构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）。
但是一旦构建成功之后，后续的查询操作会非常高效。
构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。
实现了Trie树的开源框架
可以看出， Trie 树的核心原理其实很简单，就是通过公共前缀来提高字符串匹配效率。
Apache Commons Collections这个库中就有 Trie 树实现：
Trie<String, String> trie = new PatriciaTrie<>();
trie.put("Abigail", "student");
trie.put("Abi", "doctor");
trie.put("Annabel", "teacher");
trie.put("Christina", "student");
trie.put("Chris", "doctor");
Assertions.assertTrue(trie.containsKey("Abigail"));
assertEqual
s("{Abi=doctor, Abigail=student}", trie.prefixMap("Abi").toString());
assertEquals("{Chris=doctor, Christina=student}", trie.prefixMap("Chr").toString());
双数组 Trie 树（Double-Array Trie，DAT）
Trie 树是一种利用空间换时间的数据结构，占用的内存会比较大。
也正是因为这个原因，实际工程项目中都是使用的改进版 Trie 树例如双数组 Trie 树（Double-Array Trie，DAT）。
DAT 的设计者是日本的 Aoe Jun-ichi，Mori Akira 和 Sato Takuya，他们在 1989 年发表了一篇论文《An Efficient Implementation of Trie Structures》，详细介绍了 DAT 的构造和应用，
相比较于 Trie 树，DAT 的内存占用极低，可以达到 Trie 树内存的 1%左右。
DAT 在中文分词、自然语言处理、信息检索等领域有广泛的应用，是一种非常优秀的数据结构。
Trie树的局限性
传统Trie树在处理敏感词匹配时存在以下核心缺陷：
（1）回溯成本高：当字符匹配失败时需退回到根节点重新匹配，导致对同一文本位置多次扫描，时间复杂度达 O(n×m)（n为文本长度，m为敏感词最大长度）
（2）多模式匹配低效：逐个敏感词独立判断，无法利用词汇间的关联性
（3）长尾性能劣化：敏感词库规模增大时，匹配耗时线性增长，难以应对工业级海量词库场景
AC自动机
什么是AC自动机？
简单理解AC自动机 就是 Tire树 + KMP，
关于KMP算法，可以参考网上文章，其实就是trie树 + 失配指针（下图动画中的虚线）
下面是对AC自动机构建过程的详细介绍：
构建Trie树：首先构建一个Trie树，用于存储所有字符串。每个节点代表一个字符，从根节点到任意节点的路径代表一个字符串的前缀。
创建失配指针（Failure Pointers）：这些指针指向Trie树中的另一节点，当在某一节点上的字符匹配失败时，算法会通过失效指针跳转到另一节点继续匹配，而不是从头开始。
搜索：在给定文本中进行搜索时，AC自动机沿着Trie树移动，同时在匹配失败时 , 使用Failure Pointer 失效指针进行快速跳转。
AC自动机算法演示动画，下面动画清晰的演示了AC自动机算法原理
为什么用AC自动机
AC自动机（Aho-Corasick算法）是一种用于字符串搜索的算法，它能够高效地在一段文本中查找多个模式串/字符串。
这个算法由Alfred V. Aho和Margaret J. Corasick于1975年共同提出。
AC自动机优化了字典树匹配的过程：在字典树的暴力匹配过程中，每当匹配失败，就会从下一个位置重新开始匹配，这导致了重复的匹配操作。
为了提高效率，AC自动机算法借鉴KMP算法的思想，通过在每个节点添加一个失配链接点，使得在匹配失败后能直接跳转到相应的下一个节点进行判断，从而避免重复的判断过程。
AC自动机通过预处理Fail指针和多模式状态机跳转，在Trie树基础上实现性能质的飞跃，参考后面的动画GIF
- 在 Trie匹配过程中，一些模式串之间存在一部分重叠，也就意味着在匹配 sherhs 过程，
- 如果能匹配到点1，后续一定可以匹配到点2
- 如果在点1向下匹配失败时候，可以直接跳到点2，继续向下匹配
- 通过增加两点之间联系，减少回溯过程
- 关联的条件是1的后缀与2的前缀相同(类似 KMP 思想)
AC自动机的优势
AC自动机通过两项核心改进突破Trie树瓶颈：
（1）Fail指针机制
- KMP思想的移植： 为每个节点预计算最长可复用后缀对应的状态（Fail指针），匹配失败时直接跳转而非回溯，消除重复扫描。
- 跳转逻辑示例：若敏感词集包含
she和he，当文本出现she时，匹配到e节点触发he的终止状态，无需重新从h开始。
（2）多模式并行匹配
- 单次文本扫描即可检测所有敏感词，时间复杂度降至 O(n)（与词库规模无关，n为文本长度）
- 通过构建Trie树时预置Fail指针（BFS遍历实现），确保匹配阶段无回溯
性能对比
| 维度 | Trie树 | AC自动机 |
|---|---|---|
| 时间复杂度 | O(n*m)（n为文本长度，m为敏感词最大长度） | O(n)（n为文本长度） |
| 空间利用率 | 共享前缀节省空间 | 增加Fail指针存储，但整体仍优于哈希表 |
| 适用场景 | 小规模词库、低并发场景 | 万级词库、高并发实时过滤（如社交平台） |
| 扩展性 | 无法处理模糊匹配 | 结合Wildcard优化可支持通配符 |
开源的AC自动机实现
基于双数组 Trie 结构的 Aho Corasick 算法的极速实现。
其速度是简单实现的 5 到 9 倍，或许是目前最快的实现
AhoCorasickDoubleArrayTrie：https://github.com/hankcs/AhoCorasickDoubleArrayTrie
用法：
<dependency>
<groupId>com.hankcs</groupId>
<artifactId>aho-corasick-double-array-trie</artifactId>
<version>1.2.3</version>
</dependency>
// Collect test data set
TreeMap<String, String> map = new TreeMap<String, String>();
String[] keyArray = new String[]
{
"hers",
"his",
"she",
"he"
};
for (String key : keyArray)
{
map.put(key, key);
}
// Build an AhoCorasickDoubleArrayTrie
AhoCorasickDoubleArrayTrie<String> acdat = new AhoCorasickDoubleArrayTrie<String>();
acdat.build(map);
// Test it
final String text = "uhers";
List<AhoCorasickDoubleArrayTrie.Hit<String>> wordList = acdat.parseText(text);
测试结果：
AhoCorasickDoubleArrayTrie 与 robert-bor 的 aho-corasick 进行了比较，ACDAT 代表 AhoCorasickDoubleArrayTrie，Naive 代表 aho-corasick，结果是：
Parsing English document which contains 3409283 characters, with a dictionary of 127142 words.
Naive ACDAT
time 607 102
char/s 5616611.20 33424343.14
rate 1.00 5.95
===========================================================================
Parsing Chinese document which contains 1290573 characters, with a dictionary of 146047 words.
Naive ACDAT
time 319 35
char/s 2609156.74 23780600.00
rate 1.00 9.11
===========================================================================
在英文测试中，AhoCorasickDoubleArrayTrie 的速度提高了 5 倍。
在中文测试中，AhoCorasickDoubleArrayTrie 的速度提高了 9 倍。
此测试在 i7 2.0GHz 处理器、-Xms512m -Xmx512m -Xmn256m 的环境下进行。
Netty 敏感词过滤的技术选型
在 Netty 框架中实现敏感词过滤时，需综合考虑 性能、内存占用、开发复杂度 等因素。
以下是各算法特性对比与选型建议：
1. 算法特性对比
| 算法/结构 | 适用场景 | 性能表现 | 内存占用 | 多模式匹配能力 | 实现复杂度 |
|---|---|---|---|---|---|
| BF 算法 | 小规模敏感词库、低频匹配 | O(mn)，极端场景下性能急剧下降 | 低 | 不支持 | 极简单 |
| Trie 树 | 中等规模词库、前缀匹配需求 | 匹配时间 O(L)（L为字符串长） | 高（空间换时间）14 | 支持 | 中等 |
| 双数组 Trie (DAT) | 海量敏感词库、内存敏感场景 | 单模式匹配极快，但多模式需多次回溯 | 极低 | 弱支持 | 较高（需处理状态转移） |
| AC 自动机 | 大规模词库、实时多模式匹配 | 一次扫描完成全部匹配 O(n)（n为主串长） | 中等（需维护失败指针） | 强支持 | 较高 |
2. 选型决策
根据 Netty 高并发、低延迟的特性，推荐优先级如下：
首选方案：AC 自动机
优势
- 多模式匹配效率碾压其他方案，单次文本扫描即可检测所有敏感词。
支持动态词库更新（通过重建或增量维护 Trie 树）。
- 可结合内存优化（如压缩 Trie 结构）平衡性能与资源消耗。
适用场景
- 需实时过滤大量敏感词（如聊天系统、内容审核）。
- 敏感词数量超过 1 万且需要高频匹配的场景。
次选方案：双数组 Trie (DAT)
优势
- 内存占用极低，适合嵌入式或资源受限环境。
单模式匹配速度快（如仅需检测少量固定关键词）。
局限
- 多模式匹配需多次扫描文本，性能低于 AC 自动机。
不推荐方案
- Trie 树：内存占用高，且多模式匹配效率低于 AC 自动机。
- BF 算法：仅适用于测试验证，实际生产环境性能不达标。
3. 开源实现框架参考
- Java AC 自动机库：
org.ahocorasick（轻量级，支持 Trie 树构建与多模式匹配） 。 - 双数组 Trie 实现：
com.github.komoot.datrie（高效 DAT 实现，适用于静态词库） 。
在 Netty 中实现敏感词过滤，AC 自动机是综合最优解，尤其在处理海量敏感词和高并发请求时表现卓越。若对内存有极端限制，可考虑双数组 Trie，但需接受多模式匹配性能损耗。
基于 AC 自动机算法的 Netty 敏感词风控处理器实现
下面是基于 AC 自动机算法的 Netty 敏感词风控处理器实现示例。
当检测到敏感词时，回复“您发送的消息，带有敏感内容”：
import io.netty.channel.ChannelHandlerContext;
import io.netty.channel.ChannelInboundHandlerAdapter;
import io.netty.util.AttributeMap;
import java.util.List;
/**
* 敏感词过滤处理器，用于检测入站消息是否包含敏感词
*/
public class SensitiveWordHandler extends ChannelInboundHandlerAdapter {
private AcAutomaton acAutomaton;
/**
* 构造函数，传入敏感词列表并构建AC自动机
*
* @param sensitiveWords 敏感词列表
*/
public SensitiveWordHandler(List<String> sensitiveWords) {
acAutomaton = new AcAutomaton();
acAutomaton.build(sensitiveWords); // 构建AC自动机
}
/**
* 处理入站消息
*
* @param ctx 通道处理上下文
* @param msg 入站消息
* @throws Exception 处理过程中可能出现的异常
*/
@Override
public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception {
AttributeMap msgAttr = (AttributeMap) msg; // 将消息转换为AttributeMap类型
String content = msgAttr.get("content"); // 获取消息中的文本内容
if (acAutomaton.match(content)) {
// 调用AC自动机的match方法检测是否包含敏感词
// 如果检测到敏感词，回复提示信息
ctx.writeAndFlush("您发送的消息，带有敏感内容");
return; // 结束当前方法执行，不再向下传递消息
}
ctx.fireChannelRead(msg); // 如果未检测到敏感词，继续将消息传递给下一个处理器
}
}
同时，需要实现 AC 自动机算法的类：
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.Queue;
import java.util.LinkedList;
/**
* 基于AC自动机算法实现敏感词匹配
*/
public class AcAutomaton {
/**
* Trie树节点类
*/
private static class TrieNode {
Map<Character, TrieNode> children; // 子节点映射，键为字符，值为对应的子节点
String word; // 如果该节点是一个单词的结尾，则存储该单词
TrieNode fail; // 失败指针，用于快速跳转到可能的匹配位置
/**
* 构造函数，初始化节点
*/
public TrieNode() {
children = new HashMap<>();
word = null;
fail = null;
}
}
private TrieNode root; // AC自动机的根节点
/**
* 构造函数，初始化根节点
*/
public AcAutomaton() {
root = new TrieNode();
}
/**
* 构建AC自动机
*
* @param sensitiveWords 敏感词列表
*/
public void build(List<String> sensitiveWords) {
// 构建Trie树
for (String word : sensitiveWords) {
TrieNode node = root;
for (char c : word.toCharArray()) {
// 遍历敏感词的每个字符
if (!node.children.containsKey(c)) {
// 如果当前节点没有该字符对应的子节点
node.children.put(c, new TrieNode()); // 创建新的子节点
}
node = node.children.get(c); // 移动到子节点
}
node.word = word; // 标记该节点为单词结尾
}
// 构建失败指针
Queue<TrieNode> queue = new LinkedList<>(); // 用于广度优先遍历的队列
// 初始化队列，将根节点的子节点加入队列
for (TrieNode child : root.children.values()) {
child.fail = root; // 根节点的子节点的失败指针指向根节点
queue.add(child);
}
while (!queue.isEmpty()) {
// 广度优先遍历构建失败指针
TrieNode node = queue.poll(); // 取出队列中的节点
for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
// 遍历该节点的所有子节点
TrieNode child = entry.getValue(); // 获取子节点
TrieNode failNode = node.fail; // 获取当前节点的失败指针节点
// 寻找失败指针节点的对应字符子节点
while (failNode != null && !failNode.children.containsKey(entry.getKey())) {
failNode = failNode.fail; // 如果失败指针节点没有对应子节点，则继续向上查找
}
// 设置子节点的失败指针
child.fail = (failNode != null) ? failNode.children.get(entry.getKey()) : root;
queue.add(child); // 将子节点加入队列
}
}
}
/**
* 在文本中匹配敏感词
*
* @param text 要匹配的文本
* @return 如果文本中包含敏感词，则返回true；否则返回false
*/
public boolean match(String text) {
TrieNode p = root; // 从根节点开始匹配
for (char c : text.toCharArray()) {
// 遍历文本的每个字符
// 如果当前节点不是根节点, 且没有对应字符的子节点，则沿着失败指针回溯
while (p != root && !p.children.containsKey(c)) {
p = p.fail;
}
if (p.children.containsKey(c)) {
// 如果当前节点有对应字符的子节点
p = p.children.get(c); // 移动到子节点
}
if (p.word != null) {
// 如果当前节点是一个单词结尾，则说明匹配到敏感词
return true;
}
}
return false; // 遍历完整个文本未匹配到敏感词
}
}
在上面的示例代码中：
SensitiveWordHandler类继承自ChannelInboundHandlerAdapter，用于处理 Netty 通道中的入站消息。- 在
SensitiveWordHandler的构造函数中，传入敏感词列表，并构建 AC 自动机。 channelRead方法在通道读取消息时被调用。它从消息对象中获取文本内容，然后使用 AC 自动机进行敏感词匹配。如果匹配到敏感词，则通过ctx.writeAndFlush方法向客户端回复提示信息“您发送的消息，带有敏感内容”，并终止后续的消息处理流程；如果未匹配到敏感词，则继续将消息传递给下一个处理器。
AcAutomaton 类实现了 AC 自动机算法：
- 使用
TrieNode类表示 AC 自动机的节点，每个节点包含其子节点映射、对应的单词（当节点是某个敏感词的结尾时）以及失败指针。 build方法用于构建 AC 自动机。首先构建 Trie 树，将所有敏感词插入到树中；然后构建失败指针，使用广度优先搜索的方式为每个节点设置失败指针，以便在匹配过程中能够快速跳转。match方法用于在文本中匹配敏感词。它从文本的每个字符开始，沿着 AC 自动机的节点进行匹配。如果在某个节点匹配到敏感词（即节点的word属性不为null），则返回true表示存在敏感词。
需要注意的是，这只是一个简单的示例，实际应用中可能需要根据具体的需求对代码进行扩展和完善，例如处理编码问题、支持不同格式的消息、优化性能等。此外，在构建敏感词列表时，应确保敏感词的准确性和完整性，以提高敏感词过滤的效果。
AC 自动机算法 优化
- 异步检测：将敏感词匹配任务提交至独立线程池，避免阻塞 I/O 线程
动态加载：通过
WatchService监控词库文件变更实现热更新分级响应：根据敏感词级别返回不同提示（如警告/直接封禁）
- 日志记录：记录触发敏感词的原始消息和用户信息用于审计
- 模糊匹配：集成正则表达式处理变体敏感词（如拼音、谐音）
1. 异步检测：将敏感词匹配任务提交至独立线程池
import io.netty.channel.ChannelHandlerContext;
import io.netty.channel.ChannelInboundHandlerAdapter;
import io.netty.util.AttributeMap;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class SensitiveWordHandler extends ChannelInboundHandlerAdapter {
private AcAutomaton acAutomaton;
private ExecutorService executorService; // 独立线程池
public SensitiveWordHandler(List<String> sensitiveWords, int threadPoolSize) {
acAutomaton = new AcAutomaton();
acAutomaton.build(sensitiveWords);
executorService = Executors.newFixedThreadPool(threadPoolSize); // 创建固定大小的线程池
}
@Override
public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception {
AttributeMap msgAttr = (AttributeMap) msg;
String content = msgAttr.get("content");
// 将敏感词检测任务提交至线程池异步处理
executorService.submit(() -> {
try {
if (acAutomaton.match(content)) {
ctx.writeAndFlush("您发送的消息，带有敏感内容");
}
} catch (Exception e) {
e.printStackTrace();
}
});
ctx.fireChannelRead(msg);
}
@Override
public void channelInactive(ChannelHandlerContext ctx) throws Exception {
executorService.shutdown(); // 当连接关闭时，优雅地关闭线程池
}
}
2. 动态加载：通过 WatchService 监控词库文件变更实现热更新
import java.nio.file.*;
import java.io.IOException;
import java.util.List;
public class SensitiveWordLoader {
private AcAutomaton acAutomaton;
private Path watchPath;
private WatchService watchService;
public SensitiveWordLoader(String sensitiveWordFilePath, List<String> initialSensitiveWords) throws IOException {
acAutomaton = new AcAutomaton();
acAutomaton.build(initialSensitiveWords);
watchPath = Paths.get(sensitiveWordFilePath);
watchService = FileSystems.getDefault().newWatchService();
watchPath.register(watchService, StandardWatchEventKinds.ENTRY_MODIFY); // 监听文件修改事件
startWatching(); // 开始监控文件变化
}
private void startWatching() {
new Thread(() -> {
while (true) {
try {
WatchKey key = watchService.take(); // 获取文件系统通知
for (WatchEvent<?> event : key.pollEvents()) {
WatchEvent.Kind<?> kind = event.kind();
if (kind == StandardWatchEventKinds.ENTRY_MODIFY) {
// 当敏感词文件被修改时，重新加载敏感词
List<String> newSensitiveWords = loadSensitiveWords(watchPath.toString());
acAutomaton.build(newSensitiveWords);
System.out.println("敏感词列表已更新");
}
}
key.reset(); // 重置WatchKey，以便接收下一次通知
} catch (InterruptedException | IOException e) {
e.printStackTrace();
}
}
}).start();
}
private List<String> loadSensitiveWords(String filePath) {
// 实现从文件加载敏感词列表的逻辑
// 这里可以使用BufferedReader等工具类读取文件内容并解析为敏感词列表
return new ArrayList<>(); // 返回空列表作为示例
}
public AcAutomaton getAcAutomaton() {
return acAutomaton;
}
}
3. 分级响应：根据敏感词级别返回不同提示
public class AcAutomaton {
// ...（省略其他代码）
public class SensitiveWordInfo {
String word;
int level; // 敏感词级别
public SensitiveWordInfo(String word, int level) {
this.word = word;
this.level = level;
}
public String getWord() {
return word;
}
public int getLevel() {
return level;
}
}
public void build(List<SensitiveWordInfo> sensitiveWords) {
// 根据SensitiveWordInfo构建AC自动机
// ...（省略其他代码，与之前类似，但需要处理SensitiveWordInfo对象）
}
public SensitiveWordInfo match(String text) {
TrieNode p = root;
for (char c : text.toCharArray()) {
while (p != root && !p.children.containsKey(c)) {
p = p.fail;
}
if (p.children.containsKey(c)) {
p = p.children.get(c);
}
if (p.word != null) {
return new SensitiveWordInfo(p.word, p.level); // 返回匹配的敏感词及其级别
}
}
return null;
}
}
// 在SensitiveWordHandler中使用分级响应
public class SensitiveWordHandler extends ChannelInboundHandlerAdapter {
// ...（省略其他代码）
@Override
public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception {
AttributeMap msgAttr = (AttributeMap) msg;
String content = msgAttr.get("content");
executorService.submit(() -> {
try {
SensitiveWordInfo sensitiveWordInfo = acAutomaton.match(content);
if (sensitiveWordInfo != null) {
switch (sensitiveWordInfo.getLevel()) {
case 1:
ctx.writeAndFlush("警告：您的消息包含轻微敏感内容");
break;
case 2:
ctx.writeAndFlush("您的消息违反规定，账号已被封禁");
ctx.close(); // 封禁账号，关闭连接
break;
// 可以添加更多级别和对应的处理逻辑
}
}
} catch (Exception e) {
e.printStackTrace();
}
});
ctx.fireChannelRead(msg);
}
}
4. 日志记录：记录触发敏感词的原始消息和用户信息
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
public class SensitiveWordHandler extends ChannelInboundHandlerAdapter {
private static final Logger logger = LoggerFactory.getLogger(SensitiveWordHandler.class);
// ...（省略其他代码）
@Override
public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception {
AttributeMap msgAttr = (AttributeMap) msg;
String content = msgAttr.get("content");
String userInfo = msgAttr.get("userInfo"); // 假设消息中包含用户信息
executorService.submit(() -> {
try {
SensitiveWordInfo sensitiveWordInfo = acAutomaton.match(content);
if (sensitiveWordInfo != null) {
// 记录日志
logger.warn("检测到敏感词！用户信息：{}，原始消息：{}，敏感词：{}，级别：{}",
userInfo, content, sensitiveWordInfo.getWord(), sensitiveWordInfo.getLevel());
// 根据级别返回提示信息
// ...（省略之前的处理逻辑）
}
} catch (Exception e) {
e.printStackTrace();
}
});
ctx.fireChannelRead(msg);
}
}
5. 模糊匹配：集成正则表达式处理变体敏感词
import java.util.regex.Pattern;
public class AcAutomaton {
// ...（省略其他代码）
public void build(List<SensitiveWordInfo> sensitiveWords) {
// ...（省略其他代码）
// 在构建AC自动机时，可以同时处理正则表达式模式
for (SensitiveWordInfo wordInfo : sensitiveWords) {
String word = wordInfo.getWord();
if (word.startsWith("/") && word.endsWith("/")) {
// 简单判断是否为正则表达式模式
String regex = word.substring(1, word.length() - 1);
// 将正则表达式模式转换为对应的字符序列，以便在AC自动机中处理
// 这里需要根据实际需求实现正则表达式模式的转换和处理逻辑
// ...
} else {
// 普通敏感词处理逻辑
// ...
}
}
}
public SensitiveWordInfo match(String text) {
// 首先尝试匹配普通敏感词
TrieNode p = root;
for (char c : text.toCharArray()) {
while (p != root && !p.children.containsKey(c)) {
p = p.fail;
}
if (p.children.containsKey(c)) {
p = p.children.get(c);
}
if (p.word != null) {
return new SensitiveWordInfo(p.word, p.level);
}
}
// 如果普通匹配未找到，尝试正则表达式匹配
for (SensitiveWordInfo wordInfo : sensitiveWords) {
String word = wordInfo.getWord();
if (word.startsWith("/") && word.endsWith("/")) {
// 正则表达式模式
String regex = word.substring(1, word.length() - 1);
if (Pattern.matches(regex, text)) {
// 使用正则表达式匹配
return new SensitiveWordInfo(word, wordInfo.getLevel());
}
}
}
return null;
}
}
通过以上优化，敏感词检测程序具备了异步检测、动态加载、分级响应、日志记录和模糊匹配等功能。
这些改进提高了程序的性能、灵活性和实用性，使其能够更好地适应实际应用场景中的需求。
遇到问题，找老架构师取经
借助此文的问题 套路 ，大家可以 放手一试，保证 offer直接到手，还有可能会 涨薪 100%-200%。
后面，尼恩java面试宝典回录成视频， 给大家打造一套进大厂的塔尖视频。
在面试之前，建议大家系统化的刷一波 5000页《尼恩Java面试宝典PDF》，里边有大量的大厂真题、面试难题、架构难题。
很多小伙伴刷完后， 吊打面试官， 大厂横着走。
在刷题过程中，如果有啥问题，大家可以来 找 40岁老架构师尼恩交流。
另外，如果没有面试机会，可以找尼恩来改简历、做帮扶。
遇到职业难题，找老架构取经， 可以省去太多的折腾，省去太多的弯路。
尼恩指导了大量的小伙伴上岸，前段时间，刚指导 32岁 高中生，冲大厂成功。特批 成为 架构师，年薪 50W，逆天改命 ！！！。
狠狠卷，实现 “offer自由” 很容易的， 前段时间一个武汉的跟着尼恩卷了2年的小伙伴， 在极度严寒/痛苦被裁的环境下， offer拿到手软， 实现真正的 “offer自由” 。
