- A+
看到一个集合查找的面试题，想起这个算法。
前言
一个面试题
现在有一个非常庞大的数据，假设全是 int 类型。现在我给你一个数，你需要告诉我它是否存在其中(尽量高效)。
如果int是32位或以下，这个题目只需要使用BitMap即可。
分析
- 我们可以将数据存放到BitMap中，共需要空间(2^64)=0.5G，目前的计算机可以存放。
- 计算效率是O(1)可满足性能。
以上办法可以解决32位int的场景。但别高兴得太早，此时，面试官会加大难度，如果int是64位，或元素是不是int，是字符串，怎么办呢？
此时，面试官想要得到的答案，就是BloomFilter。
算法
BloomFilter使用BitMap保存Hash计算出的校验和。为了降低冲突概率，使用不同Hash算法进行多次Hash。
在实际生产中，通常还是会用同一个Hash算法，但会对数据进行不同的处理，比如末尾添加些字符等。
特点
优点
算法简单
整个算法只需要使用多次Hash算法，单机即可完成。
使用空间小
由于使用BitMap，相比树状存储或HashMap等需要存储数据本身的算法而言。空间效率远优于一般算法。
由于BloomFilter计算简单，所需存储空间小，单机就能完成计算，可以很方便的扩展，是个非常精干的算法。但由于并未保存数据本身，因此也存在一些缺陷。
缺点
存在误判
BloomFilter存在假阳性，但不存在假阴性。不过误判概率极小。
如果BloomFilter判断元素不存在，则元素一定不存在，如果判断元素存在，则大概率存在。
不能删除元素
BloomFilter不允许删除元素，只允许添加。
由于BloomFilter不保存数据本身，所以
此外，由于存在假阳性的可能，因此即便在数组中使用计数的方式，也是存在问题。
使用场景
防止缓存被击穿
现在的系统，可以说在每个环节都会存在缓存。无论是加速静态数据的CDN，应用缓存tair，memcache，还是数据库内部，都存在缓存的设计。
如果是正常的查询，缓存通常有很高的命中率，即便存在一些未命中的情况，缓存也会更新，使得下次请求命中。但如果请求的数据本身就是不存在的呢。
可以预料到:
- 缓存会被全部击穿。
- 最终数据库中也查询不到。
- 缓存并不会更新。
这种情况下。可以使用BloomFilter来过滤掉不存在的元素。因为BloomFilter中不存在的元素，数据库里一定不存在。
另一个面试题
系统遇到大量的请求，这些请求一定会击穿缓存，应该怎么办？
答案就是BloomFilter。
用于黑名单
同样，由于所需存储空间小，也很适用于黑名单。用于过滤危险网址，垃圾邮件等。
因为存在误判，所以还需要一个白名单。
问题
为什么LevelDB中使用BloomFilter但MySQL没有？
- MySQL的Innodb的数据本地更新的，BloomFilter并不支持删除。
- 通常MySQL的数据量不会非常巨大。
- LevelDB中，已经生成的SSTable数据是不会删除的，
BloomFilter正好满足。 - LevelDB的数据结构就和缓存金字塔一样，如果数据不存在，或在较底层，就需要一层层往下查找，要没有用
BloomFilter跳不存在数据的层，就要每一层进去找，查询的成本会被放大的很厉害。 - 在B+tree中查找不存在的数据，查询成本不会像LevelDB那样放大。
总结
- BloomFilter存在极低概率的假阳性，但不存在假阴性。
- 用于保护缓存击穿，或存放过滤网址，黑名单等，BloomFilter通常是一个不错的选择，也可能是目前唯一的选择。
