java - 词频 - HashMap 或 TreeMap

Question

我需要编写一个程序来计算文本中每个单词的频率，此外我需要能够返回 n 个最常用单词的列表(如果更多单词具有相同的频率(它们按字母顺序排序)。还有一个未计算在内的单词列表(停用词)。

1. 停用词使用什么结构
   • 我认为 HashSet 是最有效的
2. 单词和频率映射使用什么结构
   • HashMap 添加单词的效率更高，但需要排序，TreeMap 插入单词需要 logn 时间，但单词可以按频率排序

哪种方法总体上更有效？

附注@版主我知道有一个类似的question ，但我有不同的限制，需要不同的结构。

Answer 1

假设有k总共字数和 m不同的单词，您想要 n最常用的词。

树形图

因为永远不会超过 m map 中的单词，每次更新/插入都会花费 O(log m) ，总运行时间为 O(k log m) .

HashMap

每次更新/插入的成本预计为 O(1) ，取O(k)对于所有单词。

然后，因为会有 m图中的单词，排序会取O(m log m) .

但是我们可以做得比排序更好 - 我们可以迭代 HashMap并维持 heap ( PriorityQueue ) n最常见的单词(主要按频率排序，其次按字母顺序排序)。每次插入堆后，如果大小大于n ，我们删除最不常见的单词。这将需要 O(m log n) .

因此，预计总运行时间为 O(k + m log n) .

比较

自 n <= m和m <= k ，我们知道m log n <= k log m ，并且，假设有大量重复项或 n比 m 稍小, k + m log n <= k log m ，所以HashMap通常是首选。