数据结构和算法的落地场景

算法：布隆过滤器（Bloom-Filter）

Bloom Filter（BF）是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter有可能会出现错误判断，但不会漏掉判断。也就是Bloom Filter判断元素不再集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。因此，Bloom Filter”不适合那些“零错误的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter比其他常见的算法（如hash，折半查找）极大节省了空间。

Bloom-Filter一般用于在大数据量的集合中判定某元素是否存在。例如邮件服务器中的垃圾邮件过滤器。在搜索引擎领域，Bloom-Filter最常用于网络蜘蛛(Spider)的URL过滤，网络蜘蛛通常有一个URL列表，保存着将要下载和已经下载的网页的URL，网络蜘蛛下载了一个网页，从网页中提取到新的URL后，需要判断该URL是否已经存在于列表中。此时，Bloom-Filter算法是最好的选择。

m	bit数组的宽度（bit数）
n	加入其中的key的数量
k	使用的hash函数的个数
f	False Positive的比率

需求

10000W个黑名单用户，快速判断当前用户是不是黑名单用户
搜索引擎判断一个网页是否已经被爬取
给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。

缺点

缺点是有一定的误识别率，不支持0误差的场景不支持删除

参考

https://www.cnblogs.com/zhxshseu/p/5289871.html

zhaobinglong / myBlog

数据结构和算法的落地场景 #33

算法：布隆过滤器（Bloom-Filter）

需求

缺点

参考