引导案例
Q: 如何在3亿个整数， 每个整数的范围是 0到2亿，判断一个数是否存在于3亿个整数中。 要求内存使用在100M以内，一台主机。
…
思考下…
数组？ hash ? 分治？ bitmap ? 布隆过滤器 ？
用数组的话 ， 开辟个data[2亿]长度的数组， data[1]=1 表示存在，data[2]=0表示不存在。 理论上可行，但是内存肯定超过了500M， 不可行
用hash的话，开3亿个空间， 举个例子 使用HashMap --> put(1,true) , get(1)为true，则存在， 听起来也可行哈，但是3亿个int类型 内存也是绝对会超过500M的。
分治： 内存要求也不满足
bitmap ? 布隆过滤器？ 这两个是可以的
我们这里先用bitmap来解决这个问题
基础知识回顾
Bitmap
计算不同存储类型需要开辟的内存空间
在计算机科学中，bit通常用于表示信息的最小单位，也可以被称作是二进制位。
在计算机学科中，bit一般用0和1表示。
Byte也就是人们常说的字节，通常由8个位（8bit）组成一个字节(1Byte)
比如我们常见的基本类型的取值范围
bit与Byte之间可以进行换算，具体的换算关系为：1Byte=8bit
计算下3亿数据需要开辟的内存空间：
- 如果使用 int数组来存储， 那就需要3亿个int , 1个int占用4个Byte字节 ， 故3亿个int 占用的内存空间为
3亿 * 4 （总共占用的Byte） / 1024 (转为KB) / 1024 (转为MB) = 1144 MB - 如果使用 bit数组来存储，那么同样也需要3亿个bit, 8个bit才等于 1个Byte字节， 故3亿个bit 占用内存空间为
3亿/8 (总共占用的Byte) / 1024 (转为KB) / 1024 (转为MB) = 35.7 MB - 当然了 你也可以用long 或者 short来存储，无非就是计算的时候的转换关系调整下 。 如果使用 long 数组来存储， 那就需要3亿个long , 1个long 占用8个Byte字节 ， 故3亿个long占用的内存空间为
3亿 * 8 （总共占用的Byte） / 1024 (转为KB) / 1024 (转为MB) = 2288 MB。 - 如果使用 short数组来存储， 那就需要3亿个short, 1个short占用2个Byte字节 ， 故3亿个short占用的内存空间为
3亿 * 2（总共占用的Byte） / 1024 (转为KB) / 1024 (转为MB) = 572MB。 - 其他类型也可以，主要是需要开辟的内存大小，当然是越小越好了…
结论显而易见，使用二进制bit来存储 3亿个数，比使用int来存储3亿个数 需要开辟的内存空间从1个G 降低为 36M， 少了30倍 ,你说它不香吗？？？
原理
bitmap就是利用一个 bit 二进制位（0,1）来存储。由于采用bit为单位来存储数据，可以大大的节省存储空间。
OK , 计算完了需要开辟的内存空间，如果使用bit来存储这些数据，该如何表示呢？
我们知道bit 二进制位，在计算机学科中，bit一般用0和1表示。
每一个bit位表示一个数，0表示不存在，1表示存在，这正符合bit二进制。 举个例子我们要存储 {1,2,4,6}
我们需要用bit来 存储，java.util包中有个专门存储bit的类 BitSet
当然了，我们也可以用其他类型来表示bit . 接下来我们以int为例 （当然了 你用byte , short ,long 都可以…）
计算需要开辟多大长度的数组
比如我们使用int来表示bit , 1个int = 4 个Byte = 4 * 8 bit . 因此一个int可以存储32个int
假设有 65个数字(0~64)，最大数字为64 。 用bit表示，肯定需要64bit ,如果用int来表示，需要几个int呢 ？
我们来计算下
-----> 需要3个int，才能把这65个bit 存下来。
-----> 65个数字 需要3个int (64/32 +1) , 97个数字 需要4个int (96/32+1) … 【从0开始计算，最大值 64 ，96】
-----> 推到出来一个公式来根据存储的bit数量计算(取数据的最大值）需要几个int
故需要开辟的int数组的容量为 (MAX/32 + 1) , 一定要注意的是 一定要取MAX来计算。 至于为啥子除以32 ， 1 int = 4 Byte = 4 * 8 bit ,通过转换计算来的。 看到MAX/32 这种 ，应该马上想到 右移 2^5次方 这种高效的计算方式。 即 （MAX >> 5 + 1 ）
找到目标数字在数组中的下标
确定了需要开辟几个int数组，假设我们要把64这个值存储到bit中（当然了，存到bit里肯定不是64 ,bit二进制位 存0 1。 1 表示存在，0 表示不存在）
是不是得找到这个具体的位置 ？
----> 是不是需要先定位到数组中的哪个int ， 比如 64 在 int[2],先找到 int[2]
----> 64~95 在 int[2] , 32~63 在int[1] , 96-127 在int[4]
—> 推到出来一个公式来 找到目标数字在数组中的下标 n / 32 ，同样的 ，通过位移的方式更高效 n/32 —> n/2^5 --> n >> 5
找到目标数字在对应数组下标中的位置
----> 然后再看下 这个int存储了32位，那我这个目标值应该在第几个位置 ，显而易见，我们的64在第一个位置。
----> 64 在 int[2] 的 第1位，即下标为0的位置， 65呢 下标为1的位置 ，70 呢 下标为6
—> 推到出来一个公式来 找到目标数字在在对应数组下标中的位置 ，取余即可 n %32 ，（因为除数32位2^5）所以 ，通过位移的方式更高效 n%32 —> n%2^5 --> n &（2^5-1） —> n & 31
总结下3个步骤
1. 计算需要开辟多大长度的数组 ：（MAX >> 5 + 1 ）
2. 找到目标数字在数组中的下标 ： n >> 5
3. 找到目标数字在对应数组下标中的位置 ： n & 31
注意： 计算需要开辟多大长度的数组，一定要取最大值计算，假设你要存3亿个数据
—> 根据公式 需要开辟的数组长度为： 3亿/32 + 1 = 9375001（9百30多万） 。
(1个int 占4个字节，9375001 * 4 （总字节大小） /1024 /1024 = 35.76MB)
存
存的本质就是将下标为pos的位由0变为1---->那就把1左移pos位，然后使用或运算符运算即可 （按位或运算【|】有一个为1时，结果位就为1）
举个例子 pos = 2 , pos 2原本的bit值是 0 （其实不管是0 ，还是1）
–> 0 | 1 --> 1
–> 1 | 1 --> 1
/** * 初始化数据 * * 其实用啥和1进行或运算都行，这里使用bitsArray[index(n)] * @return */ public boolean add(int n) { // 或运算 return (bitsArray[index(n)] |= 1 << position(n)) != 0; }
判断是否存在
public boolean find(int n) { // bitMap构建的时候，根据max来构建的，如果入参n>max，直接返回不存在 if (n > max) return false; return (bitsArray[index(n)] &= 1<<position(n)) != 0; }
假设黄色的二进制位1存储的是数字n,要想判断n是否存在
第一步： 找到n所在的数组下标
第二步： 在第一步确定的那个数组下标对应的int里（假设我们是用int来存储bit,32个bit), 确定这个n具体在哪个position，
第三步：把1 左移 position个位置，然后和目标的二进制bit位，进行 与运算. 只有都为1，才说明存在。 如果目标的二进制bit位是0，0&1=0 ，说明这个位置没有被add过，也就不存在。
注： add的时候，用的是bitsArray[index(n)] |= 1 << position(n) ，所以add完成以后bitsArray[index(n)]就有值了，所以这里继续使用bitsArray[index(n)]进行 &运算
删除
删除无非就是把 1置为 0 。
将1左移position后，因为存在，那个位置自然就是1，然后取反就是0，再与当前值做&，即可清除当前的位置了
/** * * @param n * @return */ public boolean del(int n) { // 不存在 返回删除失败 if (!find(n)) return false; // 将1左移position后，因为存在，那个位置自然就是1，然后取反就是0， // 再与当前值做&，即可清除当前的位置了. return (bitsArray[index(n)] &= ~(1<<position(n))) == 0 ; }
代码
/** * @author 小工匠 * @version v1.0 * @create 2019-12-20 6:47 * @motto show me the code ,change the word * @blog https://artisan.blog.csdn.net/ * @description **/ public class ArtisanBitMap { // 这批数据的最大值，用于确定需要开辟的数组长度 private int max; // 数据映射到bit位上，这里用int表示的bit ，1个int占4个字节即4*1Byte = 4*8bit = 32bit private int[] bitsArray; /** * 构造函数 * * @param max */ public ArtisanBitMap(int max) { this.max = max; // 构建int数组，用于存储bit // (max >> 5) 一定要加括号，因为 +号的优先级比>>高 bitsArray = new int[(max >> 5) + 1]; } /** * 初始化数据 * * 其实用啥和1进行或运算都行，这里使用bitsArray[index(n)] * @return */ public boolean add(int n) { // 或运算 return (bitsArray[index(n)] |= 1 << position(n)) != 0; } public boolean find(int n) { // bitMap构建的时候，根据max来构建的，如果入参n>max，直接返回不存在 if (n > max) return false; return (bitsArray[index(n)] &= 1<<position(n)) != 0; } /** * * @param n * @return */ public boolean del(int n) { // 不存在 返回删除失败 if (!find(n)) return false; // 将1左移position后，因为存在，那个位置自然就是1，然后取反就是0， // 再与当前值做&，即可清除当前的位置了. return (bitsArray[index(n)] &= ~(1<<position(n))) == 0 ; } /** * 根据n 判断n所在的数组下标 * * @param n * @return */ public int index(int n) { // n/32 --> n 除以 32 （2^5） ，可以表示为 n向右移5位 return n >> 5; } /** * 根据n 判断n所在数组下标对应的存储位置 * 即：数组中的一个int可以存储32位，判断这个n需要存储在哪一位 * * @param n * @return */ public int position(int n) { // n%32 --> n 取余32 （2^5） ，可以表示为 n &(2^5 -1) return n & 31; } public static void main(String[] args) { // 最大是65 ArtisanBitMap bitMap = new ArtisanBitMap(300000000); bitMap.add(2); bitMap.add(300000000); // 判断是否存在 boolean a = bitMap.find(2); System.out.println("2是否存在: " + a); boolean b = bitMap.find(300000000); System.out.println("300000000是否存在: " + b); // 删除操作 boolean delete = bitMap.del(2); System.out.println("2是否删除成功: " + delete); System.out.println("2是否存在: " + bitMap.find(2)); } }
测试
bitmap优缺点总结
优点
- BitMap的时间复杂度是O(1)， 高效
- 占用内存少 ，空间复杂度
缺点
- 数据最好不要重复。因为只用0和1表示 ， 如果重复，无法知道这个数字有多少个，只能知道这个数字存在。 比如有3个6666，每一次add都能成功，但是无法知道有几个6666. 如果你的需求是统计存不存在，那可以重复，你如果要统计某个数字出现的次数…
- 无法处理字符串 。 将字符串映射到 BitMap 的时候会有碰撞的问题，可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
- 数据稀疏 。 数据量少的情况下相对于普通的hash存储并没有太大的优势，举个例子 比如要存入(3,9877899877,98721124)这三个数据，我们需要建立一个 9999999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，普通的hash或者 Roaring BitMap 来解决。
所以针对存在的缺点，就要布隆过滤器这个神器了，下篇我们探讨下布隆过滤器的原理及使用。
小试牛刀
Q: 某个超大的文件中包含一些手机号码，每个号码为11位数字，求不同号码的个数。
有了上面的处理思路，是不是这个问题也有思路了呢？
每个号码11位， 最大值也就是 11个9呗…so , 懂了吧
