0

我创建了一个哈希图来存储多个文件中出现的单词，例如 10,000 个文本文件。然后我想从 hashmap 中对它们进行排序并打印前 10 个单词。Hashmap 定义为，

      Hashtable <String, Integer> problem1Counter = new Hashtable<String, Integer> ();

当我将文件保持在 1000 左右时，我能够使用这样的简单排序获得前十个单词，

String[] keysProblem1 = (String[]) problem1Counter.keySet().toArray(new String[0]);
  Integer [] valuesProblem1 =  (Integer[])problem1Counter.values().toArray(new Integer[problem1Counter.size()]);

诠释 kk = 0; 字符串 ii = null;

    for (int jj = 0; jj < valuesProblem1.length ; jj++){
        for (int bb = 0; bb < valuesProblem1.length; bb++){
            if(valuesProblem1[jj] < valuesProblem1[bb]){
            kk = valuesProblem1[jj];
            ii = keysProblem1[jj];
            valuesProblem1[jj] = valuesProblem1[bb];
            keysProblem1[jj] = keysProblem1[bb];
            valuesProblem1 [bb] = kk;
            keysProblem1 [bb] = ii;}}}

因此，当 hashtable 的值超过 553685 时，上述方法不起作用。那么任何人都可以建议并展示一种更好的方法来对它们进行排序吗？我是 java 的新手，但曾在 actionscript 中工作过，所以我有点舒服。谢谢。

4

3 回答 3

4

当您分开并尝试使每个索引处的事物保持连接时，您的问题就开始keys了values。相反，让它们保持耦合，并对Map.Entryjava 给你的对象进行排序。

我不确定这是否编译，但它应该给你一个开始。

// HashMap and Hashtable are very similar, but I generally use HashMap.
HashMap<String, Integer> answers = ...

// Get the Key/Value pairs into a list so we can sort them.
List<Map.Entry<String, Integer>> listOfAnswers =
    new ArrayList<Map.Entry<String, Integer>>(answers.entrySet());

// Our comparator defines how to sort our Key/Value pairs.  We sort by the
// highest value, and don't worry about the key.
java.util.Collections.sort(listOfAnswers,
    new Comparator<Map.Entry<String, Integer>>() {
        public int compare(
                Map.Entry<String, Integer> o1,
                Map.Entry<String, Integer> o2) {
            return o2.getValue() - o1.getValue();
        }
    });

// The list is now sorted.
System.out.println( String.format("Top 3:\n%s: %d\n%s: %d\n%s: %d", + 
        listOfAnswers.get(0).getKey(), listOfAnswers.get(0).getValue(), 
        listOfAnswers.get(1).getKey(), listOfAnswers.get(1).getValue(), 
        listOfAnswers.get(2).getKey(), listOfAnswers.get(2).getValue()));
于 2012-10-05T05:50:31.617 回答
3

为了更好地进行排序，我会这样做：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
    HashMap<String, Integer> counter = new HashMap<String, Integer>();

    // [... Code to populate hashtable goes here ...]
    // 

    // Extract the map as a list
    List<Map.Entry<String, Integer>> entries = new ArrayList<Map.Entry<String, Integer>>(counter.entrySet());

    // Sort the list of entries.
    Collections.sort(entries, new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Entry<String, Integer> first, Entry<String, Integer> second) {
        // This will give a *positive* value if first freq < second freq, zero if they're equal, negative if first > second.
        // The result is a highest frequency first sort.
        return second.getValue() - first.getValue();
        }
    });

    // And display the results
    for (Map.Entry<String, Integer> entry : entries.subList(0, 10))
        System.out.println(String.format("%s: %d", entry.getKey(), entry.getValue()));
    }

}

编辑解释为什么这样做

您的原始算法看起来像选择排序的变体，它是一个 O(n^2) 算法。你的变种也做了很多额外的交换，所以很慢。

作为 O(n^2)，如果将问题大小乘以 10，则运行时间通常需要 100 倍。对 50 万个元素进行排序需要进行 2500 亿次比较，其中许多会导致交换。

Collections#sort 中的内置排序算法是Merge Sort的闪电般快速的变体，它在 O(n.log(n)) 时间内运行。这意味着每次将问题大小乘以 10，只需要大约 30 倍的时间。对 50 万个元素进行排序只需要进行大约 1000 万次比较。

这就是为什么有经验的开发人员会建议您尽可能使用库函数。编写自己的排序算法对学习很有帮助，但要实现一个与库中的算法一样快速和灵活的算法需要做很多工作。

于 2012-10-05T05:57:48.127 回答
1
  • 创建一个实现 Comparable 的内部类 Word
  • 覆盖 public int compareTo(Word w) 以使其使用出现次数
  • 创建一个 HashMap 大小的单词数组
  • 遍历 HashMap 填充数组
  • 在数组上调用 Arrays.sort

或者，由于您只需要前 10 名，因此您可以遍历您的单词并在进行过程中维护前 10 名列表。

于 2012-10-05T05:46:13.677 回答