Algorithms_算法专项_Bitmap原理及应用
文章目录
- 引导案例
- 基础知识回顾
- Bitmap
- 计算不同存储类型需要开辟的内存空间
- 原理
- 计算需要开辟多大长度的数组
- 找到目标数字在数组中的下标
- 找到目标数字在对应数组下标中的位置
- 总结下3个步骤
- 存
- 判断是否存在
- 删除
- 代码
- 测试
- bitmap优缺点总结
- 优点
- 缺点
- 小试牛刀
引导案例
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来解决这个问题
基础知识回顾
Algorithms_数据结构与算法_位运算符的巧技一二事
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
除数为2的n次方时，使用位操作（&运算）代替求余操作
总结下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
判断是否存在
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 = 32bitprivate 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) {// 最大是65ArtisanBitMap 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优缺点总结
优点
缺点
所以针对存在的缺点，就要布隆过滤器这个神器了，下篇我们探讨下布隆过滤器的原理及使用。
小试牛刀
Q: 某个超大的文件中包含一些手机号码，每个号码为11位数字，求不同号码的个数。
有了上面的处理思路，是不是这个问题也有思路了呢？
每个号码11位， 最大值也就是 11个9呗…so , 懂了吧
总结
以上是生活随笔为你收集整理的Algorithms_算法专项_Bitmap原理及应用的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： Algorithms_算法专项_Hash
- 下一篇： Algorithms_基础数据结构(01