[数据结构与算法]java bitmap 位图

Java 有bitset集合，但是没有bitmap，bit*就是位图，代码如下<代码段>

有何用？

我们平时存储数据到集合，一般用hashmap，存储的基本单位就是字节，像Java基本类型int占用就是4个字节，即4*8=32位，要是存储上亿条数据，显然太耗费存储；若用位来表示，一位代表一个数据，数据存在就显示为1，不存在就是0，那就很节约空间了不是，使用场景可用来判断数据是否存在；

像一个字节范围内，0，3，7占用的位置表示如下：?

核心逻辑：

public void add(int num) {
    //数组的哪个下标中
    int index = num / 8;
    //下标元素的哪个位置
    int position = num % 8;
????//1往左移位，目的是为了保证数值是0的也能有一位来表示，且能保证此数与byteBits[index]中已有   的数据,位错开
    byte tempBit = (byte) (1 << position);
    byteBits[index] = (byte) (byteBits[index] | tempBit);
}

解释下：

目的是为了保证数值是0的也能有一位来表示，且能保证此数与byteBits[index]中已有 的数据,位错开

例如：8，经过运算，得到存储到byteBits[1]里，position为0，存0肯定就不对了，没有体现存8，所以byteBits[1]里，存00000001，就好了，怎么表示呢：1 << position?。然后，解释下 位错开：举例，现在bitmap里存储了数据3，现在要新增存储数据5，我们通过int index = num / 8 计算出来，这两个数据都在byteBits[0]里，通过int position = num % 8又算出来3的位置为3（用二进制00000011）、5的位置为5（00000101），若5不往左移动1位，就直接进行byteBits[index] | tempBit 运算，显然00000011与00000101结果会重叠，即00000101，那就体现不出来已经存储的数据3了，往左移位呢，正好可以，结果为00001111；

然后判断是否包含某个数字：

首先将byte tempBit = (byte) (1 << position); 然后与byteBits[index]&tempBit，不为0就表示位上有1体现的数据存在，即包含这个数字的

public class Bitmap {
    //数据容器
    private byte[] byteBits;
    //最大值
    private int maxValue;
    //容量
    private int capacity;

    //构造器初始化
    public Bitmap(int maxValue) {
        this.maxValue = maxValue;
        //得出需要多少个byte
        this.capacity = (maxValue / 8) + 1;
        byteBits = new byte[capacity];
    }

    public void add(int num) {
        //数组的哪个下标中
        int index = num / 8;
        //下标元素的哪个位置
        int position = num % 8;

        byte tempBit = (byte) (1 << position);
        byteBits[index] = (byte) (byteBits[index] | tempBit);
    }

    public boolean contains(int num) {
        int index = num / 8;
        int position = num % 8;
        byte tempBit = (byte) (1 << position);
        return (byteBits[index] & tempBit) != 0;
    }

    public static void main(String[] args) {
        Bitmap bitmap = new Bitmap(10);
        bitmap.add(9);
        bitmap.add(8);
        bitmap.contains(9);
        bitmap.contains(8);
        bitmap.contains(7);
        bitmap.contains(10);
    }
}