位图

概述

位图(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);
  }
}