火了50年的技术—布隆过滤器原文：火了50年的技术—布隆过滤器前言

原文：
文章插图
火了50年的技术—布隆过滤器前言我们之前讲了Redis的缓存雪崩、穿透、击穿。在文章里我们说了解决缓存穿透的办法之一，就是布隆过滤器，但是上次并没有讲如何使用布隆过滤器。
作为暖男的老哥，给你们补上，请叫我IT老暖男。
文章插图
什么是布隆过滤器布隆过滤器（Bloom Filter），是1970年，由一个叫布隆的小伙子提出的，距今已经五十年了，和老哥一样老。
它实际上是一个很长的二进制向量和一系列随机映射函数，二进制大家应该都清楚，存储的数据不是0就是1 ，默认是0 。
主要用于判断一个元素是否在一个集合中， 0代表不存在某个数据， 1代表存在某个数据。
懂了吗？作为暖男的老哥在给你们画张图来帮助理解：
文章插图
布隆过滤器用途

解决Redis缓存穿透（今天重点讲解）
在爬虫时，对爬虫网址进行过滤，已经存在布隆中的网址，不再爬取。
垃圾邮件过滤，对每一个发送邮件的地址进行判断是否在布隆的黑名单中，如果在就判断为垃圾邮件。

以上只是简单的用途举例，大家可以举一反三，灵活运用在工作中。
布隆过滤器原理存入过程布隆过滤器上面说了，就是一个二进制数据的集合。当一个数据加入这个集合时，经历如下洗礼（这里有缺点，下面会讲）：

通过K个哈希函数计算该数据，返回K个计算出的hash值
这些K个hash值映射到对应的K个二进制的数组下标
将K个下标对应的二进制数据改成1 。

例如，第一个哈希函数返回x ，第二个第三个哈希函数返回y与z ，那么： X、Y、Z对应的二进制改成1 。
如图所示：

文章插图
查询过程布隆过滤器主要作用就是查询一个数据，在不在这个二进制的集合中，查询过程如下：

通过K个哈希函数计算该数据，对应计算出的K个hash值
通过hash值找到对应的二进制的数组下标
判断：如果存在一处位置的二进制数据是0 ，那么该数据不存在。如果都是1 ，该数据存在集合中。（这里有缺点，下面会讲）

删除过程一般不能删除布隆过滤器里的数据，这是一个缺点之一，我们下面会分析。
布隆过滤器的优缺点优点

由于存储的是二进制数据，所以占用的空间很小
它的插入和查询速度是非常快的，时间复杂度是O（K），可以联想一下HashMap的过程
保密性很好，因为本身不存储任何原始数据，只有二进制数据

缺点这就要回到我们上面所说的那些缺点了。
添加数据是通过计算数据的hash值，那么很有可能存在这种情况：两个不同的数据计算得到相同的hash值。

文章插图
例如图中的“你好”和“hello” ，假如最终算出hash值相同，那么他们会将同一个下标的二进制数据改为1 。
这个时候，你就不知道下标为2的二进制，到底是代表“你好”还是“hello” 。
由此得出如下缺点：
一、存在误判假如上面的图没有存"hello" ，只存了"你好" ，那么用"hello"来查询的时候，会判断"hello"存在几何中。
因为“你好”和“hello”的hash值是相同的，通过相同的hash值，找到的二进制数据也是一样的，都是1 。