掘金后端 ( ) • 2024-04-20 09:52

bitmap本质上是一个0/1数组，用一个bitmap表示任意一个数字N，则只需要将数组的第N位置为1，例如

要表示数字2，就是将下标为2处置为1

   ---+---+---+---+---+---+
  ... | 0 | 0 | 1 | 0 | 0 |
   ---+---+---+---+---+---+
index: ...  3   2   1   0

基于此特性，可以将该01序列看成一个二进制数，而该二进制数当然可以用更符合人类直觉的十进制数来表示，例如上面的例子可以将它看成一个十进制数也就是100，转成十进制也就是8。

在Java中，一个int类型的整数在内存中占4字节，也就是4 * 8 = 32比特（位），也就是说如果用int来实现bitmap的话，一个int类型的整数就可以存储32个整数。

假如要在大量的整数中快速判断某个数字是否存在，用HashSet<Integer>当然可以做到，但是同样的需求用bitmap来实现将极大的节省空间，毕竟每一个整数都只用一个bit来表示，比用int要节省32倍的空间，况且 HashSet<Integer>存储的还是Integer，包装类型比原始类型占的空间要更多了。

实现细节

存储数字

假设要将数字2存到一个int里，就需要将该int整数的第2位置为1，具体可以通过位运算中的或运算来实现

int container = 0;
container |= 1 << 2;

/*
1 << 2：将1左移2位，以二进制来表现也就是100
container |= 1 << 2相当于对
0000 0000 0000 0000
0000 0000 0000 0100
这两个二进制数进行或运算，结果是
0000 0000 0000 0100
*/

检查数字是否存在

假设检查n是否存在于刚刚的container里，只需要将1左移n位然后与container进行与运算，结果不为0则说明n存在

int n = 2;
if ((container & (1 << n)) > 0) {
  // 2存在于container中
}

/*
假设container是
0000 0000 0000 0101
1 << 2是
0000 0000 0000 0100
进行与运算结果是
0000 0000 0000 0100
*/

移除某个数字

假设要从container中移除n，实际上也就是将container的二进制形式的第n位置为0，那么对应的做法就是，将1左移n位后取反，再跟container进行与运算，这样可以只将指定位的数置为0，不影响其他位上的数

int n = 2;
container &= ~ (1 << n);

/*
假设container是
0000 0000 0000 0100
~ (1 << 2)是
1111 1111 1111 1011
进行与运算结果是
0000 0000 0000 0000
*/

想要存储更多数字

一个int只能存32个数，那如果想存比32更大的数怎么办，那就需要不止一个int了，可以使用一个int数组，并且在实现上比只有一个int的时候要多一步操作，也就是计算要存储在第几个int上，这很简单，例如我要存48，那么就需要一个长度为2的int数组，将48除以32，得到结果为1，也就是48将被存到下标为1的那个int上，而余数是几，就将这个int的第几位置为1

代码实现

class Bitmap {
  private final int[] container;

  public Bitmap(int capacity) {
    container = new int[((int) Math.ceil(capacity >> 5))];
  }

  public void set(int n) {
    // 众所周知将数字右移n位等价于将它除以2的n次幂，所以(n / 32)可以用(n >> 5)来代替
    // 这里n % 32可以用n & 31代替，原理是：当b = 2 ^ n时，a % b等价于a & (n - 1)
    // Java的HashMap中计算键存放的下标的时候就利用了这个特点，将普通的乘除转换成位运算，速度要稍快些，将性能优化到极致
    container[n >> 5] |= 1 << (n & 31);
  }

  public boolean contains(int n) {
    return (container[n >> 5] & (1 << (n & 31))) > 0;
  }

  public void remove(int n) {
    container[n >> 5] &= ~ (1 << (n & 31));
  }

  public void clear() {
    for (int i = 0; i < container.length; i++) {
      container[i] = 0;
    }
  }
}

实际上Java中有内置的bitmap的实现，就是java.util.BitSet，BitSet内部用long类型来存储数据。

bitmap的缺点也很明显，当数据稀疏的时候，也会浪费大量的空间，对此也有改进后的数据结构，实现起来更复杂，比如roaring bitmap，我也没研究，就不往下细说了。