布隆过滤器判断一个元素存在就是判断对应位置是否为`1`来确定的,但是如果要删除掉一个元素是不能直接把`1`改成`0`的,因为这个位置可能存在其它元素,所以如果要支持删除,那我们应该怎么做呢?
最简单的做法就是加一个计数器,就是说位数组的每个位如果不存在就是`0`,存在几个元素就存具体的数字,而不仅仅只是存`1`。那么这就有一个问题,本来存`1`就是一位就可以满足了,但是如果要存具体的数字比如说`2`,那就需要`2`位了,所以**带有计数器的布隆过滤器会占用更大的空间**。
#### 带有计数器的布隆过滤器
带有计数器的布隆过滤器目前也已经被实现了,下面就是一个带有计数器的布隆过滤器示例:
1. 继续在`pom.xml`文件引入下面依赖:
~~~java
<dependency>
<groupId>com.baqend</groupId>
<artifactId>bloom-filter</artifactId>
<version>1.0.7</version>
</dependency>
~~~
2. 在`src/main/java`目录下的`com.lonely.wolf.redis`包内新建一个带有计数器的布隆过滤器`CountingBloomFilter.java`(这里计数器空间大小传了`8`,即最多允许`255`次重复,如果不传的话这里默认是`16`位大小,即允许`65535`次重复。):
~~~java
package com.lonely.wolf.redis;
import orestes.bloomfilter.FilterBuilder;
public class CountingBloomFilter {
public static void main(String[] args) {
//初始化一个带有计数器的布隆过滤器
//第一个参数是存入数据量,第二个参数是fpp,第三个是带计数器的过滤器中每个空间占用大小
orestes.bloomfilter.CountingBloomFilter<String> cbf = new FilterBuilder(1000000,
0.01).countingBits(8).buildCountingBloomFilter();
cbf.add("zhangsan");
cbf.add("lisi");
cbf.add("wangwu");
System.out.println("是否存在王五:" + cbf.contains("wangwu")); //true
cbf.remove("wangwu");//删除wangwu
System.out.println("是否存在王五:" + cbf.contains("wangwu")); //false
}
}
~~~
3. 同时,需要修改`pom.xml`文件中的`mainClass`属性,把这个类名修改正确:
~~~xml
<mainClass>com.lonely.wolf.redis.CountingBloomFilter</mainClass>
~~~
4. 执行如下命令:
~~~bash
# 进入主目录
cd /home/project/redis-demo
# 将项目打包成一个 jar 包
mvn clean package -Dmaven.test.skip=true
# 运行
java -jar target/redis-demo-1.0.0-SNAPSHOT.jar
~~~
运行之后效果如下图所示,可以看到元素被成功删除:
![](https://img.kancloud.cn/bd/92/bd927c1d26f9d22b860a9b2451c97420_735x117.png)
- Redis 为什么这么快
- 什么是 Redis
- Redis 的安装
- Redis 到底有多快
- Redis 是单线程还是多线程
- Redis 为什么选择使用单线程来执行请求
- 什么是 IO 多路复用机制
- Redis 中 I/O 多路复用的应用
- 一个简单的字符串,为什么 Redis 要设计的如此特别
- Redis 的 9 种数据类型
- 二进制安全字符串
- sds 空间分配策略
- sds 和 C 语言字符串区别
- sds 是如何被存储的
- type 属性
- encoding 属性
- 通过牺牲速度来节省内存,Redis 是觉得自己太快了吗
- 什么是压缩列表
- ziplist 的存储结构
- entry 存储结构
- ziplist 数据示例
- ziplist 连锁更新问题
- 为了加快速度,Redis 都做了哪些“变态”设计
- 列表对象
- linkedlist
- linkedlist 和 ziplist 的选择
- quicklist
- 列表对象常用操作命令
- Redis 中哈希分布不均匀该怎么办
- 哈希对象
- hashtable
- ziplist
- ziplist 和 hashtable 的编码转换
- 哈希对象常用命令
- 同一份数据,Redis 为什么要存”两次”
- 五种基本类型之集合对象
- intset 编码
- 集合对象常用命令
- 五种基本类型之有序集合对象
- skiplist 编码
- ziplist 编码
- ziplist 和 skiplist 编码转换
- 有序集合对象常用命令
- 要想用活 Redis,Lua 脚本是绕不过去的坎
- 发布与订阅
- 基于频道的实现
- 基于模式的实现
- Lua 脚本
- Lua 脚本的调用
- Lua 脚本中执行 Redis 命令
- Lua 脚本摘要
- Lua 脚本文件
- 脚本异常
- 作为一款内存数据库,为什么断电后 Redis 数据不会丢失
- Redis 持久化机制
- RDB 持久化机制
- AOF 持久化机制
- 内存耗尽后 Redis 会发生什么
- 内存回收
- 过期策略
- 8 种淘汰策略
- LRU 算法
- LFU 算法
- 不能回滚的 Redis 事务还能用吗
- Redis 有事务吗
- Redis 事务实现原理
- Redis 事务 ACID 特性
- watch 命令
- watch 命令的作用
- watch 原理分析
- Redis 为什么不直接用 master-slave 集群
- Redis 集群方案
- 主从复制
- 配置一主两从 master-slave 集群
- 主从复制原理分析
- 主从服务的不足之处
- Sentinel(哨兵)机制为什么从神坛滑落
- 哨兵 Sentinel 机制
- Sentinel 原理分析
- 配置 Sentinel 集群
- Sentinel 机制实战
- Sentinel 机制的不足之处
- Redis Cluster 集群凭什么成为了最终的胜利者
- Redis 分布式集群方案
- 客户端实现分片
- 中间代理服务实现分片
- Redis Cluster 方案
- 手动配置一个 Redis Cluster 集群
- Redis Cluster 集群常用命令
- 客户端如何使用 Redis Cluster 集群
- Redis Cluster 的不足
- 如何从 10 亿数据中快速判断是否存在某一个元素
- 缓存雪崩
- 缓存击穿
- 缓存穿透
- 布隆过滤器(Bloom Filter)
- 布隆过滤器的 2 大特点
- 布隆过滤器的实现(Guava)
- 布隆过滤器的如何删除