描述 | 一个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中）会很有帮助。
TreeMap 似乎是个不言而喻的选择 - 这仅仅是因为它需要“按字母顺序”排序。当你遍历 HashMap 时没有排序；TreeMap 则按自然键排序。
编辑：我认为 Konrad 的评论可能是在建议“使用 HashMap，然后进行排序。”这很好，因为尽管最初我们将有 N 次迭代，但由于重复，最后我们将只有 K ≤ N 个键。我们可以把昂贵的部分（排序）留到最后，当我们有比之前更少的键时再进行排序，而不是花费小但非固定的代价一边遍历一边排序。
话虽如此，就目前而言，我会坚持我的答案：因为这是实现目标最简单的方式。我们并不真正知道 OP 是否特别关注性能，但问题意味着他关心优雅和简洁。使用 TreeMap 使这变得非常简短，这很吸引我。我猜想，如果性能真的是一个问题，可能有更好的方法来解决它，而不是使用 TreeMap 或 HashMap :)
k，但我们在这里没有这样做。 我认为在这种情况下不能忽略k的值。 - Jon SkeetTreeMap比HashMap更好，因为TreeMap已经为您排序。
但是，您可能希望考虑使用更合适的数据结构-一个bag。请参见Commons Collections，以及TreeBag类：
它具有优化的内部结构和API：
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
编辑：Jon已回答了HashMap与TreeMap性能问题 - HashMap和排序可能更快（可以尝试！），但TreeBag更容易。相同的情况也适用于bags。有HashBag和TreeBag。基于实现（使用可变整数），bag应该优于等价的纯整数映射。要确定，唯一的方法是测试，就像任何性能问题一样。
我看到很多人说 "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 = 文本中不同单词的数量。
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream.GetField;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class TreeMapExample {
public static void main (String args[]){
Map<String,Integer> tm = new TreeMap<String,Integer>();
try {
FileInputStream fis = new FileInputStream("Test.txt");
DataInputStream in = new DataInputStream(fis);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String line;
int countValue = 1;
while((line = br.readLine())!= null ){
line = line.replaceAll("[-+.^:;,()\"\\[\\]]","");
StringTokenizer st = new StringTokenizer(line, " ");
while(st.hasMoreTokens()){
String nextElement = (String) st.nextElement();
if(tm.size()>0 && tm.containsKey(nextElement)){
int val = 0;
if(tm.get(nextElement)!= null){
val = (Integer) tm.get(nextElement);
val = val+1;
}
tm.put(nextElement, val);
}else{
tm.put(nextElement, 1);
}
}
}
for(Map.Entry<String,Integer> entry : tm.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
哈希表应该更快。您不应该根据最终想要的项目排列方式选择容器；只需在最后对（单词，频率）对列表进行排序即可。需要排序的这些对通常比文件中的单词要少，因此使用哈希表的渐近（和实际）性能会更好。
Order | Guava | Apache | Eclipse(GS) | JDK analog
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Not define | HashMultiset | HashBag | HashBag | HashMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Sorted | TreeMultiset | TreeBag | TreeBag | TreeMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Linked |LinkedHashMultiset| - | - | LinkedHashMap<String, Integere>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent & | ConcurrentHash- |Synchroniz-|Synchroniz- | Collections.synchronizedMap(
not define | Multiset | edBag | edBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent | - |Synchroniz-|Synchroniz- | Collections.synchronizedSorted-
and sorted | |edSortedBag| edSortedBag | Map(TreeMap<>))
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableMultiset|Unmodifiab-|Unmodifiab- | Collections.unmodifiableMap(
not define | | leBag | leBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableSorted- |Unmodifiab-|Unmodifiab- | Collections.unmodifiableSorted-
sorted | Multiset |leSortedBag| leSortedBag | Map(TreeMap<String, Integer>))
────────────────────────────────────────────────────────────────────────
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Bag bag = SynchronizedSortedBag.synchronizedBag(new TreeBag(Arrays.asList(INPUT_TEXT.split(" "))));
// Print count words
System.out.println(bag); // print [1:All!,2:Hello,1:Hi,2:World!]- in natural (alphabet) order
// Print all unique words
System.out.println(bag.uniqueSet()); // print [All!, Hello, Hi, World!]- in natural (alphabet) order
// Print count occurrences of words
System.out.println("Hello = " + bag.getCount("Hello")); // print 2
System.out.println("World = " + bag.getCount("World!")); // print 2
System.out.println("All = " + bag.getCount("All!")); // print 1
System.out.println("Hi = " + bag.getCount("Hi")); // print 1
System.out.println("Empty = " + bag.getCount("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.uniqueSet().size()); //print 4
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
MutableSortedBag<String> bag = TreeBag.newBag(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(bag); // print [All!, Hello, Hello, Hi, World!, World!]- in natural order
// Print all unique words
System.out.println(bag.toSortedSet()); // print [All!, Hello, Hi, World!]- in natural order
// Print count occurrences of words
System.out.println("Hello = " + bag.occurrencesOf("Hello")); // print 2
System.out.println("World = " + bag.occurrencesOf("World!")); // print 2
System.out.println("All = " + bag.occurrencesOf("All!")); // print 1
System.out.println("Hi = " + bag.occurrencesOf("Hi")); // print 1
System.out.println("Empty = " + bag.occurrencesOf("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.toSet().size()); //print 4
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Multiset<String> multiset = LinkedHashMultiset.create(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(multiset); // print [Hello x 2, World! x 2, All!, Hi]- in predictable iteration order
// Print all unique words
System.out.println(multiset.elementSet()); // print [Hello, World!, All!, Hi] - in predictable iteration order
// Print count occurrences of words
System.out.println("Hello = " + multiset.count("Hello")); // print 2
System.out.println("World = " + multiset.count("World!")); // print 2
System.out.println("All = " + multiset.count("All!")); // print 1
System.out.println("Hi = " + multiset.count("Hi")); // print 1
System.out.println("Empty = " + multiset.count("Empty")); // print 0
// Print count all words
System.out.println(multiset.size()); //print 6
// Print count unique words
System.out.println(multiset.elementSet().size()); //print 4
TreeMap<String,Number>分配给类型为Map<String,Integer>的变量。您可以将Double、Long等放入TreeMap<String,Number>中。当我从Map<String,Integer>获取一个值时，它必须是一个Integer。请忽略任何i18n问题、内存限制和错误处理，以下是内容：class Counter {
public static void main(String... argv)
throws Exception
{
FileChannel fc = new FileInputStream(argv[0]).getChannel();
ByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
CharBuffer cb = Charset.defaultCharset().decode(bb);
Pattern p = Pattern.compile("[^ \t\r\n\f.,!?:;\"()']+");
Map<String, Integer> counts = new TreeMap<String, Integer>();
Matcher m = p.matcher(cb);
while (m.find()) {
String word = m.group();
Integer count = counts.get(word);
count = (count == null) ? 1 : count + 1;
counts.put(word, count);
}
fc.close();
for (Map.Entry<String, Integer> e : counts.entrySet()) {
System.out.printf("%s: %d%n", e.getKey(), e.getValue());
}
}
}
我肯定会选择TreeMap：
TreeSet内部使用TreeMap，因此为什么不直接使用TreeMap。
public class SortFileWords {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<String, Integer>();
ValueCompare vc = new ValueCompare(map);
TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(map);
List<String> list = new ArrayList<>();
Scanner sc;
try {
sc = new Scanner(new File("c:\\ReadMe1.txt"));
while (sc.hasNext()) {
list.add(sc.next());
}
sc.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
for (String s : list) {
if (map.containsKey(s)) {
map.put(s, map.get(s) + 1);
} else
map.put(s, 1);
}
System.out.println("Unsorted map: " + map);
sorted_map.putAll(map);
System.out.println("Sorted map on keys: " + sorted_map);
TreeMap<String, Integer> sorted_value_map = new TreeMap<>(vc);
sorted_value_map.putAll(map);
System.out.println("Sorted map on values: " + sorted_value_map);
}
}
class ValueCompare implements Comparator<String> {
Map<String, Integer> map;
public ValueCompare(Map<String, Integer> map) {
this.map = map;
}
@Override
public int compare(String s1, String s2) {
if (map.get(s1) >= map.get(s2))
return -1;
else
return 1;
}
}