布隆过滤器
<h2>1 布隆过滤器</h2>
<p>布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。</p>
<h2>2 原理</h2>
<p>布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。</p>
<p>原理图如下：
<img src="https://s2.ax1x.com/2020/02/26/3a8ung.jpg" alt="布隆过滤器原理图" />
Bloom Filter跟单哈希函数不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。而且采用的是位数组，它占用的空间也很小。1GB=1bit<em>8</em>1024<em>1024</em>1024 约等于80亿。</p>
<h2>缺点</h2>
<p>bloom filter之所以能做到在时间和空间上的效率比较高，是因为牺牲了判断的准确率、删除的便利性</p>
<ul>
<li>
<p>存在误判，可能要查到的元素并没有在容器中，但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。</p>
</li>
<li>删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。可以采用Counting Bloom Filter</li>
</ul>
<h2>优点</h2>
<ul>
<li>查找迅速</li>
<li>占用空间小</li>
</ul>
<h2>实现方式</h2>
<ol>
<li>Guava中已提供了具体的实现</li>
<li>Redis安装bloomfilter插件，即可像操作其它数据结构一样操作</li>
</ol>
<ul>
<li>在使用bloom filter时，绕不过的两点是预估数据量n以及期望的误判率fpp，</li>
<li>在实现bloom filter时，绕不过的两点就是hash函数的选取以及bit数组的大小。</li>
</ul>
<p>对于一个确定的场景，我们预估要存的数据量为n，期望的误判率为fpp，然后需要计算我们需要的Bit数组的大小m，以及hash函数的个数k，并选择hash函数</p>
<h2>使用场景</h2>
<ul>
<li>Redis过滤掉不存在的key，避免缓存穿透</li>
<li>黑白名单，判断某一个值是否在黑白名单中</li>
<li>爬虫过滤已抓到的url就不再抓</li>
</ul>