Algorithms_算法专项_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

/**
     * 初始化数据
     *
     * 其实用啥和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优缺点总结

优点

1. BitMap的时间复杂度是O(1)， 高效
2. 占用内存少 ，空间复杂度

缺点

1. 数据最好不要重复。因为只用0和1表示 ， 如果重复，无法知道这个数字有多少个，只能知道这个数字存在。 比如有3个6666，每一次add都能成功，但是无法知道有几个6666. 如果你的需求是统计存不存在，那可以重复，你如果要统计某个数字出现的次数…
2. 无法处理字符串 。 将字符串映射到 BitMap 的时候会有碰撞的问题，可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
3. 数据稀疏 。 数据量少的情况下相对于普通的hash存储并没有太大的优势，举个例子 比如要存入(3,9877899877,98721124)这三个数据，我们需要建立一个 9999999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，普通的hash或者 Roaring BitMap 来解决。

所以针对存在的缺点，就要布隆过滤器这个神器了，下篇我们探讨下布隆过滤器的原理及使用。

小试牛刀

Q: 某个超大的文件中包含一些手机号码，每个号码为11位数字，求不同号码的个数。

有了上面的处理思路，是不是这个问题也有思路了呢？

每个号码11位， 最大值也就是 11个9呗…so , 懂了吧