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

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

文章内容概览：

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

什么是布隆过滤器？

图的详细讲解

1. 图的定义与特点

图是一种非线性数据结构，由顶点集合 ( V ) 和边集合 ( E ) 组成，通常表示为 ( G(V, E) )：

• 顶点（Vertex）：图中的基本单位，例如社交网络中的用户。
• 边（Edge）：连接顶点的线，表示顶点之间的关系，例如好友关系。

图的主要特点：

1. 关系的复杂性：顶点之间的关系可以是任意的，不局限于层次结构或线性关系。
2. 多样性：
   • 有向图：边有方向，例如 A 指向 B。
   • 无向图：边无方向，例如 A 和 B 互为邻居。
   • 带权图：边有权重，表示关系的强弱或代价。
   • 无权图：边仅表示是否存在关系。

什么是堆

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

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

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

!!!特别提示：

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

数组

定义

数组（Array）是一种常见的数据结构，用于存储相同类型的元素，并且这些元素在内存中是连续存储的。通过索引（Index）可以直接访问数组中的任意元素。

特点

1. 连续内存：数组的元素存储在连续的内存块中。
2. 相同类型：数组中的所有元素必须是相同的数据类型。
3. 随机访问：由于连续存储，数组支持通过索引直接访问元素，时间复杂度为 ( O(1) )。
4. 容量固定：数组的大小在创建时确定，不能动态调整。

红黑树介绍

红黑树（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. 什么是树？

树是一种分层数据结构，由一个根节点及其子节点组成。与现实中的树不同，计算机中的树是“倒置”的，根节点在上，叶子节点在下。

树的基本特点：

1. 树中的任意两个节点之间有且仅有一条路径连通。
2. 一棵树如果有 ( n ) 个节点，则一定有 ( n - 1 ) 条边。
3. 树中不包含回路。

---

2. 树的基本概念

2.1 常见术语

• 节点：树中的每个元素。
• 根节点：没有父节点的节点，树的起点。
• 子节点：某节点的直接下属。
• 父节点：某节点的直接上级。
• 兄弟节点：同一父节点的子节点。
• 叶子节点：没有子节点的节点。
• 节点的高度：从节点到叶子节点的最长路径所包含的边数。
• 节点的深度：从根节点到该节点的路径所包含的边数。
• 节点的层数：节点的深度 + 1。
• 树的高度：根节点的高度。