的关键

Question

你好 我需要实现（或使用来自Java包任何形式的解决方案，而无需使用TreeMap中，为SortedMap或Collections.Sort）接收一个HashMap和排序（归并）的关键它的值的方法排序的HashMap 。 我的问题是处理通配符类型... 这是我实现（使用返回因为通配符的编译错误）

public HashMap<?, ?> mergeSort(HashMap<?, ?> map) { 
     if (map.size() < 1) { 
      return map; 
     } 
     // rounds downwards 
     int middle = map.size()/2; 
     int location = 0; 

     HashMap<?,?> mapLeft = new HashMap<?, ?>(); 
     HashMap<?,?> mapRight = new HashMap<?, ?>(); 
     // splitting map 
     for (Iterator<?> keyIter = map.keySet().iterator(); keyIter.hasNext();) { 
      if (location < middle) { 
       mapLeft.put(keyIter, map.get(keyIter)); 
      } else { 
       mapRight.put(keyIter, map.get(keyIter)); 
      } 
      location++; 
     } 
     // recursive call 
     mapLeft = mergeSort(mapLeft); 
     mapRight = mergeSort(mapRight); 
     return merge(mapLeft, mapRight); 
    } 

    public HashMap<?, ?> merge(HashMap<?, ?> mapLeft, HashMap<?, ?> mapRight) { 
     HashMap<?, ?> result = new HashMap<?, ?>(); 
     Iterator<?> keyLeftIter = mapLeft.keySet().iterator(); 
     Iterator<?> keyRightIter = mapRight.keySet().iterator(); 
     String keyLeft; 
     String keyRight; 
     while (keyLeftIter.hasNext()) { 
      keyLeft = keyLeftIter.next(); 
      while (keyRightIter.hasNext()) { 
       keyRight = keyRightIter.next(); 

       if (keyLeft.compareTo(keyRight) < 0) { 
        result.put(keyLeft, mapLeft.get(keyLeft)); 
        keyLeft = keyLeftIter.next(); 
       } else { 
        result.put(keyRight, mapRight.get(keyRight)); 
        keyRight = keyRightIter.next(); 
       } 
      } 
     } 
     return result; 
    } 

我感谢您的帮助！

Answer 1

与其他评论者一样，我建议您阅读Java中的泛型主题。你在做合并使用对结果的HashMap

HashMap<?, ?> result = new HashMap<?, ?>(); 

当你穿上它通配符通配符，你基本上是说：“我将只从这个读书”。后来你想在

result.put(keyLeft, mapLeft.get(keyLeft)); 

推的东西，编译器会说：“嘿，你只要告诉我，你会只读，现在你想要把东西... FAIL

然后生成您的编译时错误。

解决方案

不把收藏通配符，您将修改。

Answer 2

你为什么总是使用?。给孩子们一个名字，如Key或Value。

编辑：您应该通过本教程拳头工作：Lesson: Generics

Answer 3

下面是排序由它的键地图的方法。它使用Collections.sort(List, Comparator)方法。

static Map sortByKey(Map map) { 
    List list = new LinkedList(map.entrySet()); 
    Collections.sort(list, new Comparator() { 
      public int compare(Object o1, Object o2) { 
       return ((Comparable) ((Map.Entry) (o1)).getKey()) 
       .compareTo(((Map.Entry) (o2)).getKey()); 
      } 
    }); 

    Map result = new LinkedHashMap(); 
    for (Iterator it = list.iterator(); it.hasNext();) { 
     Map.Entry entry = (Map.Entry)it.next(); 
     result.put(entry.getKey(), entry.getValue()); 
    } 
    return result; 
} 

Answer 4

如果您只需要满足方法合同，就可以做到这一点。

public HashMap<?, ?> mergeSort(HashMap<?, ?> map) { 
    return new LinkedHashMap(new TreeMap(map)); 
} 

这将对键进行排序并返回HashMap的子类。这种方法的设计被打破，但有时你不能改变。

---

如果您正在对地图进行排序，您应该使用TreeMap等SortedMap。 hashmap不保留一个顺序，因此使用它来进行合并排序是不可能的。对TreeMap使用合并排序是多余的。

您不能假设?是一个可比较的。你可以写一些类似的东西。

public static <K extends Comparable<K>, V> SortedMap<K,V> sort(Map<K,V> map) { 
    return new TreeMap<K, V>(map); 
} 

正如您所看到的，这比您的方法更短更简单。这是功课吗？你真的需要使用合并排序吗？

你的问题是，你不能返回一个HashMap，因为它不保留顺序，并且你不能返回一个TreeMap，因为它会为你排序键，让你做任何其他的事情。对于这个任务，你只能返回一个LinkedHashMap，因为它保留了顺序，而不需要为你排序。

---

这里是一个使用LinkedHashMap的例子。请注意，它不会创建Maps的副本，它会创建单个数组并合并它的某些部分，直到它完全排序。

注意：我使用TreeMap作为SortedMap来显示其排序正确。 ;）

public static void main(String... args) throws IOException { 
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    for(int i=0;i<100;i++) 
     map.put((int)(Math.random()*1000), i); 
    System.out.println("Unsorted "+map); 
    System.out.println("Sorted "+sort(map)); 
    final String sortedToString = sort(map).toString(); 
    final String treeMapToString = new TreeMap<Integer, Integer>(map).toString(); 
    if (!sortedToString.equals(treeMapToString)) 
     System.out.println(sortedToString+" != \n"+treeMapToString); 
} 

public static <K extends Comparable<K>, V> Map<K, V> sort(Map<K, V> map) { 
    return mergeSort(map); 
} 

// a very bad design idea, but needed for compatibility. 
public static <K extends Comparable<K>, V> HashMap<K, V> mergeSort(Map<K, V> map) { 
    Map.Entry<K, V>[] entries = map.entrySet().toArray(new Map.Entry[map.size()]); 
    mergeSort0(entries, 0, entries.length); 
    HashMap<K, V> ret = new LinkedHashMap<K, V>(); 
    for (Map.Entry<K, V> entry : entries) 
     ret.put(entry.getKey(), entry.getValue()); 
    return ret; 
} 

private static <K extends Comparable<K>, V> void mergeSort0(Map.Entry<K, V>[] entries, int start, int end) { 
    int len = end - start; 
    if (len < 2) return; 
    int mid = (end + start) >>> 1; 
    mergeSort0(entries, start, mid); 
    mergeSort0(entries, mid, end); 
    // merge [start, mid) and [mid, end) to [start, end) 
    for(int p = start, l=start, r=mid; p < end && l < r && r < end; p++) { 
     int cmp = entries[l].getKey().compareTo(entries[r].getKey()); 
     if (cmp <= 0) { 
      l++; 
      // the entry is in the right place already 
     } else if (p != r) { 
      // we need to insert the entry from the right 
      Map.Entry<K,V> e= entries[r]; 
      // shift up. 
      System.arraycopy(entries, p, entries, p+1, r - p); 
      l++; 
      // move down. 
      entries[p] = e; 
      r++; 
     } 
    } 
} 

打印

Unsorted {687=13, 551=0, 2=15, 984=3, 608=6, 714=16, 744=1, 272=5, 854=9, 96=2, 918=18, 829=8, 109=14, 346=7, 522=4, 626=19, 495=12, 695=17, 247=11, 725=10} 
Sorted {2=15, 96=2, 109=14, 247=11, 272=5, 346=7, 495=12, 522=4, 551=0, 608=6, 626=19, 687=13, 695=17, 714=16, 725=10, 744=1, 829=8, 854=9, 918=18, 984=3}