BitMap|BitMap 分析 BitMap分析

BitMap 分析引入 BitMap 从字面上是位图的意思，其实从内容翻译的角度来看，应当翻译成：基于位（Bit）的映射。
这里给出一个例子：

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

【BitMap|BitMap 分析】在这样的条件下，我们就有必要引入 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); } }