小知识

  1. 在实际项目中，我们经常需要聚合统计，比如统计一个年龄在20-30，喜欢看技术书籍，喜欢听音乐，喜欢宅在家的程序员等等一系列标签的用户。 如果使用mysql求并集，首先语句随着标签变长而变长，其次聚合，分组，去重严重影响语句性能。这种情况如何解决？
  2. 比如现在比较火的面试题，在10亿整数中找出100个重复的数，或者任意给定一个整数，判断是否在这个10亿数中。

bitMap原理

bitMap就是使用bit位来标记元素，key为该元素，value一般为0或者1，大大节省存储空间.

现在有(2, 3, 4, 5，7)5个数，任意给定一个在0-7范围内的数字，判断是否在此集合中：

image-20211214225035132

  • 创建一个范围为(0-7)的Byte类型数组，将集合数字对应数组的bit位置置1；

  • 然后遍历该Byte数组，如果Byte数组位置为1即代表该数存在。

  • 同理对于10亿整数也可以这样处理，一个int型数字4个字节，32bit，如果使用bit标记正整数，就可以节省32倍的内存空间。

  • 10亿数字，40亿字节，320亿bit，需要大约4g内存，使用bitMap标记，只需要125M内存空间即可存储，大大节省内存空间。

以上和桶排序排序的思想非常相似。

bitMap实际运用

对于1千万数据，判断任意给定的数是否在其中？
分治思想
使用int数组作为bitMap。
将数组分成32组，每组内有(0-31)个位置，如果给定数组在指定数组中的bit是0，则不存在。

  1. 求十进制数在对应数组a中的下标
    a[i] = a[N/32]
  2. 求int[]中bit位置
    index = a[i] % 32

上述两个运算可以改成位运算，因为位运算的效率非常高，占用cpu的时钟周期非常少。
结论：对于2的倍数，%2^n = &(2^n-1),模运算等于与预算，例：a % 16 = a & 15,这里的15做与运算时需要化成16进制，即0x0F.

在10000000个范围为[1-100000]数中，给定指定一个数，判断是否在这个集合中

代码

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
public class BitMapActual {
    //1千万数据集合
    private static final int N = 10000000;

    //bitmap数组
    private static int[] a = new int[N/32 + 1]; //int 等于32个bit 所以数据长度为(N/32+1)

    /**
     * 为集合数据加标记
     * @param n
     */
    public static void addValue(int n) {
        //定位数组编号 相当于n/32
        int row = n >> 5;

        //定位数组内slot位置 相当于n%32
        int offset = n & 0x1F;

        //数组slot置1
        a[row] |= 1 << offset;
    }

    /**
     * 判断给定数字是否存在
     * @param n
     * @return
     */
    public static boolean exits(int n) {
        //定位数组编号
        int row = n >> 5;

        //定位数组内slot位置
        int offset = n & 0x1F;

        // 1 << position 将a[i]中左移position求与,slot位置有值返回true
        return (a[row] & ( 1 << offset)) != 0;
    }

    public static void main(String[] args) {
        //初始化一个长度为N的数组
        int num[] = new int[N];
        Random random = new Random();
        for (int i = 0; i < N; i++) {
            //随机数范围是(0-100000)
            int item = random.nextInt(100000);
            num[i] = item;
        }

        BitMapActual map = new BitMapActual();
        //置1
        for(int i = 0; i < N; i++){
            map.addValue(num[i]);
        }

        int temp = 200;
        if(map.exits(temp)){
            System.out.println("temp:" + temp + "has already exists");
        } else {
            System.out.println("temp:" + temp + "has no exists");
        }
    }
}