这份 数据结构专题 面向计算机基础学习和算法面试复习，整理数组、链表、栈、队列、树、图、堆、红黑树、布隆过滤器等常见结构。

适合谁看

• 正在系统学习数据结构的后端开发者。
• 准备算法题、Java 集合、数据库索引、缓存等相关面试的同学。
• 对常见数据结构的操作复杂度和适用场景不够熟的读者。
• 想把数据结构和真实工程组件联系起来的工程师。

学习重点

• 数据结构的核心是“数据如何组织，以及这种组织方式带来什么复杂度和场景优势”。
• 线性结构适合理解顺序存储、链式存储、栈队列模型和常见业务队列。
• 树和图是很多算法、索引、路由、依赖关系和层级结构的基础。
• 堆、红黑树、布隆过滤器属于工程中很常见的高频结构。
• 学数据结构要配合算法题和工程场景，否则容易只记住定义。

敏感词过滤是内容安全的核心环节。无论是社交媒体、电商平台、在线游戏，还是如今的 AI 应用，都需要对输入和生成的内容进行实时过滤，防止色情、暴力、仇恨言论等违规信息传播。

从技术角度看，敏感词过滤本质上是多模式字符串匹配问题：在一段文本中同时查找多个关键词。

这篇文章接近 2 万字，我会从算法演进开始讲起，还会分享一些生产经验例如对抗变形词、高并发优化、词库管理。

核心结论：

红黑树介绍

红黑树（Red Black Tree）是一种自平衡二叉查找树。它是在 1972 年由 Rudolf Bayer 发明的，当时被称为平衡二叉 B 树（symmetric binary B-trees）。后来，在 1978 年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

由于其自平衡的特性，保证了最坏情形下在 O(logn) 时间复杂度内完成查找、增加、删除等操作，性能表现稳定。

在 JDK 中，TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。

树就是一种类似现实生活中的树的数据结构（倒置的树）。任何一棵非空树只有一个根节点。

一棵树具有以下特点：

1. 一棵树中的任意两个结点有且仅有唯一的一条路径连通。
2. 一棵树如果有 n 个结点，那么它一定恰好有 n-1 条边。
3. 一棵树不包含回路。

下图就是一棵树，并且是一棵二叉树。

什么是堆

堆是一种满足以下条件的树：

堆中的每一个节点值都大于等于（或小于等于）子树中所有节点的值。或者说，任意一个节点的值都大于等于（或小于等于）所有子节点的值。

大家可以把堆（最大堆）理解为一个公司，这个公司很公平，谁能力强谁就当老大，不存在弱的人当老大，老大手底下的人一定不会比他强。这样有助于理解后续堆的操作。

!!!特别提示：

• 很多博客说堆是完全二叉树，其实并非如此，堆不一定是完全二叉树，只是为了方便存储和索引，我们通常用完全二叉树的形式来表示堆，事实上，广为人知的斐波那契堆和二项堆就不是完全二叉树，它们甚至都不是二叉树。
• （二叉）堆是一个数组，它可以被看成是一个 近似的完全二叉树。——《算法导论》第三版

图是一种较为复杂的非线性结构。为啥说其较为复杂呢？

根据前面的内容，我们知道：

• 线性数据结构的元素满足唯一的线性关系，每个元素（除第一个和最后一个外）只有一个直接前趋和一个直接后继。
• 树形数据结构的元素之间有着明显的层次关系。

但是，图形结构的元素之间的关系是任意的。

何为图呢？ 简单来说，图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为：G(V,E)，其中，G 表示一个图，V 表示顶点的集合，E 表示边的集合。

1. 数组

数组（Array） 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。

我们直接可以利用元素的索引（index）可以计算出该元素对应的存储地址。

数组的特点是：提供随机访问 并且容量有限。

假如数组的长度为 n。
访问：O(1) //访问特定位置的元素
插入：O(n) //最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除：O(n) //最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时

布隆过滤器相信大家没用过的话，也已经听过了。

布隆过滤器主要是为了解决海量数据的存在性问题。对于海量数据中判定某个数据是否存在且容忍轻微误差这一场景（比如缓存穿透、海量数据去重）来说，非常适合。

文章内容概览：

1. 什么是布隆过滤器？
2. 布隆过滤器的原理介绍。
3. 布隆过滤器使用场景。
4. 通过 Java 编程手动实现布隆过滤器。
5. 利用 Google 开源的 Guava 中自带的布隆过滤器。
6. Redis 中的布隆过滤器。

什么是布隆过滤器？