# bit-map

**Repository Path**: que-yue/bit-map

## Basic Information

- **Project Name**: bit-map
- **Description**: Redis版BitMap应用演示
- **Primary Language**: Unknown
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: http://www.altitude.xin
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2022-03-20
- **Last Updated**: 2022-03-20

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### 一、序言

在实际开发中常常遇到如下需求：判断当前元素是否存在于已知的集合中。常见的做法是将已知集合中的元素维护一个`HashSet`，比较耗时`O(1)`的时间复杂度便可判断出结果，Java或者Redis均提供相应的数据结构。使用此种方式除了占用内存空间外，几乎没有其它缺点。

当数据量达到`亿级`别时，`HashSet`占用内存空间的缺点显著表现出来，这时使用`BitMap`是解决此类问题的另一种途径。

##### Redis版BitMap的优势

-   支持分布式系统

依托Redis分布式的特性，Redis版的BitMap能够支撑分布式系统

-   存值、取值效率高

通过索引（下标）进行位置定位，存取效率较高

-   集合维护成本低

BitMap集合初始化、添加元素、移除元素操作相对简单，维护成本较低

### 二、BitMap结构

##### 1、内存消耗分析

Redis BitMap能够存储的数据范围为`[0,2^32-1]`，超过`Integer.MAX_VALUE`上界值。

为了简化讨论，假设讨论的集合元素的范围为`[0,Integer.MAX_VALUE]`，可以是其中的任何一个数。

使用`HashSet`数据结构占用内存空间仅与集合中的元素数量（N）相关。当集合中元素数量为N时，所需的内存空间大概为`N*4/1024/1024`MB，`1亿`条数据约占内存空间`381MB`。

基于Redis的BitMap所占用的空间大小不与集合中元素数量相关，与集合中元素的`最大值`直接相关，因此BitMap所占用的内存空间范围为`[N / 8 / 1024 / 1024,Integer.MAX_VALUE / 8 / 1024 / 1024]`。

```java
// 测试1亿、5亿、10亿、Integer.MAX_VALUE
List<Integer> items = Arrays.asList(100000000, 500000000, 1000000000, Integer.MAX_VALUE);
for (Integer item : items) {
    int size = item / 8 / 1024 / 1024;
    System.out.printf("如果集合中最大值为%-10s,则所占用的内存空间为%3sMB%n",item, size);
}
```

这里给出了一组测试参考数据

```text
如果集合中最大值为100000000 ,则所占用的内存空间为 11MB
如果集合中最大值为500000000 ,则所占用的内存空间为 59MB
如果集合中最大值为1000000000,则所占用的内存空间为119MB
如果集合中最大值为2147483647,则所占用的内存空间为255MB
```

当集合中数据增长到`10亿`条时，使用BItMap最大占用内存约为`255MB`，而使用HashSet增长到`3.8GB`。

##### 2、命令行操作BitMap

使用Redis命令行可直接操作BitMap，将`offset`位置的值标注为1，则表示当前数据存在。默认情况下未标注的位置值为0。

```bash
# 默认位不赋值为0，当数据存在于集合中，将对应位赋值为1
SETBIT key offset value
# 查看对应位数据是否存在（1表示存在，0表示不存在）
GETBIT key offset
```

##### 3、时间与空间复杂度

BitMap的存储与取值时间复杂度为`O(1)`，根据数值可直接映射下标。

BitMap占用内存空间复杂度为`O(n)`，与集合中元素的最大值正相关，不是集合中元素的数量。

### 三、BitMap应用

##### 1、回避缓存穿透

`缓存穿透`是指当前请求的数据在缓存中不存在，需要访问数据库获取数据（数据库中也不存在请求的数据）。缓存穿透给数据库带来了压力，恶意缓存穿透甚至能造成数据库宕机。

使用BitMap动态维护一个集合，当访问数据库前，先查询数据的主键是否存在集合中，以此作为是否访问数据库的依据。

BitMap新增数据或者移除数据属于轻量级操作，检查操作的准确度依赖于动态集合维护的闭环的完整性。比如向数据库增加数据时需要向BitMap中添加数据，从数据库中删除数据需要从BitMap中移除数据。如果要求严格的检查可靠性，则可以单独维护一个分布式定时任务，定期更新BitMap数据。

##### 2、与布隆过滤器的区别

布隆过滤器与BitMap有相似的应用场景，但也有一定的区别。给定一个数，BitMap能准确知道是否存在于已知集合中；布隆过滤器能准确判断是否不在集合中，却不能肯定存在于集合中。

BitMap增加或者移除数据时间复杂度为O(1)，方便快捷。布隆过滤器新建容易，剔除数据操作比较繁琐。

在一些需要精确判断的场景，优先选择BitMap，比如判断手机号是否已经注册。

##### 3、应用场景拓展

Redis BitMap不是一种新的数据结构，是利用字符串类型做的一层封装，看起来像一种新型数据结构。BitMap不像一种技术，更像是算法，在时间复杂度和空间复杂度之间寻找平衡点。

BitMap其它应用场景比如签到打卡，统计在线人数等等。

### 四、SpringBoot集成

##### 客户端操作BitMap

这里提供一个SpringBoot生态的`RedisUtils`工具类，内部封装操作Redis BitMap的工具方法。

```java
// 将当前位置标记为true
RedisUtils.setBit(BIT_MAP_KEY, orderId, true);
// 获取指定位置的值（对应数值是否存在）
RedisUtils.getBit(BIT_MAP_KEY, orderId)
```

上述工具类的依赖如下，如果找不到Jar包，请直接使用Maven原始仓库源，阿里云尚未同步完成。

```xml
<dependency>
    <groupId>xin.altitude.cms</groupId>
    <artifactId>ucode-cms-common</artifactId>
    <version>1.4.3</version>
</dependency>
```

具体配置如下，在pom文件中添加如下配置：

```xml
<repositories>
    <repository>
        <id>public</id>
        <name>maven nexus</name>
        <url>https://repo1.maven.org/maven2/</url>
        <snapshots>
            <updatePolicy>always</updatePolicy>
        </snapshots>
        <releases>
            <updatePolicy>always</updatePolicy>
        </releases>
    </repository>
</repositories>
```

---
> 喜欢本文点个♥️赞♥️支持一下，如有需要，可通过微信`dream4s`与我联系。相关源码在[GitHub](https://gitee.com/decsa)，视频讲解在[B站](https://space.bilibili.com/1936685014)，本文收藏在[博客天地](http://www.altitude.xin)。
---