布隆过滤器
来自智得网
简介
布隆过滤器是Bloom提出了过滤机制，主要用于判断数据是否存在，如果数据存在返回true，否则返回false，但是当返回true的时候布隆过滤器不保证数据一定准确，也就是可能一定的假存在的可能性，但返回false的时候数据一定是不存在的。
原理
布隆过滤器一般通过Bitmap和一组Hash函数构成，当值被写入持久化存储的同时写入布隆过滤器，写入逻辑如下：
将Hash函数组中的每个Hash函数对Key进行Hash操作。
Hash操作之后进行位置运算，例如对bitmap数组的长度取模。
将Hash结果对应的位置写入1
在查询的时候，也会运用这一组Hash函数分别对请求值进行Hash和位置运算，最后判断这一组的结果值是否全为1，如果不是全1，则数据一定不存在，反之如果为0，则判定数据存在，但是因为Hash冲突的原因，所以全为1也有一定的误差存在，尤其是bitmap的空间不足的时候。
和其他表示集合类的数据结构，例如平衡二叉搜索树、Trie 树、哈希表，数组或者链表，布隆过滤器的空间复杂度最低，因为布隆过滤器不存储数据本身，而仅仅存储数据的一组哈希值，而且位数组的存储结构也更加紧凑，避免了指针开销。
布隆过滤器的仅仅需要计算一组Hash值，时间复杂度也接近O（1）。