Bloom过滤器
它要解决什么问题
假设我们有一个1000W行的手机号黑名单数据库，现在有一个需求，给一批用户发送短信推送，要求用户手机号不在黑名单数据库里面。
如何判断A在集合B中？
有哪些数据结构可以表示一个set？
- Self-balancing binary search trees
- Tries
- Hash tables
- Simple arrays
- Linked lists of the entries
上面的数据结构大都要求把实际数据存储到数据节点中，有些不够快、有些太大了
Bloom过滤器粉墨登场
核心原理是：
⼏个hash函数, 计算出n个结果, 并在
filter数据中将对应的位置为1
数据查询
查询是否在结果集中, 要⽤同样的hash算法, ⽐对是否所有结果位都为1
- 如果返回
1，数据可能在集合中 - 如果返回
0，数据绝逼不可能在集合中
使用场景
看到下面这些，你就可以放心大胆的用啦
Google BigTable,Apache HBase以及Apache Cassandra使⽤bloomfilter检查字段是否存在.Google Chrome浏览器, 使⽤bloomfilter检查恶意⽹址.Squid代理服务器使⽤bloomfilter检查缓存是否存在.Bitcoin⽐特币使⽤bloomfilter提升数据钱包的同步效率.MongoDB使⽤bloomfilter检查数据是否位于某个节点.Exim使⽤bloomfilter防范⾼频次的恶意邮件.- 许多搜索引擎⼚商使⽤bloomfilter帮助爬⾍防⽌多次爬取同⼀个url地址.
使用的局限性
不支持删除操作，如要支持，需要使用counting bloomfilter filters的变种
误判的概率
m是数组的位数k是哈希函数的个数n是要插入的原始的个数
下面是一个神奇的公式
合理的k值
