java - 计算项目的出现次数

Question

我正在尝试找出以下问题的最佳解决方案(在 Java 中):

在第一次传递一些数据时，我计算了一个项目出现的次数。基本上，我创建了一个从项目 ID 到整数的 HashMap，并在每次看到项目出现时递增整数。所以基本上，我有一个 Map<Long,Integer>从 itemID 开始计数。

现在，我需要从这张 map 中获得按计数排序的前 n 个项目 ID。

显然 HashMap 不是这里的最佳数据结构。有什么想法吗？

这是我在工作中做的一些数据挖掘工作，所以不是硬件问题...

Answer 1

实际上，HashMap 在这里是一个合理的解决方案，因为您必须累加总数。在您知道所有项目的计数之前，您无法通过快捷方式找到前 N 个项目。

有了 HashMap 之后，有几种方法可以做事。如果数据比较少，创建一个itemId和count对的数组，按照count降序排列。然后选择前 N 项。

如果你有很多项目(数十万)，在你得到计数后使用最小堆可能会更快，这个想法是你将前 N 个项目放入最小堆然后只插入一个如果它的计数大于最小堆中的最小项。

在进行加法操作时，您可以按计数排序，但每次递增计数器时，您都必须从集合中移除并重新插入。您最好在 HashMap 中累积内容，这样可以很容易地按 ID 查找内容，然后进行后处理以按计数应用排序。