算法通关村第十五关青铜挑战——使用位存储 处理海量数据问题之用4KB内存寻找重复元素

关注微信公众号：怒码少年。回复关键词【电子书】，领取多本计算机相关电子书
公众号后台开启了咨询业务，欢迎大家向我提问，免费，为爱发电😎

大家好，我是怒码少年小码。

之前我们所讲的文章中的例题都是建立在十几或几十的数据量上，但是如果将数据量提高到百万甚至十几亿😱，那处理逻辑就会发生很大差异。

处理海量数据问题的常见方法

在海量数据中，此时普通的数组、链表、Hash、树等等结构有无效了，因为内存空间放不下了。而常规的递归、排序，回溯、贪心和动态规划等思想也无效了，因为执行都会超时。

这类问题该如何下手呢🤔？这里介绍三种非常典型的思路：

1. 位存储。位存储最大的好处是占用的空间是简单存整数的1/8。例如一个40亿的整数数组，用整数存储需要16GB左右的空间，而用位存储，就可用0.5GB的空间，这样很多问题就解决了。
2. 如果文件太大 ，无法在内存中放下，则需要将大文件分成若干小块，先处理每个块，最后再逐步得到想要的结果，这种方式也叫做外部排序。这需要遍历全部序列至少两次，是典型的用时间换空间。
3. 堆。在超大数据中找第K大、第K小，K个最大、K个最小，很适合使用堆来做。将超大数据换成流数据也可以，口诀就是“查小用大堆，查大用小堆”。（这个方法我们在第十四关讲堆的时候提到过：）

本篇会首先介绍如何使用位存储解决海量数据问题，剩下的两种方法我们会在接下来的文章中一一讲解，如果不想错过的化，欢迎点个关注😎。

接下来我们以一道题为切入点：

用4KB内存寻找重复元素

给定一个数组，包含从1到N的整数，N最大为32000，数组可能还有重复值，且N的取值不定，若只有4KB的内存可用，则如何打印数组中所有重复元素。

分析：这是一道海量数据的热身题，如果去掉“只有4KB”的要求，可以先创建一个大小为N的数组，然后将这些数据放进来，但是整数最大为32000.如果直接采用数组存，则需要32000*4B = 128KB的问题

如果只有4KB的空间，那么只能寻址842^10个比特，这个值比32000要大，因此可以创建32000比特的位向量（比特数组），其中一个比特位置就代表一个整数利用这个位向量，就可以遍历整个数组

如果发现数组元素是v，那么就将位置为v的设置为1，碰到重复元素，就输出一下

pubilc class FindDuplicateIn32000 {
    // 将数用位存储到比特数组并查看是否有重复
    public void checkDuplicates (int[] array){
        // 创建大小为32000 < 4KB 的比特数组
        BitSet bs = new BitSet(32000);
        for (int i = 0; i < array.length; i++){
            int num = array[i]; // 要存储的数
            int num0 = num - 1; // 要存储的位置索引
            if (bs.get(num0)) {
                System.out.println(num); // 若该元素已经存在，这说明是重复的元素，打印
            } else {
                bs.set(num0); // 若不存在则将改为设为1以存储该元素
            }
        }
    }
    // 定义比特数组
    class BitSet {
        int[] bitset;
        public BitSet(int size){
            this.bitset = new int[size >> 5];
        }
        // 判断数组中是否有重复元素
        boolean get(int pos) {
            int wordNumber = (pos >> 5); // 除以32  --- 数大小
            int bitNumber = (pos & 0×1F); // 除于32 --- 存储的位位置
            // 查看对应位位置上是否为1，即存在该元素
            return (bitset[wordNumber] & (1 << bitNumber)) != 0;
        }
        // 将该位设为1
        void set(int pos){
            int wordNumber = (pos >> 5); // 除以32 --- 数大小
            int bitNumber = (pos & 0×1F); // 除于32 --- 存储的位位置
            // 若不存在则将对应位赋为1
            bitset[wordNumber] |= 1 << bitNumber;
        }
    }
}
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

使用 size >> 5 进行右移操作是为了将 size 除以 32。原因是 int 类型在 Java 中占据 32 位，每个 int 变量可以表示 32 个位。

由于 BitSet 是用来表示位状态的数据结构，每个位需要一个整数来表示。因此，>> 5是为了确定需要多少个整数来表示 size 个位。其他的>> 5也有类似的作用。

int num0 = num - 1; 的作用是将数组中的元素 num 减 1，得到 num0。

这是因为 bitset 的索引从 0 开始，而数组 array 中的元素取值范围从 1 开始。为了将数组元素与 bitset 中的索引对应起来，需要将数组中的元素减 1，确保 bitset 的索引和数组元素的值是一一对应的关系。

例如，假设 array[i] 的值为 5，而 bitset 的索引从 0 开始。如果直接将 array[i] 的值作为 bitset 的索引，会将位图中的索引 5 的位设置为 1，而实际上应该是将索引 4 的位设置为 1。因此，通过将 array[i] 减 1，可以将数组中的元素与 bitset 中的索引正确地对应起来。

int bitNumber = (pos & 0x1F); 是将 pos 与 0x1F 进行按位与运算，并将结果赋值给 bitNumber。

0x1F 的十六进制表示是 0b0001_1111，也就是二进制的 31。按位与运算的规则是将两个数的对应位进行逻辑与运算，结果为 1 的位保留，结果为 0 的位清零。

在这里，使用 0x1F 进行按位与运算的目的是提取 pos 的低 5 位，将结果赋值给 bitNumber。这是因为 bitset 中每个存储单元的大小是 32 位（一个 int 的大小），而 bitNumber 表示的是在这个存储单元中，当前位的位置。

通过这个运算，我们可以根据 pos 的值计算出对应在 bitset 中的存储单元和当前位的位置，从而正确地设置或获取相应的位信息。

get(int pos) 它用于获取位图中指定位置 pos 的位状态，返回一个布尔值。

具体分析如下：

1. 首先，根据位图中每个整数表示的位数（32）进行右移运算，得到 pos 除以 32 的商，即 wordNumber。这个商表示在 bitset 数组中的位置索引。

2. 接下来，根据位图中每个整数表示的位数（32）进行按位与运算，得到 pos 除以 32 的余数，即 bitNumber。这个余数表示在该整数的二进制表示中的位置索引，范围在 0 到 31 之间。

3. 使用位运算，将整数 1 左移 bitNumber 位，得到一个只有第 bitNumber 位为 1，其他位为 0 的整数。

4. 对位图数组中的第 wordNumber 个整数执行按位与操作，即 bitset[wordNumber] & (1 << bitNumber)。这将保留 bitset[wordNumber] 中只有第 bitNumber 位为 1，其他位为 0 的部分。

5. 最后，判断上一步得到的结果是否不等于零。如果不等于零，则表示位图的第 pos 位为真（1），返回 true；如果等于零，则表示位图的第 pos 位为假（0），返回 false。

总结起来，这段代码是用来获取位图中指定位置 pos 的位状态（是否为真）。它通过位运算和按位与操作，获取位图数组中指定位置的位，并判断其是否为真，返回对应的布尔值。

END

本篇，包括所有接下来的关于海量数据的题目的重点都是理解如何解决就好，面试问的时候能够将问题描述清楚，不用写代码。这里的代码也是简单演示用的。