假设你正在研发一个游戏，这个游戏有登录的功能，在登录的时候用户输入用户名，然后我们后台需要对用户名是否存在进行判断。

想象一下，我们该如何判断用户名是否已经被注册过了呢？

你可能会想到以下解决方案

第一种：暴力查询，用户输入用户名，传到后台，后台查询mysql数据库，将查询结果返回后台，后台返回给前端。但随着用户的增加，校验用户是否存在若直接查询数据库，则会对数据库造成很大的压力

第二种：将用户名存储在 redis 的 set 中，查询的时间复杂度为O(1)，看起来很不错。问题是用户多了之后，比如有一亿的用户，我们把一亿条用户存储到 redis 将占用几十 G 的内存，一年需要2万到3万块的费用

你对自己的游戏很有信心，相信很快就会达到上亿的用户体量，但又觉得为这一个小功能每年花这么多钱，实在心疼，于是你想优化这个功能，作为一名有志向的程序员，我们是不愿意牺牲性能的，该怎么办？

有没有占用空间少，并且能在O(1)的时间纬度准确判断用户是否存在的数据结构呢？

答案是没有。。。

如果有的话，我们就不用学其他的数据结构了，直接用它就好了

但是我们有一个折衷的方案，这个方案可以省钱，但可能会稍微影响一些性能，注意是“可能”

这个方案就是使用布隆过滤器

什么是布隆过滤器

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的，它实际上是一个很长的二进制向量和一系列随机映射函数

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难

其特点为：

• 与普通的 hash 函数不同，布隆过滤器可以使用固定长度的集合表示任意数量的元素
• 布隆过滤器在判断元素是否在集合中时，若判断结果为“真”，那么元素不一定存在于我们的真实数据中，这个错误识别的概率可以使用误识别率函数（参考后文）计算
• 向布隆过滤器中添加元素永远不会失败，但随着添加元素数量的增加，误识别率也会线性上升
• 布隆过滤器在判断元素是否在集合中时，若判断结果为“假”，那么元素一定不存在于我们的真实数据中
• 不能从布隆过滤器中删除元素，只能重建过滤器

布隆过滤器的工作流程

如下图，是一个拥有 10 个二进制位的空布隆过滤器，每一位都设置为 0

就像使用集合一样，我们需要先向布隆过滤器中添加元素。

若想向布隆过滤器中添加元素，需要使用一些 hash 函数，假设布隆过滤器实现使用了三个 hash 函数 h1，h2 和 h3。

每一个 hash 函数都会针对添加元素产生一个布隆过滤器的索引，即上图 1 到 10 索引中的一个。当依次使用 h1(元素) ，h2(元素)和h3(元素)产生索引之后，我们就将布隆过滤器中的索引值设置为 1

例如我们想使用 hash 函数把 “geeks“这个元素添加到布隆过滤器中

1
2
3
h1("geeks") % 10 = 1
h2("geeks") % 10 = 3
h3("geeks") % 10 = 7

调用这些函数生成索引之后，布隆过滤器会更新对应坐标(注意：这些 hash 函数的返回值只是为了说明布隆过滤器的实现而随机选的)

然后，我们把 ”nerd“ 元素也添加到布隆过滤器中

1
2
3
h1("nerd") % 10 = 3
h2("nerd") % 10 = 5
h3("nerd") % 10 = 4

那么我们的布隆过滤器也会随着更新

我们的布隆过滤器中有两个元素，分别是“geeks”和“nerd”，也可以理解为这两个用户已经注册了游戏。

现在，有第三个用户注册并也起名为“geeks”，我们需要判断“geeks”是否被注册，如下步骤

我们还是使用上边的三个hash函数处理元素 根据返回的索引去布隆过滤器中查询

• 若三个索引中有一个为 0，那么我们就可以判断 “geeks”并没有被注册
• 若三个索引的值都是 1 （我们显然已经知道这是成立的），但根据布隆过滤器的规则我们只能知道 “geeks” 可能被注册了

布隆过滤器的误算

为什么上例的 “geeks” 元素在布隆过滤器中查询后，我们只能判断它可能存在呢？

下边我们用同样的方法，把“cat”也存放到布隆过滤器中

1
2
3
h1("cat") % 10 = 1
h2("cat") % 10 = 3
h3("cat") % 10 = 7

我们需要“cat”用户hash函数计算的将索引更新为 1，以说明“cat”被添加到布隆过滤器中

但这个索引已经在我们添加”geeks“和”nerd“的时候被设置为 1 了

所以如果在我们添加“cat”元素之前，使用 “cat”来查询其是否被注册，就会得到错误的结果。

好消息是我们可以通过增加布隆过滤器的长度来控制误算概率

误算率计算

假设我们的布隆过滤器长度为 m ，使用的hash 函数数量为 k， 我们希望向布隆过滤器中添加 n个元素，则误算率 P如下

布隆过滤器长度计算

如果我们知道我们将要向布隆过滤器中添加 n 个元素，我们希望过滤器的误算率为 p，那么布隆过滤器的长度 m 如下

理想的 hash 函数数量

hash 函数数量 k 必须是正数，如果我们想向布隆过滤器中添加 n 个元素，布隆过滤器的长度设置为 m ，那么 hash 函数的数量 k 如下

布隆过滤器占用更小的空间

一般的数据结构如字典，集合等都会存储元素本身，并且需要从数据结构层处理hash碰撞问题。

布隆过滤器并不会存储元素本身，也不需要解决 hash 碰撞问题，所以布隆过滤器占用空间下，对于空间的利用率也很高

hash 函数的选择

布隆过滤器的hash函数必须是独立并且均匀分布的，这些函数越快越好

一些简洁快速无加密的hash函数可以选择使用Murmur或者Jenkins

生成 hash 函数是编写布隆过滤器的关键步骤，如果使用加密的hash 函数就会降低布隆过滤器的性能，而使用非加密的hash函数则安全性较差

布隆过滤器的应用

• Chrome 使用布隆过滤器判断是否为恶意 URL
• Apache HBase ，Apache Cassandra 和 Postgresql 使用布隆过滤器检查不存在的行
• 还有一些推荐系统使用布隆过滤器判断某些文章是否被用户阅读过
• 布隆过滤器可以作为缓存前面一层减少缓存压力，并且可以解决一些缓存穿透问题