前言

博客：http://blog.healerjean.com

一、布隆过滤器

1、引入

上一节我们学会了使用 HyperLogLog 数据结构来进行估数，它非常有价值，可以解决很多精确度不高的统计需求。

但是如果我们想知道某一个值是不是已经在 HyperLogLog 结构里面了，它就无能为力了，它只提供了 pfadd 和 pfcount 方法，没有提供 pfcontains 这种方法。

问题1：我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的?

答案：你会想到服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。

问题2：问题是当用户量很大，每个用户看过的新闻又很多的情况下，这种方式，推荐系统的去重工作在性能上跟的上么?

答案：实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行 exists 查询，当系统并发量很高时，数据库是很难扛住压力的。

问题3：不使用数据库，那使用什么呢？

答案：你可能又想到了缓存，但是如此多的历史记录全部缓存起来，那得浪费多大存储空间啊?而且这个存储空间是随着时间线性增长，你撑得住一个月，你能撑得住几年么? 但是不缓存的话，性能又跟不上，这该怎么办 ?

问题4：缓存都扛不住，那还能用啥呢？

这时，布隆过滤器 (Bloom Filter) 闪亮登场了，它就是专门用来解决这种去重问题的。

问题5：为什么用布隆过滤器呢？

答案：它在起到去重的同时，在空间上还能节省 90% 以上，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。

问题6：布隆过滤器有什么缺点呢？

答案：只是稍有那么点不精确，也就是有一定的误判概率

2、布隆过滤器是什么？

布隆过滤器可以理解为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某个对象是否存在时，它可能会误判。

1、但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率

2、当布隆过滤器说某个值存在时，这个值可能不存在，当它说不存在时，那就肯定不存在。

套在上面的使用场景中，布隆过滤器能准确过滤掉那些已经看过的内容，那些没有看过的新内容，它也会过滤掉极小一部分 (误判)，但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。

3、`Redis` 中的布隆过滤器

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。(我这里没有进行安装，所以就看着文档过一下吧，以后有需要再回来看)

命令	说明
`bf.add`	添加元素
`bf.madd`	批量添加元素
`bf.exists`	查询元素是否存在
`bf.mexists`	批量查询元素是否存在

1）默认的布隆过滤器

在我们第一次 add 的时候自动创建默认参数的布隆过滤器

默认的 error_rate 是 0.01，默认的 initial_size 是 100。

127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1

127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2 
(integer) 1
127.0.0.1:6379> bf.exists codehole user3 
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0


127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1

127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7 
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

2）自定义的布隆过滤器

Redis 其实还提供了自定义参数的布隆过滤器，需要我们在 add 之前使用 bf.reserve 指令显式创建。如果对应的 key 已经存在，bf.reserve 会报错。bf.reserve 有三个参数，分别

⬤ key

⬤ error_rate ：错误率越低，需要的空间越大。

⬤ initial_size 参数表示预计放入的元素数量，当实际数量超出这个数值时，误判率会上升，所以需要提前设置一个较大的数值避免超出导致误判率升高。

4、布隆过滤器的原理

每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。

[0][1][0]...[1]  ← m位的位数组（全0初始化）
  │   │        │
  ▼   ▼        ▼
hash1(x) hash2(x) ... hashk(x)  ← k个独立哈希函数

1）`add`：添加元素

向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

2）`exists`：校验元素是否存在

向布隆过滤器询问 key 是否存在时，跟 add 一样，也会把 hash 的几个位置都算出来，看看位数组中这几个位置是否都位 1

1、只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在。

2、如果都是 1，这并不能说明这个 key 就一定存在，只是极有可能存在，因为这些位被置为 1 可能是因为其它的 key 存在所致。如果这个位数组比较稀疏，这个概率就会很大，如果这个位数组比较拥挤，这个概率就会降低。具体的概率计算公式比较复杂，感兴趣可以阅读扩展阅读，非常烧脑，不建议读者细看。

3）空间占用估计

布隆过滤器的空间占用有一个简单的计算公式，但是推导比较繁琐，这里就省去推导过程了，直接引出计算公式

布隆过滤器有两个参数，第一个是预计元素的数量 n，第二个是错误率 f。公式根据这两个输入得到两个输出，第一个输出是位数组的长度 L，也就是需要的存储空间大小 (bit)，第二个输出是 hash 函数的最佳数量 k。hash 函数的数量也会直接影响到错误率，最佳的数量会有最低的错误率。

a、参数控制

initial_size：布隆过滤器的 initial_size 估计的过大，会浪费存储空间，估计的过小，就会影响准确率，用户在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出估计值很多。
error_rate ：布隆过滤器的 error_rate 越小，需要的存储空间就越大，对于不需要过于精确的场合， error_rate 设置稍大一点也无伤大雅。（比如在新闻去重上而言，误判率高一点只会让小部分文章不能让合适的人看到，文章的整体阅读量不会因为这点误判率就带来巨大的改变）

输入	说明
`n`	预计元素的数量 `n`
`f`	错误率 `f`

输出	说明
`L`	位数组的长度 `L`，也就是需要的存储空间大小 `(bit)`
`k`	`hash` 函数的最佳数量 `k`

k = 0.7*(1/n) # 约等于

f = 0.6185^(L/n)   #表示次方计算，也就是 math.pow

1、位数组相对越长 (l/n)，错误率 f 越低，这个和直观上理解是一致的

2、位数组相对越长 (l/n)，hash 函数需要的最佳数量也越多，影响计算效率

3、当一个元素平均需要 1 个字节 (8bit) 的指纹空间时 (L/n=8)，错误率大约为 2%

4、错误率为 10%，一个元素需要的平均指纹空间为 4.792 个 bit，大约为 5bit

5、错误率为1%，一个元素需要的平均指纹空间为 9.585 个 bit，大约为 10bit

6、错误率为 0.1%，一个元素需要的平均指纹空间为 14.377 个 bit，大约为 15bit

b、空间计算

问题：你也许会想，如果一个元素需要占据 15 个 bit，那相对 set 集合的空间优势是不是就没有那么明显了?

答案：这里需要明确的是，set 中会存储每个元素的内容，而布隆过滤器仅仅存储元素的指纹。

1、元素的内容大小就是字符串的长度，它一般会有多个字节，甚至是几十个上百个字节

2、每个元素本身还需要一个指针被 set 集合来引用，这个指针又会占去 4 个字节或 8 个字节，取决于系统是 32bit 还是 64bit。而指纹空间只有接近 2 个字节，所以布隆过滤器的空间优势还是非常明显的。

问题：计算太麻烦了，有没有一个计算的工具呢？

https://krisives.github.io/bloom-calculator/

c、误判率变化

当实际元素超出预计元素时，错误率会有多大变化，它会急剧上升么，还是平缓地上升，这就需要另外一个公式，引入参数 t 表示实际元素和预计元素的倍数

f = (1-0.5^t) ^ k # 极限近似，k 是 hash 函数的最佳数量

当 t 增大时，错误率，f 也会跟着增大，分别选择错误率为 10% ,1%, 0.1% 的 k 值，画出它的曲线进行直观观察。

从这个图中可以看出曲线还是比较陡峭的

1、错误率为 10% 时，倍数比为 2 时，错误率就会升至接近 40%，这个就比较危险了

2、错误率为 1% 时，倍数比为 2 时，错误率升至 15%，也挺可怕的

3、错误率为 0.1%，倍数比为 2 时，错误率升至 5%，也比较悬了

d、超出初始化大小怎么办？

使用时不要让实际元素远大于初始化大小，由于 error_rate 不会因为数量超出就急剧增加，这就给我们重建过滤器提供了较为宽松的时间，所以当实际元素开始超出初始化大小时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进去

注意：这就要求我们在其它的存储器中记录所有的历史元素，所以尽量一开始就尽量想好多大合适

e、最大长度

RedisBloom 2.0+版本:
- 默认最大容量: 1,000,000,000 (10亿)
- 计数器类型：使用uint32_t(32位无符号整数)
- 理论上限：4,294,967,295(2³²-1，约43亿)
- 错误信息: ERR capacity exceeds maximum limit (1000000000)
生产环境建议最大设为 440,000,000（4.4 亿），留出安全余量；
对应内存约 527 MB，更稳妥。

项目	值
最大预估容量（n）	448,000,000（4.48 亿）
理论位数组长度	≈ 4,293,480,000 bits
实际分配位数组长度	≈ 4,294,080,000 bits（对齐后）
`Redis` 内存占用	≈ 536.8 ~ 537 MB

5、布隆过滤器的场景

1、邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，因为用了这个过滤器，所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中，这个就是误判所致，概率很低

2、布隆过滤器可以显著降低数据库的 IO 请求数量。当用户来查询某个 row 时，可以先通过内存中的布隆过滤器过滤掉大量不存在的 row 请求，然后再去磁盘进行查询。

6、其他布隆过滤器

1）`java`

1）`com.google.guava`

<dependencies>  
  <dependency>  
    <groupId>com.google.guava</groupId>  
    <artifactId>guava</artifactId>  
    <version>23.0</version>  
  </dependency>  
</dependencies> 

public class BloomFilterTest {

  private static final int capacity = 1000000;
  private static final int key = 999998;

  private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), capacity);

  static {
    for (int i = 0; i < capacity; i++) {
      bloomFilter.put(i);
    }
  }

  public static void main(String[] args) {
    /*返回计算机最精确的时间，单位微妙*/
    long start = System.nanoTime();

    if (bloomFilter.mightContain(key)) {
      System.out.println("成功过滤到" + key);
    }
    long end = System.nanoTime();
    System.out.println("布隆过滤器消耗时间:" + (end - start));
    int sum = 0;
    for (int i = capacity + 20000; i < capacity + 30000; i++) {
      if (bloomFilter.mightContain(i)) {
        sum = sum + 1;
      }
    }
    System.out.println("错判率为:" + sum);
  }
}



// 成功过滤到999998
// 布隆过滤器消耗时间:215518
// 错判率为:318
//可以看到，100w个数据中只消耗了约0.2毫秒就匹配到了key，速度足够快。然后模拟了1w个不存在于布隆过滤器中的key，匹配错误率为318/10000，也就是说，出错率大概为3%，跟踪下BloomFilter的源码发现默认的容错率就是0.03：


public static <T> BloomFilter<T> create(Funnel<T> funnel, int expectedInsertions /* n */) {
  return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}

7、优缺点

适用场景：只读集合 + 极致查询速度 + 可容忍误判

1）优点

极致空间效率：布隆过滤器在理论上实现了判断成员存在的最小空间需求。通过位数组和多个哈希函数，以极小的空间开销（通常几个比特/元素）实现高效的存在性查询，特别适合海量数据场景。
查询速度极快：查询操作仅需计算多个哈希函数并检查位数组对应位置，无指针解引用或复杂逻辑。在现代CPU上，这些操作可高度优化甚至并行执行，实现超高吞吐量。
数据隐私保护：仅存储位数组而非原始数据，无法从过滤器中恢复原始元素。这一特性使其适合隐私敏感场景，如检查用户凭证是否在黑名单中，而不暴露黑名单内容。
实现简单可靠：算法逻辑简单，易于正确实现和验证。无复杂的重平衡或重建机制，系统稳定性高，适合对可靠性要求极高的场景。

2）缺点

存在误判率：布隆过滤器会产生假阳性（False Positive）：可能错误地认为未插入的元素存在。虽然可通过增加位数组大小和优化哈希函数数量降低误判率，但无法完全消除。且不支持调整已构建过滤器的误判率。
不支持删除操作：标准布隆过滤器不支持删除元素，因为将位数组中的位重置为0可能影响其他元素的查询结果。虽然存在计数布隆过滤器等变种支持删除，但会显著增加空间开销（通常4-8倍）。
内存访问不友好：多个哈希函数产生的位置通常在内存中随机分布，导致CPU缓存命中率低。在高并发查询场景下，这种随机内存访问可能成为性能瓶颈，尤其在大型过滤器上。
容量预设限制：需预先设定元素数量和误判率，以确定位数组大小。若实际插入元素超过预设值，误判率会急剧上升。动态扩容困难，通常需要重建整个过滤器。
哈希函数相关性问题：若使用的多个哈希函数结果存在相关性，会降低过滤器效率，增加误判率。需要确保哈希函数的独立性和高质量，增加了实现复杂度。

二、布谷鸟过滤器

布隆过滤器不记录元素本身，并且存在一个位被多个元素共用的情况，所以它不支持删除元素。布谷鸟过滤器，它支持删除操作，此外它还带来了其他优势：

1、查找性能更高：布隆过滤器要采用多种哈希函数进行多次哈希，而布谷鸟过滤器只需一次哈希

2、节省更多空间：布谷鸟过滤器记录元素更加紧凑，论文中提到，如果期望误报率在 3% 以下，半排序桶布谷鸟过滤器每个元素所占用的空间要比布隆过滤器中单个元素占用空间要小

1、为什么叫布谷鸟过滤器？

答案：布谷鸟过滤器之所以被称为“布谷鸟”，是因为它的工作原理类似于布谷鸟在自然界中的行为。布谷鸟以将自己的蛋产在其他鸟类的巢中而闻名，这样一来，寄主鸟就会抚养布谷鸟的幼鸟

在布谷鸟过滤器中，如果一个位置已经被占用，新元素会“驱逐”现有元素，将其移到其他位置。这种“驱逐”行为类似于布谷鸟将其他鸟蛋推出巢外，以便安置自己的蛋。因此，这种过滤器得名为“布谷鸟”过滤器。

2、基本原理

1、指纹（Fingerprint）：布谷鸟过滤器不是直接存储元素本身，而是存储元素的指纹。指纹是通过哈希函数计算得到的一个简短的摘要，通常比元素本身的长度要短。

2、桶（Bucket）：布谷鸟过滤器使用桶来存储指纹。每个桶可以存储一个或多个指纹，具体取决于设计。桶数组是一个固定大小的数组，每个桶可以存储一定数量的指纹。

3、哈希函数：至少两个，用于计算元素在桶数组中的两个可能位置

3、操作方式

布谷鸟过滤器由 桶数组 组成，每个桶包含多个槽位，用于存储元素的指纹（短哈希值）。对于元素 x：

计算指纹：f = hash(x) % fingerprint_max
计算两个候选位置：
- i1 = hash1(x) % num_buckets
- i2 = i1 ⊕ hash2(f)（⊕ 表示异或运算）

这两个位置是确定性的，即同一个元素始终映射到相同的 i1、i2 和 f。

每个元素有两个 “家”（通过两个哈希函数计算的位置）
当冲突发生时，当前元素会 “踢出” 其中一个位置的元素
被踢出的元素必须搬到自己的另一个家
如果另一个家也被占用，则继续踢出该位置的元素，直到找到空位或达到最大尝试次数

1）数据结构

内存布局（以1000万元素为例）：
[ 桶0 ] [ 桶1 ] ... [ 桶26,315,789 ]  ← 总桶数 = 1.05 * (n / (4槽 * 0.95装载率))
  │       │              │
  ▼       ▼              ▼
[ f1 f2 f3 f4 ] [ f1 f2 f3 f4 ] ...   ← 每桶4个槽位，f = 12-bit指纹

1）添加元素

计算元素的指纹 f
计算两个候选位置 i1 = hash1(element) 和 i2 = i1 ⊕ hash2(f)
检查两个位置的桶中是否有空闲槽位：
- 如果有，将指纹 f 存入空闲槽位
- 如果没有，随机选择一个位置的桶，踢出其中一个指纹 f'，并将新指纹 f 放入该位置
- 被踢出的指纹 f' 重复步骤 2-3，最多尝试 max_kicks 次（避免无限循环）
如果尝试次数超过 max_kicks，认为过滤器已满，插入失败

布谷鸟过滤器本质上是一个 桶数组，每个桶中保存若干数量的指纹（指纹由元素的部分 Hash 值计算出来）。定义一个布谷鸟过滤器，每个桶记录 2 个指纹，5 号桶和 11 号桶分别记录保存 a, b 和 c, d 元素的指纹，如下所示：

此时，向其中插入新的元素 e，发现它被哈希到的两个候选桶分别为 5 号和 11 号，但是这两个桶中的元素已经添加满了：

按照布谷鸟过滤器的特性，它会将其中的一个元素重哈希到其他的桶中（具体选择哪个元素，由具体的算法指定），新元素占据该元素的位置，如下：

以上便是向布谷鸟过滤器中添加元素并发生冲突时的操作流程，在我们的例子中，重新放置元素 e 触发了另一个重置，将现有的项 a 从桶 5 踢到桶 15。这个过程可能会重复，直到找到一个能容纳元素的桶，这就使得布谷鸟哈希表更加紧凑，因此可以更加节省空间。如果没有找到空桶则认为此哈希表太满，无法插入。虽然布谷鸟哈希可能执行一系列重置，但其均摊插入时间为 O(1)。

2）查询操作

计算元素的指纹 f
计算两个候选位置 i1 = hash1(element) 和 i2 = i1 ⊕ hash2(f)
检查这两个位置的桶中是否存在指纹 f
- 如果存在，返回元素可能存在（允许假阳性）
- 如果不存在，返回元素肯定不存在

3）删除操作

计算元素的指纹 f
计算两个候选位置 i1 = hash1(element) 和 i2 = i1 ⊕ hash2(f)
检查这两个位置的桶中是否存在指纹 f
- 如果存在，删除该指纹
- 如果不存在，不做任何操作

4、优缺点

适用场景：需要支持删除操作 + 低误判率 + 严格空间约束

1）优点：

支持元素删除 布谷鸟过滤器核心优势在于支持删除操作。它通过存储元素的”指纹”（哈希值的简短表示）而非完整哈希，使得删除成为可能。虽然存在极小概率误删（不同元素具有相同指纹时），但在合理配置下（如12位指纹），这种风险可控制在极低水平。
查询效率高：查询时只需检查两个可能位置（主位置和备用位置），时间复杂度为O(1)。相比布隆过滤器需要多次哈希计算和位检查，布谷鸟过滤器的内存访问模式更连续，对 CPU 缓存更友好，实际查询速度更快。
空间效率优越：在相同误判率要求下（特别是低于 3% 时），布谷鸟过滤器比布隆过滤器节省30%-50%的存储空间。这源于其紧凑的桶式结构设计和指纹压缩存储机制，使得在资源受限环境中更具优势。
- 误判率<3%：布谷鸟过滤器比标准布隆过滤器节省30%-50%空间
- 误判率>3%：标准布隆过滤器空间效率更高
- 关键点：布谷鸟过滤器的核心优势是同时提供删除功能和高空间效率
误判率可控且稳定：误判率可通过调整指纹长度和桶大小精确控制。在高负载情况下（如 90% 以上装载率），误判率增长相对平缓，不像布隆过滤器那样会急剧上升，更适合动态变化的数据集。

2）缺点

插入性能不稳定：当过滤器接近满载时，插入操作可能触发”踢出链”：需要将已有元素从一个位置移到另一个位置，造成连锁反应。在高负载下，这会导致插入延迟显著增加，极端情况下甚至需要重建整个过滤器。
不支持重复元素：布谷鸟过滤器本质上为集合（set）设计，不记录元素出现次数。同一元素多次插入只存储一个指纹，删除一次即完全移除。如需支持重复元素和精确计数，需使用扩展版本（如计数布谷鸟过滤器），但会增加空间开销。
动态扩容困难：当过滤器达到容量上限时，需要重建一个更大的过滤器并将所有元素迁移过去。这个过程可能造成服务短暂中断，在高可用系统中需要复杂的双缓冲或渐进式迁移策略。
小数据集不适用：对于元素数量较少（通常低于5万）的场景，布谷鸟过滤器的空间优势无法体现，反而不如传统哈希表高效。它的设计优化针对大规模数据集，在小数据集上显得”大材小用”。
哈希函数质量依赖：性能高度依赖哈希函数的均匀分布特性。低质量的哈希函数会导致某些桶过载，增加踢出链长度，降低整体性能。需要使用经过验证的高质量哈希算法（如MurmurHash3、SipHash）。

3）`FAQ`

a、踢出机制的优势

踢出机制是布谷鸟过滤器的核心创新，它通过强制冲突元素迁移来实现：这使得布谷鸟过滤器特别适合需要高性能、低内存占用且支持动态更新的场景，如缓存系统、网络数据包过滤、分布式系统中的成员检测等。

1、高空间利用率：布谷鸟过滤器的负载因子（元素数 / 槽位数）可以达到 0.95 以上，远高于传统哈希表（通常 0.7-0.8）。这是因为每个槽位被充分利用，冲突元素通过踢出机制分散到其他位置。

2、确定性查询时间：查询时只需检查两个位置，无论过滤器中有多少元素，时间复杂度始终为 O (1)。相比之下，传统哈希表在高负载下查询效率会下降。

3、支持删除操作：布谷鸟过滤器通过直接删除指纹来实现删除操作，而无需像布隆过滤器（Bloom Filter）那样需要额外的计数器。这得益于每个元素的指纹唯一存在于两个确定位置之一。

b. 踢出机制的潜在问题

1、插入失败：如果踢出链过长（超过预设的最大尝试次数），插入操作可能失败。此时需要扩容过滤器或采用更复杂的变体（如多哈希布谷鸟过滤器）。

2、性能波动：插入操作的时间复杂度在最坏情况下为 O (k)（k 为最大尝试次数），但平均情况下接近 O (1)。这使得布谷鸟过滤器在实时系统中需要谨慎使用。

5、应用场景

布谷鸟过滤器适用于需要高效查询、支持动态更新（插入和删除）并且可以容忍一定误报率的场景，例如：

1、数据库索引：在数据库中，可以用来加速查询过程。

2、网络安全：用于快速识别已知的恶意IP地址或URL。

3、内存管理：用于跟踪页面的存在性，提高内存管理效率。

三、使用场景

1、误判率要求（首要判断条件）

1）< 0.1% 极低误判率：

✅ 布谷鸟过滤器（12-16位指纹）
❌ 避免标准布隆过滤器（空间开销过大）
空间对比：布谷鸟≈15位/元素，布隆≈20位/元素

2）0.1% - 3% 低误判率：

✅ 布谷鸟过滤器（8-12位指纹）
⚠️ 标准布隆过滤器可行但空间效率较低
📊 空间对比：1%误判率时，布谷鸟7位/元素 vs 布隆9.6位/元素

3）3% - 10% 中等误判率：

✅ 标准布隆过滤器（空间效率最优）
⚠️ 布谷鸟过滤器可行，但失去空间优势
📊 空间对比：5%误判率时，布隆5位/元素 vs 布谷鸟7位/元素

4）> 10% 高误判率：

✅ 标准布隆过滤器（显著优势）
❌ 避免布谷鸟过滤器（过度设计）
📊 空间对比：20%误判率时，布隆3位/元素 vs 布谷鸟7位/元素

2、删除操作需求

1）必须支持删除：

✅ 布谷鸟过滤器（首选）
⚠️ 计数布隆过滤器（仅当数据集小且简单性优先）
📊 空间对比：布谷鸟7位/元素 vs 计数布隆28位/元素（4倍开销）

2）偶尔需要删除（<1%操作）：

✅ 标准布隆过滤器 + 定期重建策略
⚠️ 布谷鸟过滤器（可行但可能过度设计）
💡 实践技巧：记录删除操作，达到阈值（如0.5%数据量）时重建过滤器

3、数据集规模

1）< 10,000 小型数据集：

✅ 哈希表（HashMap/Dictionary）
❌ 避免任何过滤器（常量开销过大）
📊 空间对比：1,000元素时，哈希表 8KB vs 布谷鸟15KB

2）10,000 - 1,000,000 中型数据集：

✅ 有删除需求：布谷鸟过滤器
✅ 无删除需求+低误判率：布谷鸟过滤器
✅ 无删除需求+高误判率：标准布隆过滤器

3）> 1,000,000 大型数据集：

✅ 有删除需求：布谷鸟过滤器（唯一可行方案）
✅ 无删除需求：根据误判率选择，但布谷鸟在低误判率下有优势
💡 优化技巧：考虑分片策略，将大过滤器拆分为多个小过滤器

4、性能要求

1）查询密集型（读:写 > 100:1）：

✅ 布谷鸟过滤器（固定2次内存访问，缓存友好）
⚠️ 标准布隆过滤器（多哈希计算，随机内存访问）
📊 性能对比：10^6 QPS下，布谷鸟P99延迟12μs vs 布隆28μs

2）插入密集型（写:读 > 10:1）：

✅ 标准布隆过滤器（插入性能稳定）
⚠️ 布谷鸟过滤器（高负载下踢出链导致延迟波动）
⚠️ 布谷鸟优化方案：预留20%空间，90%装载率触发异步重建

3）延迟敏感型（P99<10μs）：

✅ 布谷鸟过滤器（更可预测的延迟分布）
❌ 避免布隆过滤器（随机内存访问导致长尾延迟）
💡 优化技巧：使用SIMD指令并行处理多个指纹

5、系统可靠性要求

1）关键系统（航空/医疗/金融核心）：

✅ 标准布隆过滤器（代码简单，边界情况少）
❌ 避免布谷鸟过滤器（复杂状态机，重建风险）
📊 代码复杂度：布隆<100行 vs 布谷鸟500+行

2）常规业务系统：

✅ 根据功能需求选择
💡 实践建议：使用经过验证的开源实现（如RedisBloom模块）

6、隐私与安全要求

1）高隐私要求（用户数据/凭证）：

✅ 标准布隆过滤器（仅存位图，无法恢复原始数据）
❌ 避免布谷鸟过滤器（存储指纹，存在理论逆向风险）
🌰 典型场景：密码泄露检查、敏感ID过滤

2）中等隐私要求：

✅ 布谷鸟过滤器（使用加密哈希生成指纹）
💡 优化技巧：使用HMAC或加盐哈希增强安全性

3）低隐私要求（公开数据）：

✅ 根据性能需求自由选择
🌰 典型场景：URL去重、公开商品ID过滤

ContactAuthor

一、布隆过滤器

1、引入

2、布隆过滤器是什么？

3、Redis 中的布隆过滤器

1）默认的布隆过滤器

2）自定义的布隆过滤器

4、布隆过滤器的原理

1）add：添加元素

2）exists：校验元素是否存在

3）空间占用估计

a、参数控制

b、空间计算

c、误判率变化

d、超出初始化大小怎么办？

e、最大长度

5、布隆过滤器的场景

6、其他布隆过滤器

1）java

1）com.google.guava

7、优缺点

1）优点

2）缺点

二、布谷鸟过滤器

1、为什么叫布谷鸟过滤器？

2、基本原理

3、操作方式

1）数据结构

1）添加元素

2）查询操作

3）删除操作

4、优缺点

1）优点：

2）缺点

3）FAQ

a、踢出机制的优势

b. 踢出机制的潜在问题

5、应用场景

三、使用场景

1、误判率要求（首要判断条件）

1）< 0.1% 极低误判率：

2）0.1% - 3% 低误判率：

3）3% - 10% 中等误判率：

4）> 10% 高误判率：

2、删除操作需求

1）必须支持删除：

2）偶尔需要删除（<1%操作）：

3、数据集规模

1）< 10,000 小型数据集：

2）10,000 - 1,000,000 中型数据集：

3）> 1,000,000 大型数据集：

4、性能要求

1）查询密集型（读:写 > 100:1）：

2）插入密集型（写:读 > 10:1）：

3）延迟敏感型（P99<10μs）：

5、系统可靠性要求

1）关键系统（航空/医疗/金融核心）：

2）常规业务系统：

6、隐私与安全要求

1）高隐私要求（用户数据/凭证）：

2）中等隐私要求：

3）低隐私要求（公开数据）：

3、`Redis` 中的布隆过滤器

1）`add`：添加元素

2）`exists`：校验元素是否存在

1）`java`

1）`com.google.guava`

3）`FAQ`