布隆过滤器（Bloom Filter）

如何判断一个数是否在某个集合中，我们最简单的方式是遍历集合判断是否存在这样一个元素，更高级一点的方式是使用哈希表，可以以 O(1) 的时间复杂度判断一个元素是否在集合中，但是当数据量达到亿级别的时候，再采用这种方式就会出现问题，那IPV4来说，现有ip数量为 256^4个（假设每一个不同的都算），以 map 存储的话，假如key是字符串，占用15字节，val是布尔型1个字节，一个k-v 占16个字节，至少也得占用2^36个字节，折算下来就是 2^36/1024/1024/1024 = 2^6 = 64G，这么大内存肯定是放不下的，因此需要一种特殊的算法来进行处理，接下来所要介绍的算法就是解决大数据下，元素是否存在于集合中这么一个问题的。

布隆过滤器，实际上是一个很长的二进制向量和一系列随机映射函数，可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

布隆过滤器 = bitmap + hash， 如上图（来源wikipedia）所示。

hash 我们都知道，就是通过一些逻辑运算，将元素数据转换成一个特殊的数值，且尽量保证不同的数据得到哈希值不同，但是当数据量很大的时候，难免会出现不同的数得到相同的哈希值，这就是所谓的哈希碰撞。

那bitmap又是什么呢？ bitmap就是以位信息存储数据，如上图二进制串，假设串中存储的数都是非负整数，则从0开始，二进制中右数第二位是1，则可以表示1存在于bitmap中，哪一位为1，则表示哪一个数存在于map中，一个数，只占用1 bit，可以说空间效率很高；同时如要判断1是否在bitmap中，通过二进制串与 1 进行位与操作，即可判断，时间效率也很高。

而布隆过滤器为了减少哈希冲突，通过设置一系列的hash函数，将原始数据分散开，能有效减少冲突，不过依旧无法避免特殊用例导致不同两数据，得到的结果一致的情况，因此，布隆过滤器只能说某数大概率存在于集合中，无法一定确定某个数存在于集合中。但是可以确定的是，如果某个数的多次哈希结果都不在bitmap中，那么其一定不在给定的集合中。

所以综上所述

• 当一个数的多次哈希结果不全在bitmap中时，布隆过滤器一定可以判断出其不在集合中，

• 当一个数的多次哈希结果全在bitmap中时，布隆过滤器可以说其大概率是在这个集合中的，有一定的误差率。