前言
在上一篇文章中，我们见识了位图（Bitset）在处理海量整型数据时的恐怖统治力：仅需 500MB 内存就能处理 40 亿个整数的查找与去重。
但是，现实工程中我们遇到的往往不是纯数字。比如：
爬虫系统需要对 10 亿个 URL 进行去重。垃圾邮件过滤系统需要判断一个邮箱地址是否在千万级的黑名单中。数据库防止'缓存穿透'，需要快速判断一个查询条件（通常是字符串）是否存在。
URL 和邮箱都是字符串，位图只能存整型，如果用哈希把字符串转成整型存入位图，会遇到极其严重的哈希冲突（不同的字符串算出了同一个整型，导致误判）。
为了在极致压缩空间的同时，尽可能降低字符串映射带来的哈希冲突，1970 年，Burton Howard Bloom 提出了一个绝妙的数据结构——布隆过滤器（Bloom Filter）。
一、布隆过滤器的核心原理
1.1 基本概念
布隆过滤器的本质是：一个极长的位图（Bitset） + 多个相互独立的哈希函数。
空间效率极高：不存储元素本身，只存储映射标记查询结果概率性：判断不存在一定正确，判断存在可能误判
1.2 核心特性
| 特性 | 说明 |
|---|---|
| 假阳性（False Positive） | 可能误判存在的元素为不存在（有概率） |
| 假阴性（False Negative） | 绝不误判不存在的元素为存在（100%准确） |
| 删除操作 | 标准实现不支持删除 |
1.3 工作原理图解
1.3.1 插入元素过程
初始状态：位图全 0 [0][0][0][0][0][0][0][0][0][0]
插入"find"：
哈希函数 1 → 位置 2
哈希函数 2 → 位置 5
哈希函数 3 → 位置 7
结果： [0][1][0][0][1][0][1][][][]
↑ ↑ ↑
h1= h2= h3=
