2022-06-02

那些有趣的数据结构——BitMap

在开发的时候，时常会遇到去重或者校验是否存在的需求，在 Java 中当数据量小的时候可以直接使用 Set 集合进行去重或者校验存在，但数据量逐渐变大的时候使用这种去重策略可能会导致内存溢出的问题，可以根据数据的特性决定是否使用 Bitmap 解决相关需求。

什么是 Bitmap

计算机使用二进制来作为信息存储、传输的基本单位，每个二进制数字0或1就是一个Bit（最小单位）。而位图（Bitmap）的基本思想使用 bit 数组，bit 数组中的值可以是0或者1。于是 bit 在数组中的下标加上其存储的值可以标记一个值是否存在。位图最大的好处就是节省了空间，不过缺点也很明显，位图只能存储0和1，无法存储其他类型的数据。

Bitmap 的使用

部分语言中提供了 Bitmap 中的数据结构可以直接调用，在 Java 中可以自己实现或者引入 Guava 之类的第三方包。如果项目中有引入 Redis 的话也可以使用 Redis 提供的位图供临时使用，在 redis-cli 中使用以下命令即可操作。

# 存储值
setbit key offset 0/1
# 获取值
getbit key offset

# 示例
127.0.0.1:6379> setbit key 155 0
(integer) 0
127.0.0.1:6379> setbit key 123 1
(integer) 0
127.0.0.1:6379> getbit key 123
(integer) 1
127.0.0.1:6379> getbit key 155
(integer) 0

Bitmap 的应用

用户在某天的签到/访问

签到/当日是否访问在需求中经常见到，如果用户签到/访问后实时使用数据库持久化，且需要频繁查询获取当日状态用于展示，会对数据库造成较大的压力。如果用户 ID 为数字且在 long 的范围内，可以创建容量较大的 Bitmap ，当用户签到/访问后改变 Bitmap 中用户ID对应 offset 的值，从而实现简单的签到/访问记录。不过这种情况不适用于记录包含时间、途径等信息的记录。
数字的去重

应用原理同上，创建容量较大的 Bitmap ，初始化时 Bitmap 中所有 offset 中存储的值为0，如果数字存在则把对应 offset 标记为1，当下一次要来改变 offset 值时发现已经为1，则可以认为该值重复。
多站点车辆售票

高铁动车的路途较长，当一些短途车票售出后，如何判断该座位在某个区间是否邮票？应用原理同上，创建与站点数相同容量的 Bitmap，使用该 Bitmap 来记录一个座位。假设总旅途共有10站，创建容量为10的 Bitmap，当某位旅客购买了从第二站到第五站的车票，则把 2~5 的 offset 标记为1，其他 offset 为 0的则仍可售卖。
布隆过滤器

虽然 Bitmap 只能记录0/1这样的数据，但可以将数据进行 Hash 处理后存储到对应的 offset 中，从而实现数据是否存在的判断。由于 Hash 可能冲突的特殊性，布隆过滤器只能准确的判断元素一定不存在，不能判断元素一定存在。
大小排序

应用原理同上，创建较大容量的 Bitmap 后，往 Bitmap 中写入数字对应 offset 的值，全部写入完成后，遍历 Bitmap offset 输出即可。

总结

Bitmap 拥有很多的用途，可用于去重、排序，但其也存在着一定的限制，只能标识0和1，无法存储其他类型的数据，因此适合于表示 true/false 的场景。