概述

布隆过滤器是一个应用非常广泛的概率型数据结构，一般用于判断一个元素是否存在一个集合中，比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在缓存系统中，判断一个元素是否在缓存中；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。关于这个，只需要根据元素的数量和大小简单的计算一下就知道了。虽然可以适用分布式K-V系统（如Redis）来承载，但是成本仍然高昂。布隆过滤器只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题，以一定的误判率为代价。所需要的内存大小可以通过公式精确的计算出来：Bloom Filter Calculator。

布隆过滤器其实是一个比较简单的数据结构，不难实现，接口简单，代码也不长。已经有很多开源的实现，像谷歌的guava基础库就有实现。布隆过滤器有许多的变种，像 Counting Bloom Filter, 可以支持删除元素。

布隆过滤器可以处理的类似问题：

垃圾邮件过滤
文字处理中的错误单词检测
网络爬虫重复URL检测
会员抽奖
判断一个元素在亿级数据中是否存在
缓存穿透

优点

它的优点是空间效率和查询时间都远远超过一般的算法，布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。另外, 散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

缺点

随着数据的增加，误判率随之增加；；只能判断数据是否一定不存在，而无法判断数据是否一定存在。

如果数据A，经过hash1（A）、hash2（A）、hash3（A），得到其hash值1、3、5，然后我们在其二进制向量位置1、3、5设置1，然后数据B，经过hash1（B）、hash2（B）、hash3（B）,其实hash值也是1、3、5，我们在做业务处理的时候判断B是否存在的时候发现其二进制向量位置返回1，认为其已经存在，就跳过相关业务处理，实际上根本不存在，这就是由于hash碰撞引起的问题。也就存在了误差率。