位图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);
    }
    @Test
    public 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 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("测试结束！");
    }
 
 
 
}

什么用

当最大值确定时，就可以用位图收集数字，表示是否存在。好处是极大省空间。

搞牛逼一点，就是布隆过滤器，布隆过滤器就是使用 位图 + 多个哈希函数 实现的。

位运算常识

a << 1 等价于 a*2

a<<2 等价于 a*4

a<<3 等价于 a*8

a<<4 等价于 a*16

a>>1 等价于 a/2

a >> 2 等价于 a/4

a>>3 等价于 a/8

a>> 4 等价于 a/16

a>>5 等价于 a/32

a>>6 等价于 a/64

a%64 等价于 a & 63,

a % n 等价于 a & (n-1)，前提是 n必须是 2的k次幂，即n必须是 1、2、4、8、16、32、64、128...这样的数才行。

在JDK8的  HashMap源码里，二次哈希值对数组长度取模，得到索引。也用了这个操作,

hash & (length -1)

位运算的速度很快。