我有一个文件，其中有许多随机整数(大约一百万)，每个整数由一个空格分隔。我需要在该文件中找到前 10 个最常出现的数字。在 Java 中执行此操作的最有效方法是什么？ 我能想到 1.创建一个 HashMap ，key是文件中的整数，value是计数。对于文件中的每个数字，检查该键是否已存在于 HashMap 中，如果是，value++，否则在哈希中创建一个新条目 2.做一个BST，每个节点都是文件中的整数。对于文件中的每个整数，查看 BST 中是否有节点，如果有，则执行 value++，value 是节点的一部分。
如果我能想出好的哈希函数，我觉得 HashMap 是更好的选择， 有人可以建议我这样做最好的是什么吗？我可以使用其他有效的算法吗？
最佳答案
编辑#2:
好吧，我搞砸了我自己的第一条规则——永远不要过早地优化。最坏的情况可能是使用范围很广的库存 HashMap——所以我就这么做了。它仍然会在一秒钟内运行，所以忘记这里的其他一切，只管这样做。
在担心棘手的实现之前，我会另外提醒自己始终测试速度。
(以下是旧的过时帖子，如果有人的积分超过一百万，它仍然有效)
HashSet 可以工作，但是如果你的整数有一个合理的范围(比如 1-1000)，那么创建一个包含 1000 个整数的数组会更有效，并且对于你的百万个整数中的每一个，递增大批。 (与 HashMap 的想法几乎相同，但是优化 Hash 必须考虑的一些未知数应该会使它快几倍)。
您还可以创建一棵树。树中的每个节点都将包含 (value, count) 并且树将按值组织(左侧的值较低，右侧的值较高)。遍历你的节点，如果它不存在——插入它——如果它存在，然后增加计数。
值的范围和分布将决定这两者(或常规哈希)中的哪一个表现更好。我认为常规哈希不会有很多“获胜”案例(它必须是范围广泛且“分组”的数据，即使这样树也可能获胜。
由于这非常微不足道——我建议您实现多个解决方案并针对实际数据集测试速度。
编辑:回复评论
TreeMap 可以工作，但仍会添加一个间接层(而且自己实现起来非常简单和有趣)。如果您使用股票实现，则必须使用整数并不断地在每次增加时与 int 进行转换。有指向整数的指针的间接寻址，以及您存储的对象至少是 2 倍的事实。这甚至不计算方法调用的任何开销，因为运气好的话它们应该被内联。
通常这会是一种优化(邪恶)，但是当你开始接近数十万个节点时，你偶尔必须确保效率，所以内置的 TreeMap 会因为同样的原因而变得低效-in HashSet 会。
关于java - 庞大的数字列表中最常重复的数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1402830/