用BitMap巧妙地解决难题

2021-12-21

知行是一个系列,记录我在实际工作中遇到的问题与解决方案,及背后的知识。问题或大或小,但须知“纸上得来终觉浅,绝知此事要躬行”,实际解决的问题能给人最深刻的印象。并旗帜鲜明地反对假大空的八股文类型文章。

这个季度负责了一个项目,项目内容大致是通过预设的模板、预设的规则以及一些人工智能的算法,帮助用户去智能地进行小别墅的设计工作(这个过程中也认识了博导级别的大佬,十分荣幸)。用户可以选择他希望制作的别墅类型,并制定一些参数,如占地面积、风格、想要有的房间类型等,提供给用户一系列模板,用户选择一个喜欢的,进一步编辑该模板相关联的布局信息与墙体结构、空间关系等等,后面还有智能设计的流程不再赘述了。

这其中遇到一个问题,产品希望对模板包含哪些房间类型的筛选是精确的,同时还希望支持分页。例如,用户希望设计的别墅中含有露台、书房、起居室、老人房,给出的模板就必须包含这些房间。

先说下简化版的存储:

每个模板是一条MySQL记录,通过key关联到HBase中的结构化数据Document。Document中包含墙体几何、房间位置、门窗等。所以我们要筛选等房间类型是存储在结构化数据中的,我们想获得的是Room列表中包含需求房间类型的那些模板。

房间类型,可以用一个枚举的整数typeid来表示(数量有限)。那么这个问题可以抽象为,给出一个房间的typeid列表,找出数据源中房间列表包含这些typeid的数据。

一开始我想对Document进行筛选、或者在表中添加一个字符串,表示所有的包含的房间id,用逗号分隔,之后再用FIND_IN_SET函数处理。最后发现都不太可行,这时轮到主角BitMap登场。

BitMap

BitMap,即位图,就是一个bit数组。其实这不是什么特殊的数据结构,在计算机中,所有东西都是用位表示的,比如Java中的整数类型Integer占4个字节,即32位,因此任何结构,都可以用来做BitMap。基本原理就是用一个bit 位来存放某种状态,比如存在或不存在。一般的用法就是将其数组的索引与状态关联,从而用较小的空间表示大量数据的状态。

在Java中,封装了BitSet类来处理。BitSet类中有一个long类型数组来表示实际的数据,也就是以64位为一个单元,可以无限扩充。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 初始化一个8bit的位图,位全部为0
BitSet bits1 = new BitSet(8);
// 初始化一个8bit的位图,位与传入的x的位一致
BitSet bits2 = BitSet.valueOf(new long[]{ x });
// 将第i位置为1
bits1.set(i);
// 将第j位置为0
bits2.clear(j);
// 判断第i位是否为1
boolean exist = bits1.get(i);
// 位运算:与、或、异或
bits1.and(bits2);
bits1.or(bits2);
bits1.xor(bits2);

解决方案

在这个问题中,我们的房间类型在一个模板中只有两种状态,存在或不存在,因此可以用一个bit来表示(如果还需要筛选出现次数,那就不适用了)。假如我们有8种房间类型,typeid分别为0-7,则一个模板中存在的房间类型可以用一个字节来表示。

0 1 1 0 0 1 0 1

这样就表示存在的房间类型有:0、2、5、6这几种。

到这里你应该想到了,就是在数据表中冗余BitMap字段来表示该模板包含的房间类型。模板创建或修改时,将Document中的Room类型提取出来,并写到表中。筛选时利用MySQL的位运算,来判断是否包含所需的房间类型。

这边走了些弯路,一开始企图用blob类型,可以无限扩充bit位,实际测试发现位运算可能失效。

“Bit functions and operators comprise BIT_COUNT(), BIT_AND(), BIT_OR(), BIT_XOR(), &, |, ^, ~, <<, and >>. (The BIT_AND(), BIT_OR(), and BIT_XOR() aggregate functions are described in Section 12.20.1, “Aggregate Function Descriptions”.) Prior to MySQL 8.0, bit functions and operators required BIGINT (64-bit integer) arguments and returned BIGINT values, so they had a maximum range of 64 bits. Non-BIGINT arguments were converted to BIGINT prior to performing the operation and truncation could occur.

由MySQL官方文档可知,位运算的底层其实是用的BIGINT,也就是8个字节的数,因此我们的BitMap字段类型就直接使用BIGINT类型,一个字段可以表示64种房间,目前房间的枚举值还没有超过64,但存在超过的可能(如引入公装等房间),因此增加一个backup字段。我们实现时,按照16个字节来做。

BO与POJO类

我们操作的业务对象中,应当把BitMap解析为Integer数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class POJO{
private Long id;
private Integer style;
private Double area;
private Long bitMap0;
private Long bitMap1;
...
}

public class BO{
private Long id;
private Integer style;
private Double area;
private List<Integer> roomTypes;
...
}

在service层进行转换的方法,从而在业务使用上无感知:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static long[] translate(List<Integer> typeIds) {
if (CollectionUtils.isEmpty(typeIds)) {
return new long[]{};
}
BitSet bitSet = new BitSet(RoomType.values().length);
for (Integer i : typeIds) {
bitSet.set(i);
}
return bitSet.toLongArray();
}

public static List<Integer> translate(long[] bitMaps) {
List<Integer> roomList = new ArrayList<>();
BitSet bitSet = BitSet.valueOf(bitMaps);
for (int i = 0; i < RoomType.values().length; i++) {
if (bitSet.get(i)) {
roomList.add(RoomType.values()[i].getTypeId());
}
}
return roomList;
}

进行筛选时,入参为BO类型,将其roomTypes转化为bitMap字段。执行SQL为(实际为Mybatis,这里做了简化)

SELECT * FROM table WHERE bit_map0 & bitMap0 = bitMap0 AND bit_map1 & bitMap1 = bitMap1 LIMIT 0, 50

这样就做到了筛选房间类型并支持分页。

结语

BitMap常常用于大数据处理中,但只要使用得当,也能非常巧妙地解决一些问题。关于BitMap的一些进阶用法,如结合Bloom Filter等,有时间再去研究研究并整理出来。