54

说明 | 一个 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 中）显示实现会很有帮助。

4

14 回答 14

62

TreeMap对我来说似乎很容易 - 仅仅是因为“按字母顺序”的要求。HashMap迭代时没有排序；TreeMap以自然键顺序迭代。

编辑：我认为康拉德的评论可能暗示“使用HashMap，然后排序”。这很好，因为虽然我们最初会有 N 次迭代，但由于重复，我们最终会有 K <= N 个键。我们还不如将昂贵的位（排序）保存到最后，因为我们得到的键更少，而不是在进行时保持排序的小但非恒定的打击。

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

于 2008-11-19T15:56:52.010 回答
18

TreeMap 优于 HashMap，因为 TreeMap 已经为您排序。

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

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

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

编辑：乔恩回答了 HashMap 与 TreeMap 性能的问题 - HashMap 和排序可能更快（试试吧！），但 TreeBag 更容易。袋子也是如此。有一个 HashBag 和一个 TreeBag。根据实现（使用可变整数），bag 应该优于 Integer 的等效普通映射。唯一确定的方法是测试，就像任何性能问题一样。

于 2008-11-19T16:06:11.290 回答
11

我看到不少人说“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 = 文本中不同单词的数量。

于 2011-04-14T14:21:51.800 回答
3

哈希映射应该快得多。您不应该根据您希望项目最终如何排列来选择容器；只需在最后对（单词，频率）对列表进行排序。通常要排序的此类对比文件中的单词少，因此使用哈希映射的渐近（和真实）性能会更好。

于 2008-11-19T17:35:40.330 回答
3 
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();
        }
    }

}
于 2012-05-03T13:02:31.723 回答
2

您不能将 a 分配给TreeMap<String,Number>类型为 的变量Map<String,Integer>。Double,Long等可以“放入”到TreeMap<String,Number>. 当我从 a 中“获取”一个值时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());
    }
  }

}
于 2008-11-19T16:17:34.667 回答
2

“当一个键已经存在时，它具有与 HashMap 相同的性能。” - 这是完全错误的。HashMap 有 O(1) 插入和 TreeMap O(n log n)。至少需要 n log n 检查才能确定它是否在表中！

于 2010-08-14T03:46:49.463 回答
2

对于这种方式，在我看来，最好使用Apache Commons Collections的HashBag或Guava的HashMultiset或Eclipse Collections的HashBag（以前称为GS Collections）或任何以下类：

    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>))
────────────────────────────────────────────────────────────────────────

例子：

1.使用 Apache 的 SynchronizedSortedBag：

    // 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

2. 使用 Eclipse(GC) 中的 TreeBag：

    // 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

3.使用来自 Guava 的 LinkedHashMultiset：

    // 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

您可以在我的 github 项目中找到更多示例

于 2016-03-04T17:39:50.460 回答
1

我肯定会选择 TreeMap：

  • TreeMap 在插入时自动对新键进行排序，之后不需要排序。
  • 当键已经存在时，它具有与 HashMap 相同的性能。

TreeSet 在内部使用 TreeMap，所以为什么不直接使用 TreeMap。

于 2008-11-19T18:44:41.407 回答
0

根据速度要求，您还可以使用Trie。但是，如果 TreeMap 足够快，那么实现其中之一是没有意义的。

于 2008-11-19T16:06:20.667 回答
0

考虑添加或删除数据结构的频率。如果 TreeMap 很高，它就不是理想的了。除了搜索现有条目 nLn 之外，它还经常进行重新平衡。

另一方面，哈希结构在内存上有点华丽（过度分配）。如果您可以咬紧牙关，那么请在需要时使用哈希结构并进行排序。

于 2010-08-19T11:40:32.227 回答
0

这是读取文本文件的java示例，根据键排序，然后根据值排序；取决于文件中单词的出现次数。

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;
    }
}
于 2015-06-28T12:54:10.993 回答
-2

为什么不使用TreeSet？

与 TreeMap 相同的排序概念，除了它是一个 Set - 根据定义，它是“不包含重复元素的集合”。

从您的问题描述中，听起来好像您需要一个 Set，我看不出您将哪些键和值映射在一起。

此类实现由 TreeMap 实例支持的 Set 接口。此类保证已排序的集合将按元素升序排序，根据元素的自然顺序（请参阅 Comparable）或在集合创建时提供的比较器排序，具体取决于使用的构造函数。

于 2008-11-19T16:14:11.337 回答
-3

基本上这取决于需求。有时哈希图很好，有时树图很好。但是哈希映射最好只使用它们是对开销进行排序的一些约束。

于 2011-04-05T13:02:27.210 回答