您将使用哪种数据结构:TreeMap 或 HashMap?(爪哇) [英] Which data structure would you use: TreeMap or HashMap? (Java)

问题描述

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

Description | A Java program to read a text file and print each of the unique words in alphabetical order together with the number of times the word occurs in the text.

程序应该声明一个Map类型的变量来存储单词和相应的出现频率.但是，哪种具体类型?TreeMap 或 HashMap ?

The program should declare a variable of type Map<String, Integer> to store the words and corresponding frequency of occurrence. Which concrete type, though? TreeMap<String, Number> or HashMap<String, Number> ?

输入应转换为小写.

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

A word does not contain any of these characters: ]f.,!?:;"()'

示例输出 |

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

备注 | 我知道，我已经在 Perl 中看到了用大约两行代码来解决这个问题的优雅解决方案.但是，我想在 Java 中看到它.

Remark | I know, I've seen elegant solutions to this in Perl with roughly two lines of code. However, I want to see it in Java.

哦，是的，使用其中一种结构(在 Java 中)显示实现会很有帮助.

Oh yeah, it be helpful to show an implementation using one of these structures (in Java).

推荐答案

TreeMap 对我来说似乎很简单——仅仅是因为按字母顺序"的要求.HashMap 迭代时没有排序；TreeMap 按自然键顺序迭代.

TreeMap seems a no-brainer to me - simply because of the "in alphabetical order" requirement. HashMap has no ordering when you iterate through it; TreeMap iterates in the natural key order.

我认为 Konrad 的评论可能是建议使用 HashMap，然后排序".这很好，因为虽然我们最初会有 N 次迭代，但由于重复，我们最终会有 K <= N 个键.我们不妨将昂贵的部分(排序)保存到最后，当我们得到更少的键时，而不是在进行时保持排序的小但非恒定的打击.

I think Konrad's comment may have been suggesting "use HashMap, then sort." This is good because although we'll have N iterations initially, we'll have K <= N keys by the end due to duplicates. We might as well save the expensive bit (sorting) until the end when we've got fewer keys than take the small-but-non-constant hit of keeping it sorted as we go.

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

Having said that, I'm sticking to my answer for the moment: because it's the simplest way of achieving the goal. We don't really know that the OP is particularly worried about performance, but the question implies that he's concerned about the elegance and brevity. Using a TreeMap makes this incredibly brief, which appeals to me. I suspect that if performance is really an issue, there may be a better way of attacking it than either TreeMap or HashMap :)

这篇关于您将使用哪种数据结构:TreeMap 或 HashMap?(爪哇)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！