布隆过滤器

---

去重的时候1亿个地址大约需要1.6GB的内存（8字节的信息指纹+8字节地址）。

布隆过滤器只要1/4或者1/8的空间即可。一般是对应哈希数组长度 * 1bit / C（哈希函数个数，哈希数组长度）* 单位数据对应的bit大小，因为m!/(m-k)!k!大于m，所以比一对一的映射要更节省空间。

存储1亿个地址，先建立16亿个二进制比特，即2亿B，将这16亿个二进制位清零。对每个地址X，用8个不同的随机数生成器产生8个信息指纹（f1...f8），再用一个随机数生成器将8个指纹映射到1-16亿中的8个自然数。然后将这8个自然数对应的二进制位置全部置为1。

布隆过滤器不会遗漏可疑地址，但是他可能会误判一些网址。补救方法就是再建一个白名单，以避免误判。

然后如果要删除的话会比较麻烦，一般要使用计数，加重负担。

image.png

---

计算误差：

我们假设所有哈希函数散列足够均匀，散列后落到Bitmap每个位置的概率均等。Bitmap的大小为m、原始数集大小为n、哈希函数个数为k。

• 我们先假设hash结果是均匀分布的，那么对同一个地址k次hash后
  某一位置为0的概率应为(1-1/m)^k

• 如果把n个数都映射过去，那么该点为1的概率为1-(1-1/m)^kn（hash数组的元素一但映射为1，哪怕后来映射0还是1）

• 则添加第n个数的时候k个对应位置都为1的概率为(1-(1-1/m)^kn)^k

• 误判率=k位全1的概率-正确的概率≈(1−e^(−nk/m))^k

• 以k为自变量求导可得当k=ln2*m/n时，误差率最小≈(1/2)^k（这个不是很好证）

• 综上可知，随着插入元素的增加，布隆过滤器的误判率会越来越高

---

举个具体点的例子：

当硬盘空间为5TB，数据长度为64bit，由于硬盘空间是限制死的，集合元素个数n的大小反而与单个数据的比特数成反比。

n=5TB/64bit≈2^34

若以m=16n计算(hash表的空间要比元素个数大一点避免碰撞)，Bitmap集合的大小为待检测数据空间大小/单个数据空间大小*m/n=2^38bit=2^35Byte=32GB，此时的误差率ε≈0.0005，可以用于过滤一部分的非法请求。

工程方面有谷歌现成的工具包：

但是实际使用的却并不是n个哈希函数。实际进行映射时，而是分别使用了一个64bit哈希函数的高、低32bit进行循环移位。

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;