Sorting HashMap by key

Question

hello I need to implement a method that receives a HashMap and sorts (mergeSort) it's values by key (without using TreeMap, SortedMap or Collections.Sort or use any sort solutions from JAVA Packages). my problem is dealing with the wildcard Types... this is my implementation (that returns compilation errors because of wildcards use)

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;
    }

I appreciate your help!

Answer 1

If all you have to do is meet a method contract, you can do this.

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

This will sort the keys and return a subclass of HashMap. The design of this method is broken, but sometimes you can't change things.

---

If you are sorting a map, you should be using a SortedMap like TreeMap. hashmap doesn't retain an order so using it for a merge sort is not possible. Using a merge sort for a TreeMap is redundant.

You cannot assume that ? is a Comparable. You can write something like.

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

As you can see this is shorter and simpler than your approach. Is this homework? Do you reall need to use a merge sort?

The problem you have is that you cannot return a HashMap as it doesn't keep the order, adn you cannot return a TreeMap because it will sort the keys for you making anything else you redundant. For this task you can only return a LinkedHashMap as it does retain order, without doing the sorting for you.

---

here is an example using LinkedHashMap. Note it doesn't create copies of Maps as it goes, it creates a single array and merge sorts portions of it until its completely sorted.

Note: I use TreeMap as a SortedMap to show its sorted correctly. ;)

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++;
        }
    }
}

prints

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}

Answer 2

Like other commenters I would suggest reading up on the subject of generics in Java. What you did in merge is using wildcards on the result HashMap

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

When you put wildcards on it, you are basically saying "I will only be reading from this". Later on you trying to push something in

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

The compiler will say "Hey, you just told me you would only read and now you want to put something in... FAIL

Then it generates your compile time errors.

Solution

Don't put wildcards on collections you will modify.

Answer 3

Why are you always using ?. Give the kids a name like Key or Value.

Edit: You should work through this tutorial fist: Lesson: Generics

Answer 4

Here is a method that sorts a Map by its keys. It makes use of the Collections.sort(List, Comparator) method.

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;
}