布隆过滤器

https://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8

什么是布隆过滤器

它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

特点

可能在集合 绝对不在集合中

误判率(FPP)

布隆过滤器的应用

主要用在过滤一些重复数据上。布隆过滤器并不可靠，只能判断一定不在和可能存在的情况。 即如果误判对整体流程无伤大雅。如果对数据的正确性有要求时就不能使用。

• 爬虫对 URL 去重，避免重复爬取
• 判断是否为垃圾邮箱
• 重复元素的判断
• 缓存穿透等问题