BloomFilter（布隆过滤器）是一种可以高效地判断元素是否在某个集合中的算法。

应用场景

BloomFilter有非常多的应用场景，如检查单词是否拼写正确、网络爬虫的URL去重、黑名单检验、昵称不能重复的检测等等。

原理分析

布隆过滤器本质是一个位数组。其整体思路：

1、先初始化一个m位长度的位向量{1..m}，每一位均初始化为0；
2、使用k个相互独立的Hash函数，每个Hash函数将元素映射到{1..m}的范围内，并将对应的位置为1；
3、当查找某元素是否存在时，查找该元素所对应的k位是否全部为1，即可说明该元素是否存在。

使用优缺点

优点

1. 空间和时间效率高

  1. 对于少量数据来说，使用HashSet判断是很好的选择。但是对于海量数据来说，BloomFilter相比于其他数据结构在空间效率和时间效率方面都有着明显的优势。

缺点

1. 存在误报

BloomFilter 具有一定的误判率，有可能会将本来不存在的元素判定为存在。因此，对于那些需要“零错误”的应用场景，BloomFilter将不太适用。

2. 无法删除

BloomFilter 由于并不存储元素，而是用位的0、1来表示元素是否存在，并且很有可能一个位被多个元素同时使用，所以无法通过将某元素对应的位置为0来删除元素。
幸运的是，目前学术界和工业界都有很多方法扩展已解决以上问题。如可以使用Counting Bloom Filter (CBF)，CBF将基本BloomFilter的每一个Bit改为一个计数器，这样就可以实现删除字符串的功能了。另外还有Cuckoo（布谷鸟哈希） 也可以解决误报和无法删除的问题。

实际操作

可以通过 docker 直接在 redis 中体验布隆过滤器：

docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
docker exec -it bloomfilter redis-cli

redis 布隆过滤器主要就两个命令：

bf.add 添加元素到布隆过滤器中：bf.add urls https://ninglg.com
bf.exists 判断某个元素是否在过滤器中：bf.exists urls https://ninglg.com

上面说过布隆过滤器存在误判的情况，在 redis 中有两个值决定布隆过滤器的准确率：

error_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
initial_size：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值：

bf.reserve urls 0.01 100

复制代码三个参数的含义：
第一个值是过滤器的名字。
第二个值为 error_rate 的值。
第三个值为 initial_size 的值。

使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：(error) ERR item exists。