BitMap应用：如何在2.5亿个无符号正整数中找出不重复的整数？

发表于 更新于 分类于 阅读次数： 评论数： 本文字数： 2.6k

问题：如何在2.5亿个无符号正整数中找出不重复的整数，内存不足以容纳这2.5亿个整数

解法：采用BitMap，每个整数分配2个bit

00 => 0 表示没出现过

01 => 1 表示出现过1次

10 =>2 表示出现过多次

11 =>3 表示无效数据。

  • 内存分析

每个无符号整数的取值范围为0~2^32-1，BitMap空间复杂度取决于MAX_VALUE，因此需要一个长度为2 ^ 32的BitMap，总占用空间为2^32 * 2bit = 1 GB。

使用Java程序进行实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.util.*;

public class BitMapTest {

    /**
     * ---
     * 00 没出现过
     * 01 出现过1次
     * 10 出现过多次
     * 11 无效表示
     * ---
     * 1 byte = 8 bit，可分配四个数字，长度为1000可覆盖4000个数字，因此我们设置输入整数不超过4000
     * 真实情况下该数组的长度应该为 2.5亿/4，才能覆盖所有无符号整数，此处测试用较小数字进行
     * flags默认初始值都为0
     * |00 00 00 00|    |3 2 1 0| flag[0] 例如：10000100 表示3出现过多次, 2, 0都没有出现过，1出现过一次
     * |00 00 00 00|    |7 6 5 4| flag[1]
     */
    static byte[] flags = new byte[1000];

    public static void main(String[] args) {
        int[] nums = new int[2000];  // 2000个测试输入数据
        // 验证结果的正确性
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        Random random = new Random();
        System.out.println("原始数据：");
        for (int i = 0; i < nums.length; i++) {
            // 填充随机数输入进行验证
            int num = random.nextInt(flags.length * 4);  // flags长度为1000，整数最大只能为4000
            nums[i] = num;
            System.out.print(num + " ");
            map.put(num, map.getOrDefault(num, 0) + 1);
            setVal(num);
        }
        System.out.println();
        System.out.println("-------------------");
        List<Integer> bitMapAns = new ArrayList<>();
        List<Integer> hashMapAns = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (getVal(nums[i]) == 1) {
                bitMapAns.add(nums[i]);
            }
            if (map.getOrDefault(nums[i], 0) == 1) {
                hashMapAns.add(nums[i]);
            }
        }
        System.out.println("只出现过一次的数据：");
        System.out.println(bitMapAns);
        System.out.println("bitMapAns 是否和 hashMapAns相同：" + bitMapAns.equals(hashMapAns));
    }

    public static void setVal(int idx) {
        int val = getVal(idx);
        if (val >= 2) {
            // 11 或 10 表示出现过多次，保持不变即可
            return;
        }
        int pos = idx / 4;  // 确定在flags中的位置
        int loc = idx % 4;  // 确定在一个byte中的位置
        /*
        假设flags[0] = 0b10010100
        |00 00 00 00|    |3 2 1 0|
        idx = 2  => pos = 2/4 = 0;  loc = 2%4 = 2
        ~(3<<loc) => 11001111 即让2bit对应位置为0，其他都为1
        (flags[pos] & ~(3<<loc)) => 效果就是让2bit对应位置置为00，其他为保持不变
        | ((val + 1) << loc) => 效果就是让val+1的值填充2bit的位置
         */
        int newVal = (flags[pos] & ~(3 << (loc * 2))) | ((val + 1) << (loc * 2));
        flags[pos] = (byte) newVal;
    }

    public static int getVal(int idx) {
        int pos = idx / 4;  // 确定在flags中的位置
        int loc = idx % 4;  // 确定在一个byte中的位置
        /*
        假设flags[0] = 0b10010100
        |00 00 00 00|    |3 2 1 0|
        idx = 2  => pos = 2/4 = 0;  loc = 2%4 = 2
        flags[pos] >> (loc * 2)  => 00001001  (左边自动补0) 这个操作的效果是让2这个整数在bitmap中对应的两个bit移动到最右端
        拿上面的结果  (0b00001001) & (byte)3  => (0b00001001) & (0b00000011) => (0b00000001) 即可得到目标的两个bit对应的数字
         */
        int val = (flags[pos] >> (loc * 2)) & (byte) 3;
        return val;
    }

}

运行结果：

上述通过HashMap的方案可以检验BitMap的答案是正确的，并且成功节省了内存空间。

相关文章