哈希系列-布隆过滤器

bloom Filter 布隆过滤器
K个hash函数，当写入一个key的时候，设置H1(key), H2(key)…Hk(key)为1。当需要check key是否存在的时候，依次检测H1(key)…Hk(key)是否均为1，如果其中一个不为1，则表示key不存在；否则认为key存在。

注意：有错误判断的可能性，所以仅仅适用于允许一定错误率的场景。

应用：

1. 爬虫程序url是否处理过
2. 黑名单,垃圾邮件过滤
3. 是否关注、判断用户关系（如果出现误判，顶多会多回源一次数据库）
4. 【TODO，没看明白】Bloom filter在重复数据删除中的应用。主流的重复数据删除技术的基本原理是对文件进行定长或变长分块，然后利用hash函数计算数据块指纹，如果两个数据块指纹相同则认为是重复数据块（同样这里存在数据碰撞问题），只保存一个数据块副本即可，其他相同数据块使用该副本索引号表示，从而实现数据缩减存储空间并提高存储效率。