通过实例解析布隆过滤器工作原理及实例通过实例解析布隆过滤器工作原理及实例
布隆过滤器布隆过滤器
布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用
来告诉你 “一定不存在或者可能存在”。
相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切
的。
布隆过滤器的工作原理布隆过滤器的工作原理
假设一个长度为m的bit类型的数组，即数组中每个位置只占一个bit，每个bit只有两种状态：0，1，所有bit的初始状态都为0。
再假设一共有k个哈希函数，这些函数的输出域大于或者等于m，并且这些哈希函数，彼此之间相互独立，每个哈希函数计算
出来的结果是独立的，可能相同也可能不相同，对每一个计算出来的结果都对m取余（%m），然后再将数组下标位置置为
1。
我们这里假设m为13,k为3的布隆过滤器，来看看布隆过滤器的工作原理：
当我们要映射一个值到布隆过滤器时，首先计算三个哈希函数的值，然后对13取余，映射到对应位中，图中映射到
2，6，10，这样我们就完成了一个值的映射。
那么怎么判断一个值是否存在，当一个值输入时，通过三个哈希函数，然后取余，我们就可以得到对应的三个位置，我们只需
要判断这三个位置是否都为1，如果都为1，则该值存储，反之不存在。
但是有一个特殊情况，前面说了不同的哈希函数可能计算可能相同也可能不相同，而且不同的哈希函数对不同的值计算出来的
值可能一样，这就造成一个结果，一个值通过哈希和取余得到的位置，早就被其它值给置1了，当我们存储的值过多，而这个
bit数组过小，都会造成这种情况更多的发生，一个值明明不存在，而它的所有位置早就被其它不同值置1，造成了误判，这里
就对布隆过滤器提出了一个指标：失误率p。
在同样数据规模下，不同大小的bit数组及不同数量k的哈希函数对误判率的结果：
资源评论
