概率数据结构：布隆过滤器

喜欢就点关注吧!

哈希表与哈希函数

在简单数组或列表中插入新数据时，插入数据的索引不是从要插入的值确定的。这意味着密钥（索引）和值（数据）之间没有直接关系。因此，如果需要在数组中搜索值，则必须在所有索引中进行搜索。在哈希表中，您可以通过散列值来确定键或索引。这意味着密钥是根据值确定的，每次需要检查列表中是否存在该值时，您只需对值进行散列并搜索该密钥，查找速度非常快，时间复杂度为O(1）。

现在，假如你有一个庞大的弱密码列表，它存储在一些远程服务器上。由于数据量比较大，无法在RAM中一次加载它们。每次用户输入密码时，都要检查它是否是弱密码。如果是，你想给他/她一个警告，如果将数据存储在哈希表中，每次根据给定的密码进行匹配，匹配可能很快，但是在磁盘上或通过远程服务器上的网络查找的成本非常大，如何在尽量小的成本里得到匹配结果，就需要考虑使用布隆过滤器。

布隆过滤器

布隆过滤器是一种概率数据结构，由长度为m的位向量或位列表（仅包含0或1位值的列表）组成。最初所有值都设置为零，如下所示。

如果要将数据添加到bloom过滤器，需要将其提供给k个不同的哈希函数，并在位向量中将这些位设置为1。在哈希表中使用单个哈希函数，因此只有一个索引作为输出。但在bloom过滤器中，我们将使用多个哈希函数，也将得到多个索引。

如上图，我们存入geeks得到位向量中的1、4、7的位置为1，而其他位置为0。现在我们再存入nerd得到位向量中的3、4、5的位置为1，其中4的位置被重复置1。

现在如果我们想要查找元素是否在数据集中，假如我们想要查找“nerd”，将其通过三个哈希函数映射，根据刚才存储的情况会返回3、4、5位置上值为1。如果我们想要查找“cat”呢，假如返回1、3、7位置为1，虽然刚才我们没有存储该元素，但仍返回位置都为1，这就说明发生了误报。布隆过滤器查找原理图如下：

因此总结得到：

• 如果我们搜索一个值并看到该值的散列值为零，那么该值肯定不在列表中。
• 如果所有散列索引都是1，则搜索的值可能在列表中。

布隆过滤器操作

基本布隆过滤器支持两种操作：测试和添加。

• 测试用于检查给定元素是否在集合中
• 添加是向集合添加元素

Bloom过滤器大小和散列函数的数量

在实验中如果布隆过滤器的太小，则很快就会将所有位字段全变为1。那么布隆过滤器将有很高的“误报率”。因此布隆过滤器的大小是一个非常重要。

较大的过滤器将具有较少的误报但速度越慢，而较小的过滤器将具有较多的误报。另一个重要参数是我们将使用多少哈希函数。我们使用的哈希函数越多，布隆过滤器就越慢，填充的速度就越快。但如果哈希函数太少，就可能会有更多误报。其关系图如下：

还可以根据滤波器的大小(m)、散列函数的数量(k)和插入的元素数n来计算误报率p，公式如下：

因此得到m、k与误报率的关系式为：

应用

Bloom过滤器主要是用于检测元素是否在集合中的。使用bloom过滤器的主要目的是减少磁盘（或网络）查找元素的代价。我们可以看到布隆过滤器可以在O(k)的时间内搜索元素，其中k是哈希函数的数量，查找速度非常快。

如果元素不在bloom过滤器中，那么我们肯定不需要继续查找。如果它在布隆过滤器中，我们也可以预期得到查找的准确率。下面是布隆过滤器的一些应用例子：

• 可以使用布隆过滤器来警告用户设置密码过弱。
• 可以使用布隆过滤器来防止用户访问恶意网站。
• 可以先使用布隆过滤器进行预查找，而不是查询SQL数据库以检查是否存在具有特定电子邮件的用户。如果电子邮件不存在，则不需要继续查找；如果确实存在，则可能必须对数据库进行额外查询。同时还可以搜索是否已使用用户名。
• 可以使用布隆过滤器根据网站访问者的IP地址来检查您网站的用户是返回用户还是新用户
• 可以使用布隆过滤器来跟踪字典单词，从而制作拼写检查程序。

参考

https://medium.com/better-programming/probabilistic-data-structures-bloom-filter-5374112a7832