算法---BitMap

问题：

假设有3亿个整数（范围0-2亿），如何判断某一个树是否存在。局限条件一台机器，内存500m。

常规的思路：我们可以将数据存到一个集合中，然后判断某个数是否存在；或者用一个等长的数组来表示，每个数对应的索引位置，存在就标记为1，不存在0。当然如果设备条件允许，上面的这方案是可行的。

但是现在我们内存只有500m。Int类型4个字节。

单单是这3亿个数都已经：300000000*4/1024/1024 差不多1144m了。显然已经远超过内存限制了。

显然在这种条件下面，我们想要将这些书完整的存储下来已经是不现实的。只有另寻他经。

上面的第二种方案中提供一个很好思路，用标记来标注。我们只有寻求内存占用更小的数据类型来标记了，1int=4byte，1byte = 8bit

如果我们用bit来打标记。就不可以很好的缩小内存占用了嘛。1int=4byte，如果用bit那么内存占用就会缩小32倍，1144/32大概36m就可以了。

也就是说其实我们的一个int位置，可以表示32个数据存在与否。

Int 1的二进制完整表示：0000 0000 0000 0000 0000 0000 0000 0001，它是有32位，只不过平时前面的0都是没有显示的

我们声明一个int类型的标记数组：flag[2亿/32 +1]，数组长度2亿/32 +1，就可以了，为什么是2亿/32，不是3亿呢，因为这3亿个数的范围就是0-2亿，所以我们的标记数组最大只需要对应2亿即可。有的数，就将其标记为1。就是说数组的没一个元素其实包含了32个数存在与否。

Flag[0] --->0-31

Flag[1] --->32-63

Flag[2] --->64-95

Flag[3] --->96-127

.......

我们怎么来操作这个int类型里面的32位呢，这就要用到我们的位运算：

<<：左移

>>：右移

&：同位上的两个数都是1则位1，否则为0

|：同为上的两个数只要有一个为1 则为1，否则为0

我们怎么找到某个数的标记在数组的索引及其值的多少位呢？

假设3这个数

Index = 3 / 32 = 0

Location = 3 % 32 = 3

3的标记应该在flag[0] 的第三个位置，将其置为1：

flag[0]  |=  1 << Location (位或是不会影响其他位置1的标记)

原本的flag[0]  0000 0000 0000 0000 0000 0000 0000 0011    原本已经有了0和1

　　　　　|    0000 0000 0000 0000 0000 0000 0000 1000    1 << Location 之后的

得到：           0000 0000 0000 0000 0000 0000 0000 1011    现在有0,1,3了

这样就可以所有的数据标记给保存下来了。

那么判断的时候怎么判断呢。

同理先找到某个数精确位置

还是3

Index = 3 / 32 = 0

Location = 3 % 32 = 3

现在我们的flag[0] -> 0000 0000 0000 0000 0000 0000 0000 1011

Exist = flag[0] & (1 << Location) != 0  &：相同位上的两个数都是1则位1，否则为0

　　0000 0000 0000 0000 0000 0000 0000 1011

& 　0000 0000 0000 0000 0000 0000 0000 1000

 　  0000 0000 0000 0000 0000 0000 0000 1000

&运算之后结果不为0说明该数存在。

大致的思路就是这个样子，下面用代码实现上述逻辑

package com.nijunyang.algorithm.math;

/**
 * Description:
 * Created by nijunyang on 2020/5/5 22:33
 */
public class BitMap {
    /**
     * 范围中最大的那个数
     */
    private int max;

    private int[] flag;

    public BitMap(int max) {
        this.max = max;
        flag = new int[max >> 5 + 1]; //除以32也可以表示为>>5
    }

    /**
     * 添加数据标记
     * @param val
     */
    public void put(int val) {        //往bitmap里面添加数字

        int index = val / 32;        // 计算数组索引位置
        int location = val % 32;    // 计算在32位int中的位置
        flag[index] |= 1 << location;   //标记位改成1
    }

    /**
     * 判断是否存在
     * @param val
     * @return
     */
    public boolean exist(int val) {
        int index = val / 32;
        int location = val % 32;

        int result = flag[index] & (1 << location);
        return result != 0;
    }

    /**
     * 移除标记
     * @param val
     * @return
     */
    public void remove(int val) {
        int index = val / 32;
        int location = val % 32;

        System.out.println(Integer.toBinaryString(flag[index]));
        flag[index] = flag[index] &~ (1 << location); //~取反1变0 0变1
        System.out.println(Integer.toBinaryString(flag[index]));
    }

    public static void main(String[] args) {
        BitMap bitMap = new BitMap(200_000_000);
        bitMap.put(128);
        bitMap.put(129);
        System.out.println(bitMap.exist(127));
        System.out.println(bitMap.exist(128));
        bitMap.remove(128);
        System.out.println(bitMap.exist(128));

    }
}

虽然说用bitMap的这种思想可以解决上面的这个问题，但是它还是有缺点的，我们上面用的数字，如果是其他类型可能就需要hash之后得到hashcode再进行这个操作，对于hash冲突是无法解决的。因为标记只有0和1。数据量少的时候相对于普通的hash集合操作并没有优势。它对于那种数据量很大，且数据相对密集的，因为数组的长度是和最大的数据值有关，而不是和集合容量有关。

布隆过滤器就使用bitMap的思想。不过它同时会使用集中hash算法来计算hashcode，来尽量解决hash冲突。Redis缓存设计与性能优化 中有简单的介绍。

JDK中也有一个BitSet类。