如果对数据进行了排序，则可以在 O(n) 哪里 n 是数据的大小。因为数据是排序的，不同的值是连续的。当遍历一次数据时对它们进行计数，可以得到全局频率，当数据未排序时，该频率对您不可用。
请参阅下面的示例代码，了解如何做到这一点。github上还有一个完整方法的实现（在kotlin中）
注意：实际上，排序本身不是必需的。所需要的是不同的值是连续的（因此不需要定义顺序）-我们从排序中获得这一点，但也许有一种方法可以更有效地做到这一点。
您可以使用（外部）合并排序对数据文件进行排序 O(n log n) 通过将输入数据文件拆分为适合内存的较小文件，排序并将其写入排序后的文件，然后合并它们。
关于此代码示例：
排序后的数据由 long[] . 因为逻辑一个接一个地读取值，所以它是从排序文件中读取数据的近似值。
op没有明确说明如何处理频率相同的多个值；因此，代码除了确保结果是没有特定顺序的前n个值，并且不意味着没有其他具有相同频率的值之外，什么也不做。

import java.util.*;
import java.util.Map.Entry;

class TopN {
    private final int maxSize;
    private Map<Long, Long> countMap;

    public TopN(int maxSize) {
        this.maxSize = maxSize;
        this.countMap = new HashMap(maxSize);
    }

    private void addOrReplace(long value, long count) {
        if (countMap.size() < maxSize) {
            countMap.put(value, count);
        } else {
            Optional<Entry<Long, Long>> opt = countMap.entrySet().stream().min(Entry.comparingByValue());
            Entry<Long, Long> minEntry = opt.get();
            if (minEntry.getValue() < count) {
                countMap.remove(minEntry.getKey());
                countMap.put(value, count);
            }
        }
    }

    public Set<Long> get() {
        return countMap.keySet();
    }

    public void process(long[] data) {
        long value = data[0];
        long count = 0;

        for (long current : data) {
            if (current == value) {
                ++count;
            } else {
                addOrReplace(value, count);
                value = current;
                count = 1;
            }
        }
        addOrReplace(value, count);
    }

    public static void main(String[] args) {
        long[] data = {0, 2, 3, 3, 4, 5, 5, 5, 5, 6, 6, 6, 7};
        TopN topMap = new TopN(2);

        topMap.process(data);
        System.out.println(topMap.get()); // [5, 6]
    }
}

整数是有符号的32位，所以如果只有正整数发生，我们看2^31最大不同的条目。2^31字节的数组应保持在最大数组大小之下。
但那不能保持高于255的频率，你会说？是的，你说得对。
因此，我们为数组中超过最大值的所有条目添加一个hashmap（255-如果有符号，那么从-128开始计数）。在这个散列图中最多有1600万个条目（40亿除以255），这应该是可能的。
我们有两种数据结构：
一个大数组，按读取的字节数（0..2^31）编制索引。
一个hashmap（数字读取，频率）
算法：

while reading next number 'x'
 {
   if (hashmap.contains(x))
   {
     hashmap[x]++;
   }
   else
   {
     bigarray[x]++;
     if (bigarray[x] > 250)
     {
       hashmap[x] = bigarray[x];
     }
   }
 }

 // when done:
 // Look up top-100 in hashmap
 // if not 100 yet, add more from bigarray, skipping those already taken from the hashmap

我的java语言不太流利，所以不能给出更好的代码示例。
请注意，此算法是单通道的，适用于未排序的输入，并且不使用外部预处理步骤。
它所做的只是假设读取的数字有一个最大值。如果输入是非负整数（最大值为2^31），它应该可以工作。示例输入满足该约束。
上面的算法应该能满足大多数提出这个问题的面试者。能否用java编写代码应该由另一个问题来确定。这个问题是关于设计数据结构和高效算法的。

在伪代码中：
执行外部排序
做一个过程来收集前100个频率（不是哪个值有它们）
执行另一个过程以收集具有这些频率的值
假设：有明显的赢家-没有平局（前100名之外）。
时间复杂度：o（n logn）（近似值）取决于排序。空间复杂度：可用内存，同样由于排序。
第2步和第3步都是o（n）时间和o（1）空间。
如果没有联系（在前100名之外），那么步骤2和步骤3可以合并到一个过程中，这不会提高时间复杂度，但会稍微提高运行时间。
如果有一些平局会让赢家的数量很大，你就无法发现这一点并在没有两次传球的情况下采取特殊行动（例如，抛出错误或放弃所有平局）。但是，您可以从一次传递的关系中找到最小的100个值。

但对于40亿个数字的数据集，它可能会抛出outofmemory异常。此外，因为4000000000超过了java数组的最大长度，所以假设数字在一个文本文件中并且没有排序。
这取决于价值分布。如果您有4e9个数字，但是这些数字是1-1000的整数，那么您将得到一个包含1000个条目的Map。如果数字是双倍的或值空间是不受限制的，那么您可能有问题。
正如前面的回答-有一个错误

unsorted.put(number, unsorted.getOrDefault(number, 0) + 1);

我个人会使用“atomiclong”作为值，它允许在不更新hashmap条目的情况下增加值。
我假设多线程或map reduce更适合大数据集？解决这个问题最有效的办法是什么？
这是一个典型的map-reduce练习示例，因此理论上可以使用多线程或m-r方法。也许这是您练习的目标，您应该实现多线程map reduce任务，不管它是否是最有效的方法。
实际上，你应该计算一下是否值得付出努力。如果您正在串行读取输入（因为它在您的代码中使用 Scanner )，那肯定不行。如果考虑到i/o吞吐量，可以拆分输入文件并并行读取多个部分，则可能是这样。
或者，如果值空间太大，无法放入内存，并且需要缩小数据集的规模，则可以考虑采用不同的方法。

因为数据集对于内存来说可能太大了，所以我会进行十六进制基数排序。因此，数据集将在每个过程中被分割成16个文件，并根据需要使用尽可能多的过程来获得最大的整数。
第二部分是将这些文件合并成一个大数据集。
第三部分是逐个读取文件编号，并计算每个编号的出现次数。将出现的次数和次数保存到按大小排序的二维数组（列表）中。如果文件中的下一个数字的出现次数多于列表中出现次数最少的数字，则替换该数字。

一种选择是二进制搜索。考虑一个二叉树，其中每个分割对应于32位整数中的一位。所以概念上我们有一个深度为32的二叉树。在每个节点上，我们可以计算集合中从该节点的位序列开始的数字的计数。这个计数是一个o（n）运算，因此查找最常见序列的总开销将是o（nf（n）），其中函数取决于需要枚举的节点数。
让我们先考虑深度优先搜索。这为枚举期间的堆栈大小提供了合理的上限。对所有节点进行暴力搜索显然很糟糕（在这种情况下，您可以完全忽略树的概念，只需枚举所有整数），但我们有两件事可以避免搜索所有节点：
如果我们到达一个分支，其中以该位序列开始的集合中有0个数字，我们可以修剪该分支并停止枚举。
一旦我们到达一个终端节点，我们就知道这个特定的数字出现了多少次。我们将此添加到“前100名”列表中，必要时删除最低的。一旦这个列表满了，我们就可以开始修剪任何总计数低于“前100个”计数中最低值的分支。
我不确定这种情况下的平均和最坏表现。对于不同数目较少的集合，它的性能会更好，而对于接近均匀分布的集合，它的性能可能最差，因为这意味着需要搜索更多的节点。
一些观察结果：
最多有n个终端节点的计数为非零，但在这种特定情况下，由于n>2^32，这并不重要。
m个叶节点（m=2^32）的节点总数为2m-1。这在m中仍然是线性的，所以最坏情况下的运行时间在o（nm）上是有界的。
在某些情况下，这比只搜索所有整数的性能差，而只搜索一个线性标量因子。平均而言，这是否表现得更好取决于预期的数据。对于均匀随机的数据集，我的直觉猜测是，一旦前100名列表填满，您将能够修剪足够多的分支，您可能需要少于m个计数，但这需要经验评估或证明。
实际上，该算法只需要对数据集进行只读访问（它只执行从特定位模式开始的数字计数），这意味着它可以通过跨多个数组存储数据、并行计算子集、然后将计数相加来进行并行化。在实际实现中，这可能是一个相当大的加速，而对于一个需要排序的方法来说，这是很难做到的。
这是一个如何执行的具体例子，对于一组更简单的3位数字，只查找单个最频繁的数字。假设集合是'000，001，100，001，100，010'。
计算所有以“0”开头的数字。这个数是4。
再深入一点，数一数所有以“00”开头的数字。这个数是3。
数一数“000”的所有数字。这个数是1。这是我们最常见到的新朋友。
数一数所有为“001”的数字。这个数是2。这是我们最常见到的新朋友。
取下一根深树枝，数一数以“01”开头的所有数字。此计数为1，小于最频繁的计数，因此可以停止枚举此分支。
计算所有以“1”开头的数字。此计数为1，小于最频繁的计数，因此可以停止枚举此分支。
我们没有分支了，所以我们完成了，“001”是最常见的。

linux工具

这只需在linux/mac上的shell脚本中完成：

sort inputfile | uniq -c | sort -nr | head -n 100

如果已经对数据进行了排序，只需使用

uniq -c inputfile | sort -nr | head -n 100