词频-HashMap或TreeMap

Question

我需要使一个程序，计数频率的每一个字在一个文本，另外，我需要能够返回一个列表的n个最经常的字（如果更多的字有相同的频率，他们排序的字母顺序）。还有一个单词列表是不被计算的（停止单词）。

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

  总体而言，什么方法更有效？

  附言。@主持人我知道有一个类似的问题，但我有一个不同的约束，需要不同的结构。

Answer 1

树状图

由于映射中的单词不能超过m，因此每次更新/插入都要花费O（log m)，总运行时间为O（k log m)。

HashMap

每次更新/插入都将花费预期的O(1)，对所有单词取O(k)。

然后，由于映射中将有m单词，因此排序将采用O（m log m)。

但是我们可以做得比排序更好--我们可以遍历HashMap并维护N最频繁单词的堆(PriorityQueue)（主要按频率排序，其次按字母排序）。每次插入堆后，如果大小大于n，我们将删除最不频繁的单词。这将采用O（m log n)。

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

比较

由于n<=m和m<=k，我们知道m log n<=k log m，假设有大量重复项，或者n比mk+m log n<=k log m，因此hashmap通常是首选。