English 中文(简体)
你会使用哪种数据结构:TreeMap还是HashMap?(Java)[重复]
原标题:
  • 时间:2008-11-19 15:55:12
  •  标签:

描述 | 一个Java程序用于读取文本文件,并按字母顺序打印每个独特的单词以及单词在文本中出现的次数。

该程序应声明一个类型为 Map<String, Integer> 的变量来存储单词及其出现频率。但具体使用哪种类型呢?TreeMap<String, Number> 还是 HashMap<String, Number>

输入应转换为小写。

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

示例输出 |

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

备注 | 我知道,我在Perl中已经看到了优美的解决方案,大约只需要两行代码。然而,我想在Java中看到它。

编辑:哦,展示一个使用这些结构之一的实现(用Java)会很有帮助。

最佳回答

我认为TreeMap似乎是一个不言而喻的选择,因为它需要按字母顺序排序。当你遍历HashMap时没有任何顺序;TreeMap按照自然键的顺序遍历。

编辑:我认为Konrad的评论可能在建议“使用HashMap,然后进行排序”。这是很好的,因为尽管最初我们会有N次迭代,但由于重复项,最后我们将只有K <= N个键。我们可以把代价昂贵的排序过程留到最后,当我们的键比较少时,而不是在整个过程中保持排序状态,并承受一些小但不定常数的损失。

话虽如此,我目前还是坚持我的答案:因为这是实现目标最简单的方式。我们并不真的知道OP是否特别担心性能,但问题暗示他关注优雅和简洁。使用TreeMap使这变得极其简短,这很吸引我。我怀疑如果性能真的是一个问题,可能有比TreeMapHashMap更好的攻击方法 :)

问题回答

TreeMap胜过HashMap,因为TreeMap已经为您排序。

However, you might want to consider using a more appropriate data structure, a bag. See Commons Collections - and the TreeBag class:

这拥有一个优化良好的内部结构和API:

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

编辑:关于HashMap vs TreeMap的性能问题已经被Jon解答了- HashMap和排序可能更快(试试!),但TreeBag更容易。包也是如此。存在HashBag和TreeBag。基于实现(使用可变整数),Bag应优于等效的Integer纯映射。确切知道的唯一方法是测试,就像任何性能问题一样。

我看到很多人说“TreeMap查找的时间复杂度是O(n log n)”!! 怎么回事?

我不知道它是如何实现的,但是在我的头脑中它需要 O(log n)

这是因为在树中查找可以在 O(log n) 内完成。 每次插入一个项目时,您不需要对整个树进行排序。 这就是使用树的整个思想!

因此,回到最初的问题,比较的数字为:

哈希映射方法:平均情况下为O(n + k log k),最坏情况可能会更大。

树图方法:最坏情况下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();
        }
    }

}

你不能将类型为Map的变量分配给TreeMap。Double,Long等可以“放入”TreeMap中。当我从Map中“获取”值时,它必须是一个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("[^ 	
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());
    }
  }

}

当键已经存在时,HashMap 和 TreeMap 的性能是不同的。HashMap 的插入是O(1),TreeMap 是O(n log n)。至少需要n log n 次检查才能确定它是否在表中!

在我看来,更好的方法是使用来自Apache Commons CollectionsHashBag、来自GuavaHashMultiset、来自Eclipse CollectionsHashBag(以前是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. Using SynchronizedSortedBag from Apache:

    // 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. Using TreeBag from Eclipse(GC):

    // 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. Using LinkedHashMultiset from Guava:

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

More examples you can find in my github projects

我一定会选择TreeMap:

  • TreeMap automatically sorts new keys on insertion, no sorting afterwards is needed.
  • When a key already exists it has the same performance as a HashMap.

TreeSet 内部使用 TreeMap,为什么不直接使用 TreeMap。

根据速度要求,您也可以使用Trie。但是,如果TreeMap足够快,则没有实现其中之一的必要。

考虑向数据结构添加或删除的频率。如果频率很高,TreeMap 就不是理想的选择。除了搜索现有条目的 nLn 外,还需要经常重新平衡。

另一方面,哈希结构在内存上有些浮华(过度分配)。如果你能接受这一点,那就选择哈希结构,并在需要时进行排序。

这是一个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;
    }
}

为什么不使用TreeSet?

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

从您的问题描述中,似乎您需要一个Set,我不明白您需要将哪些键和值进行映射。

这个类实现了Set接口,由TreeMap实例支持。这个类保证排序后的集合将根据元素的自然顺序(参见Comparable)或在集合创建时提供的比较器,根据使用哪个构造函数而按升序元素顺序排序。





相关问题
热门标签