一、简述

有时候我们需要 判断一个元素是否在一个集合中 。最直接的方法就是将集合中的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表来存储的。它的好处是快速准确，缺点是耗费存储空间。其根本原因是哈希表方法需要把实实在在的具有特定长度（每个 Email 地址对应成一个 8 字节的信息指纹）的元素的信息指纹存储在内存或硬盘中的哈希表中。比如每存储一亿个 Email 地址，需要 0.8G 大小的数字指纹存储空间，考虑到哈希表的存储空间利用率一般只有一半，所以需要 1.6G 的存储空间。如果存储几十亿上百亿的 Email 地址，那就需要百亿字节的内存存储空间。
布隆过滤器 主要就是用于解决：快速判断一个元素是否在一个集合中，优势是只需要 占用很小的内存空间以及有着高效的查询效率 ，缺点是 不能从布隆过滤器中删除元素和有一定的误报率

二、原理

利用一个 很长的二进制向量 和一系列的随机映射函数 来实现。

1. 首先需要初始化一个二进制的数组，长度设为 L ，同时初始值全为 0。
2. 当写入一个 A1=1000 的数据时，需要进行 H 次 hash 函数的运算；与 HashMap 有点类似，通过算出 hashcode 与 L 取模后定位到 0、2 处，将该处的值设为 1。
3. A2=2000 也是同理计算后将 4、7 位置设为 1。
4. 当有一个 B1=1000 需要判断是否存在时，也是做两次 hash 运算，定位到 0、2 处，此时他们的值都为 1，所以认为 B1=1000 存在于集合中。
5. 当有一个 B2=3000 时，也是同理。第一次 Hash 定位到 index=4 时，数组中的值为 1，所以再进行第二次 hash 运算，结果定位到 index=5 的值为 0，所以认为 B2=3000 不存在于集合中。

三、特点

1. 只要返回数据不存在，则肯定不存在。
2. 返回数据存在，只能是大概率存在。
3. 不能清除其中的数据
4. 误报率和布隆过滤器的位数是负相关的
5. 映射函数函数多浪费算力，一般取 0.7* 布隆位数 / 元素个数

四、设计方法

1. 决定元素个数 n 和期望误差 p
2. 布隆位数为 -n*ln(p) / ln(2)^2
3. 哈希函数个数为 0.7*m/n
4. 为了保证低于期望误差，可以适当增加布隆位数