你会使用哪种数据结构:TreeMap或HashMap?(JAVA)

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (17)

说明| 一个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来看它。

提问于
用户回答回答于

TreeMap对我来说似乎是一件简单的事情 - 仅仅因为“按字母顺序排列”的要求。当你遍历它时,HashMap没有排序; TreeMap按自然键顺序进行迭代。

我认为康拉德的评论可能一直暗示“使用HashMap,然后排序”。这很好,因为尽管我们最初会进行N次迭代,但由于重复,最终会有K <= N个键。我们不妨将这些昂贵的位(排序)保存到最后,直到我们拥有更少的密钥,而不是像我们走的时候那样保持排序的小而非恒定的命中。

话虽如此,我暂时坚持我的回答:因为这是实现目标的最简单方式。我们并不真的知道OP对表演特别担心,但这个问题意味着他对优雅和简洁感到担忧。使用TreeMap使这个令人难以置信的简短,这吸引我。我怀疑,如果性能确实是一个问题,那么攻击它的方式可能会比TreeMap或HashMap更好:)

用户回答回答于

因为TreeMap已经为你排序,所以TreeMap击败HashMap。

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

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

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

HashMap vs TreeMap性能的问题由Jon - HashMap回答,排序可能会更快(尝试它!),但TreeBag更容易。袋子也是如此。有一个HashBag以及一个TreeBag。根据实现(使用可变整数),一个袋子应该优于Integer的等效平原地图。要知道的唯一方法就是测试,就像任何性能问题一样。

扫码关注云+社区