十一、布隆过滤器

访问 www.coding-time.cn 阅读原文动画效果，体验更佳。

布隆过滤器是一种空间有效的概率数据结构，设计用来测试一个元素是否在一个集合中。它的设计目标是极快的速度和最小的内存使用，但可能会产生误报。可能会有误报，但不会有漏报 —— 换句话说，查询返回的是"可能在集合中"或"绝对不在集合中"。

布隆提出这种技术是为了应对那些使用"常规"无误差哈希技术处理会需要不切实际大量内存的源数据的应用。

1. 算法描述

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

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

2. 操作

布隆过滤器可以执行两个主要操作：插入 和 搜索。搜索可能会导致误报。删除操作是不可能的。

换句话说，过滤器可以接收项目。当我们去检查一个项目是否之前已经插入，它可以告诉我们"否"或者"可能"。

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

3. 构造过滤器

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

1）插入

在插入过程中，会使用多个哈希函数，我们的例子中使用了3个哈希函数，对输入进行哈希。这些哈希函数输出索引。在每个接收到的索引处，我们简单地将布隆过滤器中的值更改为true。

2）搜索

在搜索过程中，调用相同的哈希函数并用于哈希输入。然后我们检查在布隆过滤器中接收到的索引是否_全部_为true。如果它们_全部_为true，我们知道布隆过滤器可能已经插入过这个值。

然而，这并不确定，因为有可能其他之前插入的值将这些位置的值改变为true。这些值并不一定是由当前搜索的项目设为true的。除非只有一个项目被插入，否则无法绝对确定。

在检查由我们的哈希函数返回的布隆过滤器索引时，如果其中任何一个值为false，我们可以确定地知道该项目之前未被插入。

带你读《图解算法小抄》十一、布隆过滤器（2）https://developer.aliyun.com/article/1348193?groupCode=tech_library