什么是布隆过滤器
布隆过滤器 (Bloom Filter) 是由 Howard Bloom 在 1970 年提出的一种比较巧妙的概率型数据结构, 它可以告诉你某种东西一定不存在或者可能存在. 当布隆过滤器说, 某种东西存在时, 这种东西可能不存在; 当布隆过滤器说, 某种东西不存在时, 那么这种东西一定不存在.
布隆过滤器相对于 Set,Map 等数据结构来说, 它可以更高效地插入和查询, 并且占用空间更少, 它也有缺点, 就是判断某种东西是否存在时, 可能会被误判. 但是只要参数设置的合理, 它的精确度也可以控制的相对精确, 只会有小小的误判概率.
Redis 中布隆过滤器
之前的布隆过滤器可以使用 Redis 中的位图操作实现, 直到 Redis4.0 版本提供了插件功能, Redis 官方提供的布隆过滤器才正式登场. 布隆过滤器作为一个插件加载到 Redis Server 中, 就会给 Redis 提供了强大的布隆去重功能.
布隆过滤器的基本使用
在 Redis 中, 布隆过滤器有两个基本命令, 分别是:
bf.add: 添加元素到布隆过滤器中, 类似于集合的 sadd 命令, 不过 bf.add 命令只能一次添加一个元素, 如果想一次添加多个元素, 可以使用 bf.madd 命令.
bf.exists: 判断某个元素是否在过滤器中, 类似于集合的 sismember 命令, 不过 bf.exists 命令只能一次查询一个元素, 如果想一次查询多个元素, 可以使用 bf.mexists 命令.
比如:
- > bf.add one-more-filter fans1
- (integer) 1
- > bf.add one-more-filter fans2
- (integer) 1
- > bf.add one-more-filter fans3
- (integer) 1
- > bf.exists one-more-filter fans1
- (integer) 1
- > bf.exists one-more-filter fans2
- (integer) 1
- > bf.exists one-more-filter fans3
- (integer) 1
- > bf.exists one-more-filter fans4
- (integer) 0
- > bf.madd one-more-filter fans4 fans5 fans6
- 1) (integer) 1
- 2) (integer) 1
- 3) (integer) 1
- > bf.mexists one-more-filter fans4 fans5 fans6 fans7
- 1) (integer) 1
- 2) (integer) 1
- 3) (integer) 1
- 4) (integer) 0
上面的例子中, 没有发现误判的情况, 是因为元素数量比较少. 当元素比较多时, 可能就会发生误判, 怎么才能减少误判呢?
- > bf.reserve one-more-filter 0.0001 1000000
- OK
来源: https://www.cnblogs.com/heihaozi/p/12174478.html