布隆过滤器

参考 https://www.cnblogs.com/yy1234/p/10484815.html

什么是布隆过滤器

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

布隆过滤器使用场景

https://www.cnblogs.com/ysocean/p/12594982.html
比如有如下几个需求：

    ① 原本有10亿个号码，现在又来了10万个号码，要快速准确判断这10万个号码是否在10亿个号码库中？
　　 解决办法一：将10亿个号码存入数据库中，进行数据库查询，准确性有了，但是速度会比较慢。
　　 解决办法二：将10亿号码放入内存中，比如Redis缓存中，这里我们算一下占用内存大小：10亿*8字节=8GB，通过内存查询，准确性和速度都有了，但是大约8gb的内存空间，挺浪费内存空间的。
    ② 接触过爬虫的，应该有这么一个需求，需要爬虫的网站千千万万，对于一个新的网站url，我们如何判断这个url我们是否已经爬过了？解决办法还是上面的两种，很显然，都不太好。
    ③ 同理还有垃圾邮箱的过滤。那么对于类似这种，大数据量集合，如何准确快速的判断某个数据是否在大数据量集合中，并且不占用内存，布隆过滤器应运而生了。
    ④ 新闻推送过滤
    ⑤ 解决redis穿透，或者缓存击穿问题

假设我有 1亿 条用户数据，现在查询用户要去数据库中查，效率低而且数据库压力大，所以我们会把请
求首先在 Redis 中处理（活跃用户存在 Redis 中），Redis 中没有的用户，再去数据库中查询。
现在可能会存在一种恶意请求，这个请求携带上了很多不存在的用户，这个时候 Redis 无法拦截下来请
求，所以请求会直接跑到数据库里去。这个时候，这些恶意请求会击穿我们的缓存，甚至数据库，进而
引起“雪崩效应”。
为了解决这个问题，我们就可以使用布隆过滤器。将 1亿条用户数据存在 Redis 中不现实，但是可以存
在布隆过滤器中，请求来了，首先去判断数据是否存在，如果存在，再去数据库中查询，否则就不去数据库中查询。

原理

查找元素是否存在的数据结构，O(1)的还有hashtable,但是占内存太大。因为负载因子的存在，空间用不满。

布隆过滤器
是一个bit数组，每个元素不是0就是1，再通过多个哈希函数计算出多个哈希值，将哈希值对应的下标的值置为1，这样判断一个数是否存在只需要判断下标为该数的哈希值对应的位数组的值是否为1，如果有一个不为1则说明不存在。但是如果都为1并不能说明该数已存在，因为随着插入的增多，1也会越来越多，可能会出现某个值的哈希值对应的值都是1，所以并不能确定一定存在。

如何选择哈希函数个数和位数组大小

位数组过小那么很快就都是1，起不到过滤作用。哈希函数过多，置为1的速度越快，效率越低；哈希函数过少，误报率越高。
哈希函数个数和位数组大小的选择参考 https://zhuanlan.zhihu.com/p/43263751

https://www.jianshu.com/p/c2defe549b40
借助redis bitmap 实现布隆过滤器