用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等，有时间再去研究研究并整理出来。