看到一个集合查找的面试题,想起这个算法。
现在有一个非常庞大的数据,假设全是 int 类型。现在我给你一个数,你需要告诉我它是否存在其中(尽量高效)。
如果int是32位或以下,这个题目只需要使用BitMap即可。
以上办法可以解决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
跳不存在数据的层,就要每一层进去找,查询的成本会被放大的很厉害。