简介

主要由一个二进制数组和一系列哈希映射函数两部分组成的数据结构。

优点为占用空间更少，效率更高。

缺点为结果为概率性的，而不是很准确，理论轻装下添加的元素越多，错误的可能性越大，且存放在布隆过滤器的数据不容易被删除。

原理

  1. 加入操作：

    • 用哈希函数对元素进行计算，得到哈希值（如果有多个哈希函数则得到多个哈希值。

    • 根据得到的多个哈希值，在位数组中把哈希值对应下标的值设置为1。

  2. 判断是否存在与布隆过滤器：

    • 对元素进行哈希计算。
    • 得到值后判断位数组相应位置是否都为1，如果都为1，说明这个值大概率在布隆过滤器中，如果存在一个值不为1，则说明元素肯定不在布隆过滤器中。

Redis的BloomFilter

Redis的bitmap只支持2的32次方大小，对应需要的内存为512MB，误判率万分之一，可以放下2亿的数据，性能高，空间占有小，省去了无效的数据库连接。

此外布隆过滤器还可以推荐去重

例如新闻客户端的推送去重功能，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。

实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行 exists 查询，当系统并发量很高时，数据库是很难扛住压力的。如果使用缓存把历史记录都放入缓存里，占用空间太大明显不现实，这个时候布隆过滤器就登场了，它就是专门用来解决这种去重问题的。它在起到去重的同时，在空间上还能节省 90% 以上，只是稍微有那么点不精确，也就是有一定的误判概率。

用户浏览记录存入数据库时，会在Filter上通过key的hash算法存储判断其是否存在，类似于数据存在数据库中，判断该数据是否存在的信息即元数据存放在BloomFilter中，避免了每次判断数据是否存在都要去数据库exist一遍；这样推送新闻时通过布隆过滤器判断，推送内容是否已经存在，如果存在则不推送，如果不存在则推送；

布隆过滤器可以准确过滤你已经看过的内容，没有看过的新内容，可能由于误判率过滤掉极小的一部分，这样就可以保证推荐给用户的都是无重复的。