布隆过滤器

在其他语言中阅读： 俄语(README.ru-RU.md| 葡萄牙语(README.pt-BR.md| 乌克兰语(README.uk-UA.md)

布隆过滤器是一种空间高效的概率数据结构，用于测试一个元素是否存在于集合中。它的设计目标是快速且使用最少的内存，但代价是潜在的误报。误报匹配是可能的，但误报不可能发生——换句话说，查询要么返回“可能存在于集合中”，要么返回“肯定不在集合中”。

布隆提出的这项技术适用于源数据量会因为应用“传统”无错误哈希技术而需要大量内存的情况。

算法描述

一个空的布隆过滤器是一个由m位组成的比特数组，所有位都设置为0。还必须定义k个不同的哈希函数，每个哈希函数都将集合中的一个元素映射到m数组位置之一，生成均匀随机分布。通常，k是一个常数，远小于m，m与要添加的元素数量成正比；k的确切选择和m的比例常数由过滤器的预期误报率决定。

这里有一个布隆过滤器的例子，代表集合{x, y, z}。彩色箭头显示了每个集合元素在比特数组中的位置。元素w不在集合{x, y, z}中，因为它哈希到一个包含0的比特数组位置。对于这个图，m = 18和k = 3。

布隆过滤器

操作

布隆过滤器可以执行两个主要操作：插入（insertion）和搜索（search）。搜索可能会导致误报。无法删除。

换句话说，过滤器可以接受项目。当我们检查一个项目是否之前已经插入时，它可以告诉我们“没有”或者“可能”。

插入和搜索都是O(1)操作。

创建过滤器

布隆过滤器是通过分配一定大小来创建的。在我们的例子中，我们使用100作为默认长度。所有位置都被初始化为false。

插入

在插入过程中，使用k个哈希函数（在我们的例子中是3个哈希函数）来创建输入的哈希值。这些哈希函数输出索引。在收到的每一个索引上，我们只需将布隆过滤器中的值更改为true。

搜索

在搜索过程中，调用相同的哈希函数并用于哈希输入。然后我们检查收到的索引中是否有true的值。如果有true的值，我们就知道布隆过滤器可能之前插入过该值。

然而，我们不能确定这一点，因为其他之前插入的值可能会翻转这些值为true。由于当前正在搜索的项目，值不一定为true。除非只插入了一个项目，否则绝对确定性是不可能的。

在检查我们的哈希函数返回的索引时，如果其中任何一个值为false，我们就可以肯定地知道该项目之前没有被插入。

误报

误报的概率由三个因素决定：布隆过滤器的大小、我们使用的哈希函数的数量以及已插入过滤器的项目数量。

计算误报概率的公式是：

( 1 - e ^-kn/m ) ^k

k = 哈希函数的数量

m = 过滤器大小

n = 已插入项目的数量

这些变量k、m和n应该根据对误报的接受程度来选择。如果选择了这些值，并且得到的概率太高，那么应该调整这些值并重新计算概率。

应用

布隆过滤器可以用于博客网站。如果目标是只向读者展示他们从未见过的文章，那么布隆过滤器是完美的。它可以基于文章存储哈希值。用户在阅读了一些文章后，可以将它们插入到过滤器中。下次用户访问网站时，这些文章可以从结果中过滤掉。

一些文章不可避免地会被错误地过滤掉，但这种成本是可以接受的。只要用户每次访问网站时都能看到其他全新的文章，即使他们错过了几篇文章也是可以接受的。

布隆过滤器

算法描述

操作

创建过滤器

插入

搜索

误报

应用

参考资料