概述
位图（BitMap）使用二进制的比特位来表示一个数是否存在，比如一个字节占 8 个比特位，这样就能用该字节表示 1-8，对应比特位为 1 表示对应数字存在，为 0 则不存在，大大节约存储空间
位图的 Java 实现
在 java.util 包中有官方的位图实现 BitSet，我们也可以自己实现位图
Java 使用 byte[] 字节数组来存储位数据。对于位数据中的第 i 位，该位为 1 表示 true，即数据存在；为 0 表示 false，即数据不存在
位图的数据结构如下，以 bit 为存储单位
public class Bitmap {
private byte[] bytes;
// length 为位图的长度
private int length;
public Bitmap(int length) {
this.length = length;
bytes = new byte[length % 8 == 0 ? length / 8 : length / 8+1];
}
}
假设要查询的值为 val，使用位图的查询操作如下：
- 通过 val/8 得到目标位所在的字节 arrayIndex
- 通过 val%8，得到目标位在该字节中的位置 bitIndex
- 令 bytes[arrayIndex] & (1<<bitIndex) 将对应目标位以为的位全部置 0 并得到最终值，如果最终值为 0 则表示 false，否则表示 true
public boolean get(int val) {
int arrayIndex = val /8;
int bitIndex = val % 8;
if((bytes[arrayIndex] & (1 << bitIndex)) != 0) {
return true;
}
return false;
}
假设要修改的值为 val，使用位图的修改操作如下：
- 按照查询的思路找到 val 所在的目标位
- 如果修改 val 为数据存在，将目标位与 1 做或运算，需要构建目标位为 1，其他位为 0 的操作数
- 如果修改 val 为数据不存在，将目标位与 0 做与运算，需要构建目标位为 0，其他位为 1 的操作数
public void set(boolean flag, int val) {
int arrayIndex = val /8;
int bitIndex = val % 8;
if(flag) {
bytes[arrayIndex] |= 1 << bitIndex;
} else {
bytes[arrayIndex] &= ~(1 << bitIndex);
}
}