按键对HashMap 进行排序
你好我需要实现一个接收HashMap的方法,并按键排序(mergeSort)它的值(不使用TreeMap,SortedMap或Collections.Sort或使用JAVA包中的任何排序解决方案) 。 我的问题是处理通配符类型…这是我的实现(由于使用通配符而返回编译错误)
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; }
我感谢您的帮助!
像其他评论者一样,我建议阅读Java中的generics主题。 您在合并中所做的是在结果HashMap上使用通配符
HashMap, ?> result = new HashMap, ?>();
当你把通配符放在上面时,你基本上是在说“我只会读这个”。 后来你试图推进一些东西
result.put(keyLeft, mapLeft.get(keyLeft));
编译器会说“嘿,你刚刚告诉我你只会阅读,现在你想把东西放进去……失败
然后它会生成编译时错误。
解
不要在要修改的集合上放置通配符。
如果您所要做的就是满足方法合同,那么您可以这样做。
public HashMap, ?> mergeSort(HashMap, ?> map) { return new LinkedHashMap(new TreeMap(map)); }
这将对键进行排序并返回HashMap的子类。 这种方法的设计被打破了,但有时你无法改变事物。
如果要对地图进行排序,则应使用类似TreeMap的SortedMap。 hashmap不保留订单,因此无法使用它进行合并排序。 对TreeMap使用合并排序是多余的。
你不能假设?
是一个可比较的。 你可以写类似的东西。
public static , V> SortedMap sort(Map map) { return new TreeMap(map); }
正如您所看到的,这比您的方法更简单,更简单。 这是家庭作业吗? 你还需要使用合并排序吗?
你遇到的问题是你不能返回一个HashMap,因为它不能保持顺序,并且你不能返回一个TreeMap,因为它会为你做任何其他冗余的事情对键进行排序。 对于此任务,您只能返回LinkedHashMap,因为它会保留顺序,而不会为您进行排序。
这是使用LinkedHashMap的示例。 请注意,它不会创建地图的副本,它会创建一个单独的数组并合并对其中的部分进行排序,直到完全排序。
注意:我使用TreeMap作为SortedMap来正确显示其排序。 ;)
public static void main(String... args) throws IOException { Map map = new HashMap(); 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(map).toString(); if (!sortedToString.equals(treeMapToString)) System.out.println(sortedToString+" != \n"+treeMapToString); } public static , V> Map sort(Map map) { return mergeSort(map); } // a very bad design idea, but needed for compatibility. public static , V> HashMap mergeSort(Map map) { Map.Entry[] entries = map.entrySet().toArray(new Map.Entry[map.size()]); mergeSort0(entries, 0, entries.length); HashMap ret = new LinkedHashMap(); for (Map.Entry entry : entries) ret.put(entry.getKey(), entry.getValue()); return ret; } private static , V> void mergeSort0(Map.Entry[] 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 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}
你为什么一直在使用?
。 给孩子一个像Key
或Value
这样的名字。
编辑:您应该完成本教程: 课程:generics
这是一种通过键对Map进行排序的方法。 它使用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; }