您将使用哪种数据结构:TreeMap或HashMap？(JAVA)

Question

说明| 一种Java程序,用于读取文本文件并按字母顺序打印每个唯一单词以及单词在文本中出现的次数.

程序应该声明一个类型的变量Map<String, Integer>来存储单词和相应的出现频率.但是哪种具体类型呢？TreeMap<String, Number>还是HashMap<String, Number>？

输入应转换为小写.

一个单词不包含以下任何字符: \t\t\n]f.,!?:;\"()'

示例输出|

 Word            Frequency
  a                 1
  and               5
  appearances       1
  as                1
         .
         .
         .

备注| 我知道,我已经在Perl中看到了大致两行代码的优雅解决方案.但是,我想在Java中看到它.

编辑:哦,是的,使用这些结构之一显示实现是有帮助的(在Java中).

Answer 1

TreeMap对我来说似乎不费吹灰之力 - 仅仅是因为"按字母顺序"的要求.迭代时HashMap没有排序; TreeMap以自然键顺序迭代.

编辑:我认为Konrad的评论可能暗示"使用HashMap,然后排序".这很好,因为尽管我们最初会进行N次迭代,但由于重复,我们最终会得到K <= N个密钥.我们不妨将昂贵的位(排序)保存到最后,当我们获得的密钥少于采用小而非常量的命中时保持按顺序排序.

话虽如此,我现在仍然坚持我的答案:因为这是实现目标的最简单方法.我们并不是真的知道OP特别担心性能,但问题暗示他关注优雅和简洁.使用TreeMap使这个非常简短,这对我很有吸引力.我怀疑如果性能真的是一个问题,可能有一种比TreeMap或HashMap更好的攻击方式:)

Answer 2

TreeMap击败了HashMap,因为TreeMap已经为你排序了.

但是,您可能需要考虑使用更合适的数据结构,即包.请参阅 Commons Collections - 和TreeBag类:

这有一个很好的优化内部结构和API:

bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")

编辑:Jon-HashMap回答了HashMap与TreeMap性能的问题,排序可能更快(尝试一下!),但TreeBag更容易.包袋也是如此.有一个HashBag和一个TreeBag.根据实现(使用可变整数),一个包应该胜过Integer的等效平面映射.确切知道的唯一方法是测试,就像任何性能问题一样.

Answer 3

我看到不少人说"TreeMap查找需要O(n log n)"!! 怎么会？

我不知道它是如何实现的,但在我的头脑中它需要O(log n).

这是因为树中的查找可以完成O(log n).每次在其中插入项目时,都不会对整个树进行排序.这就是使用树的整个想法!

因此,回到最初的问题,比较的数字结果是:

HashMap方法: O(n + k log k)平均情况,最坏情况可能会大得多

TreeMap方法: O(k + n log k)最坏的情况

其中n =文本中的单词数,k =文本中不同单词的数量.