1. 首页
  2. 后端

Bitmap个人理解和简单代码实现

  Bitmap个人理解和简单代码实现

=================

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相当于对
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000100
这两个二进制数进行或运算,结果是
00000000 00000000 00000000 00000100
*/

检查数字是否存在

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

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

/*
假设container是
00000000 00000000 00000000 00000101
1 << 2是
00000000 00000000 00000000 00000100
进行与运算结果是
00000000 00000000 00000000 00000100
*/

移除某个数字

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

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

/*
假设container是
00000000 00000000 00000000 00000100
~ (1 << 2)是
11111111 11111111 11111111 11111011
进行与运算结果是
00000000 00000000 00000000 00000000
*/

想要存储更多数字

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

代码实现

class Bitmap {
  private final int[] container;

  public Bitmap(int capacity) {
    // 这里有问题 不能这样写 这样根本没法向上取整 我还是太菜了 低级错误 
    // container = new int[((int) Math.ceil(capacity / 32))];
    container = new int[(capacity >> 5) + ((capacity & 31) > 0 ? 1 : 0)];
  }

  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.BitSetBitSet内部用long类型来存储数据。

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

原文链接: https://juejin.cn/post/7359391403163041811

文章收集整理于网络,请勿商用,仅供个人学习使用,如有侵权,请联系作者删除,如若转载,请注明出处:http://www.cxyroad.com/17178.html

QR code