位图

概述

位图（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，使用位图的查询操作如下：

1. 通过 val/8 得到目标位所在的字节 arrayIndex
2. 通过 val%8，得到目标位在该字节中的位置 bitIndex
3. 令 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，使用位图的修改操作如下：

1. 按照查询的思路找到 val 所在的目标位
2. 如果修改 val 为数据存在，将目标位与 1 做或运算，需要构建目标位为 1，其他位为 0 的操作数
3. 如果修改 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);
  }
}