经典算法系列之 - BitMap

BitMap的应用十分广泛，可以用于大数据快速排序、去重、查询，Redis中也有应用，甚至HBase中的Bloom Filter的底层实现也是基于BitMap的扩展，因此我对BitMap的原理进行了初步认识，并手动实现了一个BitMap。

问题引入

BitMap从字面直译是位图的意思，其实准确的来说，翻译成基于位的映射。

举个栗子，有一个无序有界int数组{1,2,5,7}，初步估计占用内存 4 x 4 = 16 字节，这倒没什么说法，但是如果这样的数据有10亿呢，10亿 x 4 / (1024 x 1024 x 1024) = 3.72G 左右。如果这样一个大的数据做查找和排序，那估计内存也崩溃了，即使你的机器配置足够，这样大的一个内存占用量也值得商榷和优化。

问题分析

如果用BitMap的思想来解决这个问题的话，会好很多很多。BitMap的思想如下：

一个byte是8个bit，如果一个bit的值就是有或者没有，也就是二进制的0或者1，用bit的位置代表数组值有还是没有，那么0代表该数值没有出现过，1代表该数值出现过。用这种方式依然可以描述数据。

是不是有一丢丢神奇，那么现在10亿的数据所占的空间就是3.72G/32了，一个占用32bit的数据现在只用了1bit，存储空间节省了31倍。如果数据之间没有关联性，还可以用多线程的方式去读取并计算，时间复杂度为O(Max/n)，其中Max为byte数组的大小，n为线程数。

代码实现

在看代码之前，先搞清楚一个问题，一个数怎么快速定位它的索引号，也就是说搞清楚byte[index]的index是多少，position是哪一位。举个栗子，例如14，14已经超出byte[0]的映射范围，在byte[1]范围之类。那么怎么快速定位它的索引呢，Index(N)代表N的索引号，Position(N)代表N的所在的位置号，那么：

Index(N) = N/8 = N >> 3

Position(N) = N%8 = N & 0x07

public class BitMap {
    // 保存数据的byte数组
    private byte[] bits;

    // 能够存储多少个数据
    private int capacity;

    public BitMap(int capacity) {
        this.capacity = capacity;

        // 1byte能存储8个数据，那么capacity个数据需要capacity/8+1个byte,右移3位相当于除以8
        bits = new byte[(capacity >> 3) + 1];
    }

    /**
     * add方法的本质就是将数据对应索引位置标记为1
     * */
    public void add(int num) {
        // num/8得到byte[]的index
        int arrayIndex = num >> 3;

        // num%8得到在byte[index]的位置
        int position = num & 0x07;

        // 将1左移position后的位置记为A，那么A位置自然就是1，然后和以前的数据做|，这样，A位置就替换成1了
        bits[arrayIndex] |= 1 << position;
    }

    /**
     * contain方法的本质就是判断数据对应索引位置是不是0
     * */
    public boolean contain(int num) {
        // num/8得到byte[]的index
        int arrayIndex = num >> 3;

        // num%8得到在byte[index]的位置
        int position = num & 0x07;

        // 将1左移position后的位置记为A，那么A位置自然就是1，然后和以前的数据做&，判断A位置是否为0即可
        return (bits[arrayIndex] & (1 << position)) != 0;
    }

    /**
     * clear方法本质就是将数据对应索引位置标记为0，其他所有位置不变，所以其他位置做&1操作
     * */
    public void clear(int num) {
        // num/8得到byte[]的index
        int arrayIndex = num >> 3;

        // num%8得到在byte[index]的位置
        int position = num & 0x07;

        // 将1左移position后的位置记为A，那么A位置自然就是1，然后对位取反，再与当前值做&，即可清除A位置
        bits[arrayIndex] &= ~(1 << position);

    }

    public static void main(String[] args) {
        BitMap bitmap = new BitMap(100);
        bitmap.add(7);
        System.out.println("insert 7 success!");

        boolean isExist = bitmap.contain(7);
        System.out.println("7 exists:" + isExist);

        bitmap.clear(7);
        isExist = bitmap.contain(7);
        System.out.println("After clear, 7 exists:" + isExist);
    }
}

注：本文只是初步对BitMap的原理有所了解，后续会记录一些BitMap的实际应用场景，以及BitMap有哪些优劣势，以及如何优化BitMap。