问题：
假设有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类。
