什么是Bitmap？

所谓Bitmap,字面意思即为位映射，即用一个bit来标记某个数字对应的值。通常用于海量数据查询、去重、过滤等场景，大大节省查询时间和存储空间。

场景举例

有这样一道面试题，现有10亿个随机整数，32位机器内存1G？那我们可以算下，一个int占4个字节，即我们需要4000000000/(1024×1024×1024)≈3.7G,显然不够。那么使用bitmap呢？1bit为8位，所以每个byte记录8bit信息,也就是可以表示8个数，占据4000000000/(1024×1024×1024×8)≈465MB，空间大大节省。时间复杂度O(n)。

image.png

每个bit上我们可以用0或者1来表示这个数字是否存在。比如125这个数字，它会落在哪个字节上呢？125/8=15,落在第15个字节上，那我们应该把它存在哪个bit上呢？125%8=5，落在第5个bit上，即我们将下标为4的标记为1，此时二进制数为00001000；如果再来一个数字123呢？同样125/8=15，落在第15个字节上，125%8=3，落在第3个bit上，我们将下标为2 的标记为1，此时的二进制数为00101000，查询如果bit位为1，则存在。

java 代码示例

public class BitMap {

    public static final int DEFAULT = 1024*1024*1024;

    public int size;

    private byte[] map;

    public BitMap() {
        this.size = DEFAULT;
        this.map = new byte[size];
    }

    public BitMap(int size) {
        this.size = size;
        this.map = new byte[size];
    }

    public void set(int val) {
        if (val < 0) {
            throw new RuntimeException("need Positive integer");
        }
        //等价于val/8得到所在的第几个字节里，即位桶
        int seg = val >> 3;

        //等价于val%8获取余数，即位于上面求得所在位桶的第几位
//        int mod = val & (0x07);

        map[seg] |= 0x01 << (val & (0x07));
    }


    public boolean exist(int val) {
        if (val < 0) {
            throw new RuntimeException("need Positive integer");
        }
        //计算位于第几个桶位
//        int seg = val >> 3;
        //位于上面求得所在位桶的第几位
//        int mod = val & 7;

        return ((map[val >> 3] >> (val & 7)) & 0x01) == 0x01;
    }

}

那下面来说下代码的实现细节和详解。
例如数字125，存储为byte[15],值为2的5次方 = 32，二进制00001000，再存储123，存储为byte[15],值为2⁴⁺²2=20，二进制为00101000，即为00001000和00100000进行或运算，即为代码中的map[seg] |= 0x01 << (val & (0x07))。

image.png

即代码中((map[val >> 3] >> (val & 7)) & 0x01) == 0x01。

运行验证

public static void main(String[] args) {

        BitMap bitMap = new BitMap();

        int[] array = new int[20000000];
        Random random = new Random();


        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(5000000);
        }

        for (int i = 0; i < array.length; i++) {
            bitMap.set(array[i]);
        }
        long start = System.currentTimeMillis();

        for (int a : array) {
            if (!bitMap.exist(a)) {
                System.out.println("not exist");
            }
        }
        System.out.println("bitmap时间=" + (System.currentTimeMillis() - start));
    }

运行结果：

image.png

2千万条数据循环遍历查询时长仅50ms。