java - TreeBag 的比较器按出现次数排序

Question

我有一个字符串源(比方说，一个文本文件)，并且许多字符串重复多次。我需要按照出现次数递减的顺序获取前 X 个最常见的字符串。

首先想到的想法是创建一个可排序的 Bag(类似于 org.apache.commons.collections.bag.TreeBag)并提供一个比较器来按顺序对条目进行排序我需要。但是，我无法弄清楚我需要比较的对象类型是什么。它应该是某种内部映射，结合了我的对象(字符串)和出现次数，由 TreeBag 内部生成。这可能吗？

或者我会更好地简单地使用 HashMap 并按值对其进行排序，例如 Java sort HashMap by value 中所述。

Answer 1

为什么不将字符串放入 map 中。字符串到它们在文本中出现的次数的映射。在步骤2中，遍历map中的项目并继续将它们添加到大小为X的最小堆中。如果堆已满，则在插入之前始终先提取min。
需要 nlogx 时间。

否则，在步骤 1 之后，按出现次数对项目进行排序，并取出前 x 个项目。树形图在这里会很有帮助:)(我添加了一个指向 javadocs 的链接，但我在平板电脑中)需要 nlogn 时间。