BitMap--解决海量数据

系统管理员 2022-06-07 23:09 207阅读 0赞

### 一、概述 ###

本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景，例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说BitMap的特点已经在各个场景的使用性。

### 二、Bit-Map算法 ###

先看看这样的一个场景：给一台普通PC，2G内存，要求处理一个包含40亿个不重复并且没有排过序的无符号的int整数，给出一个整数，问如果快速地判断这个整数是否在文件40亿个数据当中？

#### 1、问题思考： ####

40亿个int占（40亿\*4）/1024/1024/1024 大概为14.9G左右，很明显内存只有2G，放不下，因此不可能将这40亿数据放到内存中计算。要快速的解决这个问题最好的方案就是将数据搁内存了，所以现在的问题就在如何在2G内存空间以内存储着40亿整数。一个int整数在java中是占4个字节的即要32bit位，如果能够用一个bit位来标识一个int整数那么存储空间将大大减少，算一下40亿个int需要的内存空间为40亿/8/1024/1024大概为476.83 mb，这样的话我们完全可以将这40亿个int数放到内存中进行处理。

#### 2、具体思路： ####

1个int占4字节即4\*8=32位，那么我们只需要申请一个int数组长度为 int tmp\[1+N/32\]即可存储完这些数据，其中N代表要进行查找的总数，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:  
tmp\[0\]:可表示0~31  
tmp\[1\]:可表示32~63  
tmp\[2\]可表示64~95  
…….  
那么接下来就看看十进制数如何转换为对应的bit位：  
假设这40亿int数据为：6,3,8,32,36,……，那么具体的BitMap表示为：  
其中0位置为0，1位置为下标1；  
![这里写图片描述][SouthEast]  
**如何判断int数字在tmp数组的哪个下标？**  
这个其实可以通过直接除以32取整数部分，例如：整数8除以32取整等于0，那么8就在tmp\[0\]上。另外，我们如何知道了8在tmp\[0\]中的32个位中的哪个位，这种情况直接mod上32就ok，又如整数8，在tmp\[0\]中的第8 mod上32等于8，那么整数8就在tmp\[0\]中的第八个bit位（从右边数起）。

### 三、算法实现（java） ###

public class BitMapTest { 
        /* * int 32位可以存取 1位符号位，所以就只有31位可以使用 * */
        static class BitMap {
            int[] record;
    
            public BitMap() {
                record = new int[10];
            }
    
            public BitMap(int len) {
                record = new int[len];
            }
    
            /** * 1 位于 0000 0000 0010 2 位于 0000 0000 0100 * * @param value */
            public void set(int value) {
                int loc = indexInRecord(value);
                int intloc = indexInInt(value);
                // System.out.println(loc + " " + intloc);
                if (intloc == 0) {
                    intloc = 1;
                } else {
                    intloc = 1 << intloc;
                }
                record[loc] |= intloc; // 或运算避免多个值相等的情况
            }
    
            /** * 获取该元素所在位置 * * @param value */
            public boolean get(int value) {
                int loc = indexInRecord(value);
                int intloc = indexInInt(value);
    
                if (intloc == 0) {
                    return (record[loc] & 1) != 0;
                }
                if (intloc == 31) {
                    return (record[loc] & 1 << 31) != 0;
                }
    
                return (record[loc] & 1 << intloc) != 0;
            }
    
            /*** * 第几个int value/32== value>>5 (32=2^5) * * @param value * @return */
            private int indexInRecord(int value) {
                return value >> 5;
            }
    
            /** * 计算recor[i] 的初始数值的大小 比如 record[0]=0 record[1]=32 * * @param i * @return */
            private int indexInRecordValue(int i) {
                return i << 5;
            }
    
            /** * value%31 ==value&(32-1) 具体思想见hashmap的indexFor * * @param value * @return 在int的哪个位置 */
            private int indexInInt(int value) {
                return value & 31;
            }
    
            public void print() {
                for (int i = 0; i < record.length; i++) {
                    for (int j = 0; j < 32; j++) {
                        int num = j + (i << 5);
                        // System.out.println(num);
                        if (get(num)) {
                            System.out.print(num + " ");
                        }
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            BitMap bm = new BitMap();
            // 边界值测试
            bm.set(31);
            System.out.println(bm.get(31));
            assert (bm.get(31));
            bm.set(32);
            assert (bm.get(32));
            System.out.println(bm.get(32));
            bm.set(0);
            assert (bm.get(0));
            System.out.println(bm.get(0));
    
            for (int i = 0; i < 35; i++) {
                bm.set(i);
                bm.set(i);
                System.out.println(Integer.toBinaryString(bm.record[i >> 5]));
            }
            System.out.println(bm.get(32));
            for (int i = 0; i < 35; i++) {
                System.out.println(bm.get(i));
            }
            // 排序测试
            bm.set(48);
            assert (bm.get(48));
            bm.set(69);
            bm.set(169);
            bm.set(77);
            bm.print();
        }
    }

运行结果如下：  
我在最开始添加了31 ，所以最左边是1000。。。1,代码没有进行过多的异常检查，但对边界值进行了判断基本保证了程序的正确性（ps：懒不想再写了）  
![这里写图片描述][SouthEast 1]

我在eclipse的运行图标→的run configuration 的vm参数中添加了断言，用于检查代码错误。  
![这里写图片描述][SouthEast 2]

### 四、算法分析与应用 ###

#### (1)在3亿个整数中找出不重复的整数，限制内存不足以容纳3亿个整数。 ####

对于这种场景我可以采用2-BitMap来解决，即为每个整数分配2bit，用不同的0、1组合来标识特殊意思，如00表示此整数没有出现过，01表示出现一次，11表示出现过多次，就可以找出重复的整数了，其需要的内存空间是正常BitMap的2倍，为：3亿\*2/8/1024/1024=71.5MB。  
具体的过程如下：  
扫描着3亿个整数，组BitMap，先查看BitMap中的对应位置，如果00则变成01，是01则变成11，是11则保持不变，当将3亿个整数扫描完之后也就是说整个BitMap已经组装完毕。最后查看BitMap将对应位为11的整数输出即可。

#### (2)对**没有重复元素**的整数进行排序。 ####

对于非重复的整数排序BitMap有着天然的优势，它只需要将给出的无重复整数扫描完毕，组装成为BitMap之后，那么直接遍历一遍Bit区域就可以达到排序效果了。  
举个例子：对整数4、3、1、7、6进行排序

参考链接[理论部分][Link 1]  
[http://zengzhaozheng.blog.51cto.com/8219051/1404108][Link 1]

[SouthEast]: /images/20220608/d568b55177fd4e88a81bcb556d34bbf9.png
[SouthEast 1]: /images/20220608/b91ee098d4354e60badd265703ce39ed.png
[SouthEast 2]: /images/20220608/65c719935132488985993c3ef0c50202.png
[Link 1]: http://zengzhaozheng.blog.51cto.com/8219051/1404108