Java 面试题 10 - 海量数据处理算法

大数据处理中的分治思想

1. 哈希映射：如果数据太大，不能全部放入内存中，就可以利用映射函数将每条数据映射到一个小文件中，例如 %1000 可以将大文件映射成 1000 个小文件。相同的数据会出现在同一个文件中。
2. HashMap 统计：将大文件转换为小文件后，就可以利用 HashMap 来统计每个 key 出现的次数。
3. 堆排序/快速排序：根据 HashMap 中的数据，利用堆排序/快速排序，就可以得到频率最高的 key。

问题：统计 1 亿个 IP 地址中出现频率最高的 IP

将大文件映射为小文件，比如使用 IP%1000 将所有 IP 映射到 1000 个小文件中，相同的 IP 会被映射到同一个文件中。然后找出每个小文件中出现频率最高的 IP，那么这 1000 个 IP 中频率最高的那个就是所有 IP 中频率最高的那个。

具体来说，对于一个小文件，使用 HashMap 统计每个 IP 的次数，统计过程中找出频次最高的 IP。

问题：从 300 万个字符串中找出频率最高的 10 个

假设每个字符串占据 255 字节，那么 300 万个字符串一共占据 \(300 * 10000 * 255 /1024/1024/1024 = 0.75GB\)，可以全部放到内存中来处理。所以不再需要将大文件转化为小文件，可以直接使用 HashMap 进行统计，然后使用快排/堆排序找出结果。

1. HashMap 统计：使用 HashMap 保存每个字符串的频次，可以在 \(O(n)\) 时间完成统计。
2. 堆排序：维护一个大小为 10 的小根堆，遍历每个字符串，将它的频次和堆顶元素比较，如果大于堆顶元素的频次，就将堆顶元素删除，将当前字符串加入堆。这样最后堆中元素就是频次最大的 10 个字符串。

问题：有 10 个文件，每个 1G，每个文件的每一行是一个字符串，如何按照出现次数给所有字符串排序？

1. hash 映射：依次读取每个文件，按照 hash(str)%10 的结果将每个字符串写入一个文件，形成另外 10 个文件，和原来的 10 个文件的不同在于，现在 相同的字符串会出现在同一个文件中。如果 hash 函数结果是随机的，那么每个文件的大小也会是 1G。
2. HashMap 统计每个字符串出现的次数。
3. 利用堆排序按照出现次数对字符串排序，将排好序的字符串和对应的次数输出到文件中，形成 10 个排序文件（因为全部排序的话内存装不下）。然后利用外部排序（归并排序）对这 10 个文件进行整体排序。

问题：给定两个文件 a、b，各存放 50 亿个 url，每个 url 占 64 字节，内存限制是 4G，找出两文件的共同 url。

每个文件大小约为 320G，需要分治。首先读取文件 a，对每个 url 求 hash(url)%1000，将每个 url 映射到一个小文件中，且相同的 url 会被放到同一个文件。这样每个小文件大小约为 300M。对文件 b 执行同样的操作。然后求出这 2000 个小文件中的共同 url 即可：

1. 使用 HashSet 对每个小文件去重。

2. 求出 1000 对小文件中的共同 url：

   for fa in all_file_a:
   	for fb in all_file_b:
   		求出 fa 和 fb 中的共同 url
   

问题：在 2.5 亿个 int 数中找出不重复的整数

采用 2-bitmap 方法：00 表示不存在，01表示出现一次，10表示出现多次。即用两位就可以表示一个数的状态。int 型整数占用 4B，一共有 \(2^{32}\) 个不同的数，所以需要使用 \(2^{32}*2b=1GB\) 内存来表示所有 int 整数的状态。

遍历这 2.5 亿个数，查看位图中对应的位，如果是 00，则变为 01，如果是 01，则变为 10，如果是 10，则保持不变。遍历结束后，将 01 对应的所有整数输出即可。

问题：从 5 亿个数中找出中位数

如果数据可以全部放入内存中，那么可以直接排序，时间复杂度为 \(O(nlogn)\)，更好的办法是使用两个堆，一个大根堆一个小根堆，大根堆中最大的数小于等于小根堆中最小的数，且保证两个堆中的元素个数相差不超过 1。如果数据总数为偶数，那么中位数就是这两个堆顶元素的平均值；如果为奇数，中位数就是数据较多的那个堆的堆顶元素。

class MedianFinder {
  private PriorityQueue<Integer> maxHeap;
  private PriorityQueue<Integer> minHeap;
  
  public MedianFinder() {
    maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    minHeap = new PriorityQueue<>(Integer::compareTo);
  }
  
  public void addNum(int num) {
    // 大根堆中的元素都小于小根堆
    if (maxHeap.isEmpty() || maxHeap.peek() > num) {
      maxHeap.offer(num);
    } else {
      minHeap.offer(num);
    }
    // 保证两堆数据个数相差最多一个
    int size1 = maxHeap.size();
    int size2 = minHeap.size();
    if (size1 - size2 > 1) {
      minHeap.offer(maxHeap.poll());
    } else if (size2 - size1 > 1) {
      maxHeap.offer(minHeap.poll());
    }
  }
  
  public double findMedian() {
    int size1 = maxHeap.size();
    int size2 = minHeap.size();
    return size1 == size2
      	? (maxHeap.peek() + minHeap.peek()) * 1.0 / 2
      	: (size1 > size2 ? maxHeap.peek() : minHeap.peek());
  }
}

5 亿个数，每个数字占 4B，那么一共需要 2G 内存，一般来说是可以全部放入内存的。但如果数据量大于可用内存，就需要使用分治法了。

顺序读取这 5 亿个数字，对于读取到的数字 num，如果它对应的二进制中最高位为 1（说明是负数），则把这个数字写到 f1 中，否则写入 f0 中。通过这一步，可以把这 5 亿个数划分为两部分，而且 f0 中的数都大于 f1 中的数。

如果划分后两个文件中的数据有相同个数，那么中位数就是数据较小的文件中的最大值与数据较大的文件中的最小值的平均值。

如果划分后个数不同，则中位数在那个数据较多的文件中。假设 f1 中有 1 亿个数，那么中位数就是 f0 中从第 1.5 亿个数开始的两个数求得的平均值。对于 f0 可以用次高位的二进制继续将文件一分为二，如此划分下去，直到划分后的文件可以被加载到内存中，把数据加载到内存中以后直接排序，找出中位数。