2G 内存在 20 亿个整数中找出现次数最多的数

• 案例分析：
  • 整数占用 4个字节。
  • 整数的范围是 -21亿 ~ 21亿。
  • kv 对需要 8个字节，k 存储整数，v 存储出现次数。
  • 存储 20亿个整数需要 16G内存。
• 数据存储使用散列表。
• 分治：
  • 要将一个大文件拆分成若干个小文件。
    • 同一个数字不能分布在多个文件中。
    • 20亿个整数能够均衡分布在多个文件中。
    • 通过 hash 运算实现。
      • 因为同一个数字经过运算会得到相同的值，可用于数据分流
      • hash 算法具备随机性 → 将大文件中的数据均衡分布在多个小文件中；siphash → 近似的 key 通过哈希函数会得到反差很大的值。
    • 建议拆分为 16个文件，这样每个文件大体上需要占用 1G内存。
      • 考虑 hash 不均衡的情况。
      • 考虑散列表扩容的情况。
      • 为了优化取余运算，要找一个恰好大于 10 的 $2^n$，即 $2^4$。
        • x % 16 = x & (16 - 1)
  • 分别统计单个文件中的最大值，最终得到整体的最大值。
• 优化：如果某个数出现次数超过 10亿了，直接返回这个数，无需继续统计。
• 如果是 40亿个整数 ?
  • 拆分出更多的文件。
  • 出现次数 value 起始值不能为 0，可以为 -20亿。
• 如果是 80亿个整数 ?
  • 拆分出更多的文件。
  • 出现次数 value 起始值不能为 0，可以为 -20亿。
  • 因为某个数出现次数超过 40亿的时候，无需继续统计。

---

100 亿个 URL 中重复词汇的 TOP K 问题

• 题目：一个包含 100 亿条 URL 的大文件，每个 URL 占用 64 个字节，找出重复的 URL。
• 附加：某搜索公司每天需要处理海量搜索词汇，设计一个找出每天热门 Top 100 词汇的可行方法。
• 解决方案：hash 分流 + 散列表词频统计。
• 询问资源限制：内存、时间、机器。
• hash 分流：
  • 把大文件拆分为若干个小文件。
  • hash 运算特征：同一个 key 反复 hash 运算总是得到同一个值。
  • hash 算法具备随机性 → 将大文件中的数据均衡分布在多个小文件中。
  • 把大文件分流到多台机器中处理。
• 时间限制：
  • 使用散列表进行词频统计。
  • 为什么不使用平衡二叉树（红黑树）?
    • 因为不要求有序。
• Top K 问题：
  • 此时是否使用平衡二叉树来统计 ?
    • 只要求一部分有序，不使用平衡二叉树。
  • 维护一个大小为 K 的最小堆。

---

40 亿个非负整数中找到未出现的数

• 题目：最多使用 1GB 内存，怎么找到所有未出现过的数。
• 进阶：内存限制为 10MB，只需找到一个没出现过的数即可。
• 解题思路：
  • 非负整数范围：0 ~ 42.9亿之间，那么有接近 3亿的数字未出现。
  • 散列表：40亿 * 4B = 16G。
  • 位图：大概需要 537MB 空间。
    • unsigned char arr[536870911];
    • x / 8 得到数组索引值，也就是 unsigned char 的一个值 value。
      • 因为每个 unsigned char 存储 8位。
    • x % 8 得到具体位，value = value | 1 << bit;。
    • 将 40亿个数字执行前两步后进行整体遍历，如果某一位不为 1，则该数字未出现过。
• 如果内存限制为 10MB：
  • 问题拆分：537 / 10 = 53.7份，至少需要拆分为 54份数据。
  • 为了优化除法运算，找一个恰好大于 54 的 $2^n$，即 $2^6$。
    • 除以 64 可以优化为右移 6 位。
  • 解题思路：
    • 准备一个数组 unsigned int arr[64]，每个区间的数字个数为 67108864。
    • 将某个数字对 67108864 整除，相当于右移 26位，得到的值肯定在 0 ~ 63 之间。
    • 假设得到的是 x，arr[x]++。
    • 将 40亿个数字经过上面运算，找出 arr[i] < 67108864，这样找出 i 区间有未出现的数字。
    • 接着对 i 区间的数字使用位图，找出未出现的数字即可。

---