基本概念

布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出，是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。-- 维基百科

【资料图】

查找问题建模

如何判断某个元素是否存在于一个集合中？

比较直观的做法是将所有元素保存起来，然后逐个比较确认结果，建模转换为具体的数据结构：

线性结构: 数组、链表等，时间复杂度为 O(N), 空间复杂度为 O(N)

散列表结构: Map、HashTable 等, 时间复杂度为 O(1), 空间复杂度为 O(N)

树形结构: AVL、RBTree 等, 时间复杂度为 O(logN), 空间复杂度为 O(N)

常见的数据结构随着元素的增加，存储空间也会越来越大，同时查询速度也会越来越慢 (散列表结构不受影响)，如果我们希望在保持时间复杂度为 O(N) 的前提下，尽可能地降低内存占用，就需要转换一下思路：保存特征数据，而非所有数据。什么是特征数据？简单来说，就是能够唯一标识出其对应的源数据，比如常见的 用户 ID、游戏中奖 ID、管理后台审批流 ID 等。

原理和应用场景

布隆过滤器的原理: 当一个元素被加入集合时，通过 K 个哈希函数 将元素映射到一个位图数据结构 (例如 bitmap) 中的 K 个位置上面，并将这些位置全部置为 1。判断元素是否存在于集合时，只需查看 K 个哈希函数 映射后的 K 个位置上面的值即可。

如果这些位置任意一个为 0，则表示被检测元素一定不存在于集合中，如果都是 1，则表示被检测元素有较大可能存在于集合中。

为什么不能检测 “一定存在” ?

检测元素时可以返回 “一定不存在” 和 “可能存在”，因为可能有多个元素映射到相同的 bit 上面，导致该位置为 1, 那么一个不存在的元素也可能会被误判为存在，所以无法提供 “一定存在” 的语义保证。

为什么元素不允许被 “删除” ?

如果删除了某个元素，导致对应的 bit 位置为 0, 但是可能有多个元素映射到相同的 bit 上面，那么一个存在的元素会被误判为不存在 (这是不可接收的)，所以为了 “一定不存在” 的语义保证，元素不允许被删除。

PS: 虽然可以引入一个 删除计数器 来解决上述问题，不过这需要引入额外的空间，失去了使用过滤器的意义。

两个语义操作

Add: 添加一个元素到集合中

Test: 检查给定元素是否存在于集合中

示例

URL 去重

假设下面的 URL 列表为采集队列 (一共 100 条数据)，我们希望采集完成的 URL 可以记录起来，避免多次采集，如果使用正常的字符串存储的话 (以 Go 语言为例，string 占用 16 bytes)，大概需要 16 bytes * 100 = 1600 bytes 内存空间。

https://www.example.com/u/101/profilehttps://www.example.com/u/102/profile...https://www.example.com/u/200/profile

而如果我们改为 布隆过滤器 的方式来记录的话，假设哈希函数可以将每个链接转换为 1 个 0-255 的数字，通过将数据存入一个 bitmap,那么理想情况下 (不发生任何碰撞) 最终只需要 1 个 byte 的内存空间即可，内存使用直接降低了 1600 倍。

#布隆过滤器记录URL只需要1个byte------------------------------------|0|1|2|3|...|255|------------------------------------|URL|URL|URL|||URL|------------------------------------

网站用户性别

假设网站的用户数量为 1000 万，每个用户性别存储需要 1 个 bytes, 如果正常存储的话，大概需要 1 byte * 1000 W ≈ 10 MB 内存空间。

而如果我们改为 布隆过滤器 的方式来记录的话，假设用户 ID 是一个数字，通过将数据存入一个 bitmap, 那么 1 byte 可以表示 256 个 用户性别，理想情况下 (不发生任何碰撞) 最终只需要 1000 W / 256 * 1 byte ≈ 0.04 MB 内存空间，内存使用直接降低了 256 倍。

#布隆过滤器记录用户网站性别--------------------------------------------------|0|1|2|3|...|9999999|--------------------------------------------------|User1|User2|User3|User4|...|User...|--------------------------------------------------

其他应用场景

垃圾邮件过滤

防止缓存穿透

业务记录计数器

Web 拦截

两个核心支撑点

通过上面两个简单的应用场景可以看到，要实现一个健壮的 布隆过滤器，需要规划设计好两个技术点：

元素长度和用于存储哈希映射值的数据结构，一般使用 bitmap (具体的长度和存储规模有关)

显著降低碰撞、性能优良的哈希函数

Murmur3，FNV 系列和 Jenkins 等非密码学算法适合作为哈希函数，其中 Murmur3 因为易于实现，并且在速度和随机分布上有很好的权衡，实践中多选用其作为 布隆过滤器 的哈希函数。

数学部分

一个 布隆过滤器 至少需要包含如下参数:

哈希空间大小，记为 m

元素集合大小，记为 n

哈希函数个数，记为 k

误判概率，记为 p (可能出现一个元素不在集合中，但是被误判为存在于集合中，这个误判的概率取值范围为 0 - 1)

哈希函数个数满足以下公式时，布隆过滤器 有最好的效果(数学证明部分省略，数学渣暴露了 :( ... )

k = [(ln2)(m/n)]

还是以刚才的 网站用户性别 为例，1000W 用户需要以不高于 0.00001% 误判率的的情况下被检测到，需要多少个哈希函数？需要耗费多少空间？

#带入公式计算n=ceil(m/(-k/log(1-exp(log(p)/k))))p=pow(1-exp(-k/(m/n)),k)m=ceil((n*log(p))/log(1/pow(2,log(2))))k=round((m/n)*log(2))

记不住数学公式？没关系，已经有大佬做好了一个 在线工具^[1]，可以通过输入参数直接生成对应的哈希函数个数。

Bloom Filter Calculator

开源库

笔者选择了 bits-and-blooms/bloom^[2]作为研究 布隆过滤器 代码实现，版本为 v3.3.1。

安装组件

$goget-ugithub.com/bits-and-blooms/bloom/v3

示例

初始化过滤器时，需要知道对应的业务场景有多少元素（期望的容量），以及期望的误判概率。常见的误判率为 1%, 误报率越低，需要的内存就越多，同时容量越大，需要的内存就越多。

初始化过滤器时，应该尽可能明确需要的元素数量，因为 布隆过滤器 不是动态数据结构，如果指定的元素数量太少，则可能会超出误判概率范围。

packagemainimport"github.com/bits-and-blooms/bloom"funcmain(){//初始化能够接收100万个元素且误判率为1%的布隆过滤器filter:=bloom.NewWithEstimates(1000000,0.01)hw:=[]byte(`helloworld`)hg:=[]byte(`hellogolang`)filter.Add(hw)println(filter.Test(hw))//trueprintln(filter.Test(hg))//false}

我们只添加了 hello world 字符串到过滤器中，所以正常的输出应该是 true false:

$gorunmain.gotruefalse

源码分析

接下来，我们来简单分析下 bits-and-blooms/bloom 的实现代码。

哈希算法选择

modulegithub.com/bits-and-blooms/bloom/v3go1.14require(github.com/bits-and-blooms/bitsetv1.3.1github.com/twmb/murmur3v1.1.6)

从 bits-and-blooms/bloom 的依赖包中，可以看到其选择了 murmur3 算法作为哈希函数实现。

BloomFilter

BloomFilter 结构体表示一个 布隆过滤器，包含 3 个字段，分别对应上文提到的 布隆过滤器 的必要参数。

typeBloomFilterstruct{muint//哈希空间大小kuint//哈希函数个数b*bitset.BitSet//bitmap}

初始化过滤器

NewWithEstimates 方法创建一个 布隆过滤器，内部调用了 EstimateParameters 方法来计算 m 和 k 的值，最后通过 m 和 k 初始化一个 BloomFilter 结构体并返回。

funcNewWithEstimates(nuint,fpfloat64)*BloomFilter{m,k:=EstimateParameters(n,fp)returnNew(m,k)}funcEstimateParameters(nuint,pfloat64)(muint,kuint){m=uint(math.Ceil(-1*float64(n)*math.Log(p)/math.Pow(math.Log(2),2)))k=uint(math.Ceil(math.Log(2)*float64(m)/float64(n)))return}

添加元素

BloomFilter.Add 方法添加一个元素到 布隆过滤器，返回当前的 BloomFilter 对象来支持链式调用。

func(f*BloomFilter)Add(data[]byte)*BloomFilter{h:=baseHashes(data)fori:=uint(0);ibaseHashes 函数返回哈希函数计算出的哈希值，其内部调用了 murmur3 算法。

funcbaseHashes(data[]byte)[4]uint64{...}

location 函数返回哈希值对应的 bitmap 的位置索引，通过将 bitmap 对应的位置进行设置，就可以将元素添加到 布隆过滤器 了。

funclocation(h[4]uint64,iuint)uint64{...}

检测元素

BloomFilter.Test 方法检测一个元素是否存在于 布隆过滤器 中，可以看到，其内部实现就是 BloomFilter.Add 方法的逆过程。

func(f*BloomFilter)Test(data[]byte)bool{h:=baseHashes(data)fori:=uint(0);i调用流程图调用流程图

小结

本文简述了 布隆过滤器 的基本概念和原理，并通过开源库 bits-and-blooms/bloom 的实现代码分析了实现 布隆过滤器 的核心技术点，最后引用维基百科关于 布隆过滤器 的优缺点作为文章结尾。

优点

布隆过滤器 在算法的空间复杂度和时间复杂度方面都有巨大的优势，Add 和 Test 操作的时间复杂度都是常数 O(K) (K: 哈希函数个数)。由于哈希函数相互之间没有关联，因此可以通过硬件并行实现计算加速，此外，由于 布隆过滤器 不存储源数据，在某些对数据保密要求非常严格的场景 (数据可用，但不可见) 有明显优势。最后，在哈希空间向量长度相同的情况下，使用同一组哈希函数的两个 布隆过滤器 的 集合相关运算可以使用位操作进行。

缺点

布隆过滤器 最明显的的缺点就是 误判率，随着元素数量增加，误判率 也随之增加，所以如果元素数量很少的情况下，使用 map 就可以了。此外，布隆过滤器 不支持删除元素， 因为 布隆过滤器 只能确定元素一定不存在于集合中，无法确定元素一定存在于集合中，如果一定要删除某个元素，则必须重新构建整个 布隆过滤器。

Reference

布隆过滤器 - 维基百科^[3]

bits-and-blooms/bloom^[4]

Bloom Filters^[5]

经典论文解读——布隆过滤器

白话布隆过滤器 BloomFilter

Bloom and Cuckoo Filters - Awesome Go^[6]

redis bitmap^[7]

CUCKOO FILTER：设计与实现^[8]

链接

[1]

在线工具: https://hur.st/bloomfilter/

[2]

bits-and-blooms/bloom: https://github.com/bits-and-blooms/bloom

[3]

布隆过滤器 - 维基百科: https://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8

[4]

bits-and-blooms/bloom: https://github.com/bits-and-blooms/bloom

[5]

Bloom Filters: https://www.jasondavies.com/bloomfilter/

[6]

Bloom and Cuckoo Filters - Awesome Go: https://awesome-go.com/bloom-and-cuckoo-filters/

[7]

redis bitmap: https://redis.io/commands/?group=bitmap

[8]

CUCKOO FILTER：设计与实现: https://coolshell.cn/articles/17225.html

推荐阅读

Go：详解布隆过滤器原理与实现

福利

我为大家整理了一份从入门到进阶的Go学习资料礼包，包含学习建议：入门看什么，进阶看什么。关注公众号 「polarisxu」，回复ebook获取；还可以回复「进群」，和数万 Gopher 交流学习。

关键词：