在内存限制的情况下从 2000GB 数据中返回前 10 个字

Question

我有 2000GB 的字符串数据，我的电脑有 2GB 的空间。我想返回数据中出现频率最高的前 10 个单词。

我在技术面试中被问到这个问题。我尝试使用 HashMap、优先级队列来解决这个问题，但面试官并不满意，因为最坏的情况是每个单词只出现一次。

Answer 1

如果您不着急，可以执行以下操作。

• 1 将数据复制到存储（不是 RAM）并在副本上进行操作（因为它会发生变异）。
• 2 维护一个哈希图，最初是空的，但很快就有 10 个键。键是迄今为止找到的频率最高的 10 个单词，值是频率。
• 3 选择第一个（剩余）字符串中的第一个单词

  w

  。将其添加到值为 1 的哈希映射中，并从字符串中删除该单词。如果字符串为空，则删除该字符串。
• 4 遍历所有字符串的所有单词。每当在给定字符串增量中找到

  w

  时，它就会在哈希映射中计数，从该字符串中删除该单词，如果该字符串为空，则删除该字符串。
• 5 从哈希图中删除值最小的键，留下迄今为止发现的频率最高的 10 个键（单词）。
• 6 重复步骤 3，直到没有任何绳子剩余。