你会使用哪种数据结构: TreeMap还是HashMap？(Java)
说明|一个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中)会很有帮助。
回答 14
Stack Overflow用户
发布于 2008-11-19 15:56:52
TreeMap对我来说似乎是不需要动脑筋的--仅仅是因为“按字母顺序”的要求。当您迭代HashMap时，它没有顺序；TreeMap以自然键的顺序迭代。
编辑:我认为康拉德的评论可能是在建议“使用HashMap，然后排序”。这很好，因为虽然我们一开始会有N次迭代，但由于重复，到最后我们会有K个<= N个密钥。我们不妨把昂贵的比特(排序)保留到最后，当我们有更少的键时，而不是承受小但不稳定的打击，保持它的排序。
话虽如此，我目前仍坚持我的答案:因为这是实现目标的最简单方法。我们真的不知道OP是否特别担心性能，但这个问题意味着他关心的是优雅和简洁。使用TreeMap让这一切变得非常简短，这对我很有吸引力。我怀疑，如果性能真的是一个问题，那么可能有比TreeMap或HashMap更好的方法来攻击它:)
Stack Overflow用户
发布于 2008-11-19 16:06:11
TreeMap胜过HashMap，因为TreeMap已经为您排序了。
但是，您可能希望考虑使用更合适的数据结构，即包。请参阅Commons Collections和TreeBag类：
这有一个很好的优化的内部结构和API：
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")编辑: HashMap和TreeMap性能的问题由Jon - HashMap回答，排序可能更快(试试吧！)，但TreeBag更容易。包包也是如此。除了TreeBag之外，还有一个HashBag。基于实现(使用可变整数)，bag的性能应该优于Integer的等效平面图。确定的唯一方法是测试，就像任何性能问题一样。
Stack Overflow用户
发布于 2011-04-14 22:21:52
我看到不少人说"TreeMap look-up takes O(n log n)"！怎么会这样?
我不知道它是如何实现的，但在我的脑海中，它需要O(log n)。
这是因为在树中的查找可以在O(log n)中完成。并不是每次在树中插入项目时都对整个树进行排序。这就是使用树的全部想法！
因此，回到原来的问题，可作比较的数字如下：
HashMap方法： O(n + k log k)平均情况，最坏情况可能更大
TreeMap方法： O(k + n log k)最坏情况
其中n=文本中的单词数量，k=文本中不同单词的数量。
https://stackoverflow.com/questions/302371
复制相似问题