BitMap 分析

引入

BitMap 从字面上是位图的意思，其实从内容翻译的角度来看，应当翻译成：基于位（Bit）的映射。

这里给出一个例子：

假如我们有一个无序的 int 数组，如 int arr[] = { 1, 4, 9, 3}; 这个数组占用内存 44 = 16 字节，一个这样的数据不可怕，但是假如有一亿个这样的数据，那么占用的内存 10^816/(102410241024) = 3.75G, 要想对这样巨大的数据进行查找，内存基本就会崩溃了。如果不是一次性的查找，那么就需要在硬盘上存盘，存盘就会带来 IO 的消耗，这样就会影响性能。

在这样的条件下，我们就有必要引入 BitMap 了。那么 BitMap 如何解决这个问题呢？

由于一个 Byte 占用 8 个 Bit，每一个 Bit 有 0 和 1 两个开关量，那么如果用一个二进制的 0 和 1 来代表该数是否存在，不是也能用来描述数组吗？

Byte[0]	1	0	1	0	0	1	1	0
	7	6	5	4	3	2	1	0
Byte[1]	0	0	0	0	1	0	0	0
	15	14	13	12	11	10	9	8

如果按照上图的表格进行表示数组，那么原来的 3.75 G 的数组就能通过 3.75/32 = 0.12 G 的数组来进行表示，首先节省了大量的空间，排序也更加简单了。这样的数据由于没有关联性，可以通过多线程进行读取，这样时间复杂度为 O(n/x)，其中 n 为 全部数组的大小，x 为线程数量

应用

BitMap 不仅仅优越在占用空间小，由于针对 Bit 的逻辑运算也十分简单，使得其可以用于权限计算上

不过用到这个的时候，我们首先得知道如何对一个数据进行定位，即对于一个数据N，如何确定 index（组号）和 position（每组的位置号）：

例如对于 14，14 超过了 Byte[0] 的范围，到达了 Byte[1] 的范围，那么我们对其进行定位可以用：

Index(N) = N / 8 = N >> 3 ;
Position(N) = N % 8 = N & 0x07 ;

添加数据 add(N)

如果想把一个数据 N 加入数组，按照前面所述，就只用把二进制的第 N 位置 1 即可，那么我们只用找到其组数和位置，进行位操作就可以了。

0	0	0	0	1	0	0	0
		做	|	操	作
0	0	0	0	0	1	0	0
		得	到
0	0	0	0	1	1	0	0

void add(int num)
{
  int index = num >> 3;         //  index = num / 8; 这两个是等价的
  int position = num & 0x07;    //  index = num % 8; 这两个是等价的
  bit[index] |= 1 << position;  // 相当于把 position 位置的数变成 1
}

删除数据 delete(N)

删除也是一样的，只需要对 1 进行左移操作，然后取反，对其进行与就可以了

void delete(int num)
{
  int index = num >> 3;             //  index = num / 8; 这两个是等价的
  int position = num & 0x07;        //  index = num % 8; 这两个是等价的
  bit[index] &= ~(1 << position);   // 相当于把 position 位置的数变成 0，后续位不变
}

确认数据 contain(N)

确认的话也是只用确认相应位是否为1 即可

char contain(int num)
{
  int index = num >> 3;         //  index = num / 8; 这两个是等价的
  int position = num & 0x07;    //  index = num % 8; 这两个是等价的
  return (bit[index] & 1 << position) != 0; // 相当于确认当前位是否为1
}

全部代码 C++：

public class BitMap {
    private byte[] bits;     //用于保存数据


    private int capacity;    //保存的数据量

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

        //capacity 需要 capacity/8+1 个bit
        bits = new byte[(capacity >>3 )+1];
    }

    public void add(int num){
        int arrayIndex = num >> 3;
        int position = num & 0x07;
        bits[arrayIndex] |= 1 << position;
    }

    public boolean contain(int num){
        int arrayIndex = num >> 3;
        int position = num & 0x07;
        return (bits[arrayIndex] & (1 << position)) !=0;
    }

    public void clear(int num){
        int arrayIndex = num >> 3;
        int position = num & 0x07;
        bits[arrayIndex] &= ~(1 << position);

    }

    public static void main(String[] args) {
        BitMap bitmap = new BitMap(100);
        bitmap.add(7);
        System.out.println("插入7成功");

        boolean isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);

        bitmap.clear(7);
        isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);
    }
}