理解布隆过滤器、使用场景

1.布隆过滤器基础

简单来说，布隆过滤器可以看作是一个【位数组】。存的都是0或者1。
位数组中每个元素都只占用1bit；
它是一种概率性数据结构，可以实现高效插入和查询。
通常都是用来检索某个元素是否在给定的大集合中***
能告诉你：XXX一定不存在或者可能存在，给你的结果不是确切的，更加的高效、占用空间小*。

2.布隆过滤器原理？(如何使用它去判断元素是否存在)

思考：通常情况下，我们判断某个元素是否存在，会使用HashMap，因为Key是唯一的，我们就可以去查询一个元素的Key，而去找到这个元素。时间复杂度是O（1），效率很高。但是当存储的数据量很大时，也会占用很大内存。
布隆过滤器可以实现更加快速的查询。
如图所示，当字符串存储要加入到布隆过滤器中时，该字符串首先由多个哈希函数生成不同的哈希值，然后在对应的位数组的下表的元素设置为 1（当位数组初始化时 ，所有位置均为0）。

加入元素：
如，往布隆过滤器中加入“hello”字符串时，会先使用布隆过滤器中的n个哈希函数对 字符串进行计算，得到n个不同的哈希值，然后将对应的位数组置1。假设得到三个不同的哈希值 1，3，5.

此时，再加入“world”字符串，假设得到 2，3，4
由于3位置本身就是1，此时又得到了3，就覆盖，完了还是1.

查找元素
当查找元素“HI”时，计算得到的哈希值为0，3，5
此时发现0位置的值是0，说明"HI"一定不存在！

当查找元素“GOOD”是，计算得到的哈希值为1，2，5
所在位置都是1，但是它实际上并不存在！只能说明“GOOD”可能存在
同理，就是查找的是前面存过的”hello“,哈希值是1，3，5 也只能告知”hello“可能存在，而不是一定存在。

总结

布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。

3.布隆过滤器使用场景

3.1 学习Redis时，在某种情况下，可能会出现缓存雪崩和缓存穿透。
缓存穿透：大量请求访问时，Redis没有命中数据，导致请求绕过了Redis缓存，直接去访问数据库了。数据库难以承受大量的请求。
此时便可以使用布隆过滤器来解决。
请求到来时，先用布隆过滤器判断数据是否有效，布隆过滤器可以判断元素一定不存在和可能存在，对于一定不存在的数据，则可以直接丢弃请求。对可能存在的请求，再去访问Redis获取数据，Redis没有时，再去访问数据库。
3.2 邮箱的垃圾邮件过滤、黑名单等。
3.3 去重，：比如爬给定网址的时候对已经爬取过的 URL 去重。