位图BiMap

在此记录我学的位图相关知识

是什么

是一种数据结构。也可以认为是一种二进制数组。
一个整型int是32位，用他的二进制能表示0-31这些整数是否出现过。

我们现在看int，要深入到微观去看，即看它的二进制，它有32个bit位。

比如现在很多App上每月都有签到活动，一个月签到几次就送大礼包。这个功能我们就可以使用这种思想来实现。

int calender; 用这一个整型来统计某个月的签到情况。

day 表示第几天
签到：即第day天签到了，则
int calender =0; 
calender |= (1 << (day & 31))//day表示第几天public void qiandao(int day){int calender =0;  // 00000000 00000000 00000000 00000000 calender |= (1 << (day & 31));System.out.println(calender);}@Testpublic void t1(){qiandao(2);//结果是 4。// 对应二进制  00000000 00000000 00000000 00000100// 说明第二天签到了}

一个整型数组int[ ] a = new int[32];

每个元素都是32位 , 32*32= 1024。所以，这个数组能表示0-1023这些整数是否出现过。

相当于连起来了。

同理

一个long 是64位，能表示0-63数字是否出现过。

一个long数组 long[ ] b = new long[32], 32 * 64 = 2048 ,所以，这个数组能表示0-2047这些整数是
否出现过。

每一格子存储64个整数是否存在，a[0]可以表示0-64，a[1]可以表示64-127。返过来

126>>6 = 1（即126/64=1）,即126落在a[1]里，又因为126 & 63=62(即126 % 64 = 62)，所

以，具体来说是 a[1]的第62位表示126是否存在。

若存在，如何将该位设置为1？

使用 | 运算，即按位或运算。

1L 是long形的数字1，有64位，00000000000........000000001

1L << (126 &63) 然后 | 上a[1]

即 a[1] = a[1] | ( 1L << ( 125 & 63))

简写为 a[ 1 ] |= 1L << ( 125 & 63)

可以把数组每个元素看出一个桶。

把握关键点：添加时：

①确定该数在数组中的哪个元素中（哪个桶中）--- /操作，用 >> 代替

②确定用该元素的哪一位表示 ---- % 操作，用 &代替

为什么代替？因为位运算速度飞快

那如何删除呢？也很简单。使用 & ，用0 去和那个bit位进行 & 操作。

代码实现位图

看代码应该比较好懂。就是对二进制、位运算的一种巧妙应用。

public  class BitMap{public long[] bits;public BitMap(int max){//给定最大的数//若max=1，则数组长度得是1.若max=0，数组长度是1.抠边界。// >> 6 等价于 /64,但位运算速度更快bits = new long[(max+64) >> 6];}//num & 63 即num%64,看是该元素的第几位。public void add(int num){//两步：找到数组中对应的元素，然后，将相应位 弄成1. 必须写1L，表示是64位的1。//bits[num >> 6] = bits[num >> 6] | (1L << (num & 63));//简写为//bits[num >> 6 ]是确定在哪个桶里。num & 63 是确定在该桶的哪个位置，让1移动过去对准//每一个桶64位bits[num >> 6] |= (1L << (num & 63));}//删除public void delete(int num){bits[num >> 6] &= ~(1L << (num & 63));}public boolean contains(int num){return (bits[num >> 6] & (1L << (num & 63))) != 0;}
}

带有测试的

public  class BitMap{public long[] bits;//给定一个预估的最大值，初始化数组，看看最多需要几个格子（几个坑位）//    如果实际业务中，超过了，那就重写造一个public BitMap(int max){//给定最大的数//若max=1，则数组长度得是1.若max=0，数组长度是1.抠边界。//看看最多需要几个格子。 >> 6 等价于 /64,但位运算速度更快bits = new long[(max+64) >> 6];}//num & 63 即num%64,看是该元素的第几位。public void add(int num){//两步：找到数组中对应的元素，然后，将相应位 弄成1. 必须写1L，表示是64位的1。//bits[num >> 6] = bits[num >> 6] | (1L << (num & 63));//简写为//bits[num >> 6 ]是确定在哪个桶里。num & 63 是确定在该桶的哪个位置，让1移动过去对准//把1怼上去//每一个桶64位bits[num >> 6] |= (1L << (num & 63));}//删除 // 这个好理解，就是先非一下，然后和他与，这样可以保证其他位置不变，只变标志位public void delete(int num){bits[num >> 6] &= ~(1L << (num & 63));}public boolean contains(int num){return (bits[num >> 6] & (1L << (num & 63))) != 0;//注意：是!=0, 它的结果不一定全是1}//1L << (num & 63) 相当于一个可以滑动的游标，一个辅助工具。public static void main(String[] args) {System.out.println("测试开始！");int max = 10000;BitMap bitMap = new BitMap(max);HashSet<Integer> set = new HashSet<>();int testTime = 10000000;for (int i = 0; i < testTime; i++) {int num = (int) (Math.random() * (max + 1));double decide = Math.random();if (decide < 0.333) {bitMap.add(num);set.add(num);} else if (decide < 0.666) {bitMap.delete(num);set.remove(num);} else {if (bitMap.contains(num) != set.contains(num)) {System.out.println("Oops!");break;}}}for (int num = 0; num <= max; num++) {if (bitMap.contains(num) != set.contains(num)) {System.out.println("Oops!");}}System.out.println("测试结束！");}}