Sorting a HashMap, while keeping duplicates

Question

I'm trying to sort a HashMap in two ways. The default way: alphabetically by the value, the second way: numerically by the key, with the higher number being at the top. I have searched around but can't find anything on the subject, and what I do find, doesn't work. If it's not possible to sort both of them (I want the person with the highest key at the top, decreasing as people have lower keys, then alphabetically sort all of the rest (the people with 0 as their key).

Here's what I've tried so far:

private HashMap<String, Integer> userGains = new HashMap<String, Integer>();

public void sortGains(int skill, int user) {
    userGains.put(users.get(user).getUsername(), users.get(user).getGainedExperience(skill));
    HashMap<String, Integer> map = sortHashMap(userGains);
    for (int i = 0; i < map.size(); i++) {
        Application.getTrackerOutput().getOutputArea(skill).append(users.get(user).getUsername() + " gained " + map.get(users.get(user).getUsername()) + "  experience in " + getSkillName(skill) + ".\n");
    }
}

public LinkedHashMap<String, Integer> sortHashMap(HashMap<String, Integer> passedMap) {
    List<String> mapKeys = new ArrayList<String>(passedMap.keySet());
    List<Integer> mapValues = new ArrayList<Integer>(passedMap.values());
    LinkedHashMap<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();

    Collections.sort(mapValues);
    Collections.sort(mapKeys);

    Iterator<Integer> it$ = mapValues.iterator();
    while (it$.hasNext()) {
        Object val = it$.next();
        Iterator<String> keyIt = mapKeys.iterator();
        while (keyIt.hasNext()) {
            Object key = keyIt.next();
            String comp1 = passedMap.get(key).toString();
            String comp2 = val.toString();
            if (comp1.equals(comp2)) {
                passedMap.remove(key);
                mapKeys.remove(key);
                sortedMap.put((String) key, (Integer) val);
                break;
            }
        }
    }
    return sortedMap;
}

Since you cannot run that here is an SSCCE:

private HashMap<String, Integer> userGains = new HashMap<String, Integer>();

private Object[][] testUsers = { { "Test user", 15 }, { "Test", 25 }, { "Hello", 11 }, { "I'm a user", 21 }, { "No you're not!", 14 }, { "Yes I am!", 45 }, { "Oh, okay.  Sorry about the confusion.", 0 }, { "It's quite alright.", 0 } };

public static void main(String[] arguments) {
    new Sorting().sortGains();
}

public void sortGains() {
    for (Object[] test : testUsers) {
        userGains.put((String) test[0], (Integer) test[1]);
    }
    HashMap<String, Integer> map = sortHashMap(userGains);
    for (int i = 0; i < map.size(); i++) {
        System.out.println(testUsers[i][0] + " gained " + map.get(testUsers[i][0]) + "  experience.");
    }
}

public LinkedHashMap<String, Integer> sortHashMap(HashMap<String, Integer> passedMap) {
    List<String> mapKeys = new ArrayList<String>(passedMap.keySet());
    List<Integer> mapValues = new ArrayList<Integer>(passedMap.values());
    LinkedHashMap<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();

    Collections.sort(mapValues);
    Collections.sort(mapKeys);

    Iterator<Integer> it$ = mapValues.iterator();
    while (it$.hasNext()) {
        Object val = it$.next();
        Iterator<String> keyIt = mapKeys.iterator();
        while (keyIt.hasNext()) {
            Object key = keyIt.next();
            String comp1 = passedMap.get(key).toString();
            String comp2 = val.toString();
            if (comp1.equals(comp2)) {
                passedMap.remove(key);
                mapKeys.remove(key);
                sortedMap.put((String) key, (Integer) val);
                break;
            }
        }
    }
    return sortedMap;
}

The output of the program is currently:

Test user gained 15  experience.
Test gained 25  experience.
Hello gained 11  experience.
I'm a user gained 21  experience.
No you're not! gained 14  experience.
Yes I am! gained 45  experience.
Oh, okay.  Sorry about the confusion. gained 0  experience.
It's quite alright. gained 0  experience.

When I need it to be:

Yes I am! gained 45  experience. // start numeric sorting here, by highest key.
Test gained 25  experience.
I'm a user gained 21  experience.
Test user gained 15  experience.
No you're not! gained 14  experience.
Hello gained 11  experience.
It's quite alright. gained 0  experience. // start alphabetical sorting here, if possible.
Oh, okay.  Sorry about the confusion. gained 0  experience.

Any insight?

Answer 1

This question approaches what you're trying to do, by sorting on value in a TreeMap. If you take the most voted answer and modify the Comparator to sort on value then key, it should give you what you want.

Effectively, you create a Comparator that has a field that points to the TreeMap (so it can look up values). And the TreeMap uses this Comparator. When items are added to the TreeMap, the Comparator looks up the values and does a comparison on

• if the value a < value b, return 1
• if the value a > value b, return -1
• if the key a < key b, return 1
• if the key a > key b, return -1
• otherwise, return 0

Copying a lot of code from that answer (with no checking to see if the code works, since it's just for the idea):

public class Main {

    public static void main(String[] args) {

        ValueComparator<String> bvc =  new ValueComparator<String>();
        TreeMap<String,Integer> sorted_map = new TreeMap<String,Integer>(bvc);
        bvc.setBase(sorted_map);

        // add items
        // ....

        System.out.println("results");
            for (String key : sorted_map.keySet()) {
            System.out.println("key/value: " + key + "/"+sorted_map.get(key));
        }
     }

}

class ValueComparator implements Comparator<String> {
    Map base;

    public setBase(Map<String,Integer> base) {
        this.base = base;
    }

    public int compare(String a, String b) {
        Integer value_a = base.get(a);
        Integer value_b = base.get(b);

        if(value_a < value_b) {
            return 1;
        }
        if(value_a>< value_b) {
            return -1;
        }
        return a.compareTo(b);
    }
}

Answer 2

You made a mistake in displaying the values.

HashMap<String, Integer> map = sortHashMap(userGains);
for (int i = 0; i < map.size(); i++) {
    System.out.println(testUsers[i][0] + " gained " + map.get(testUsers[i][0]) + "  experience.");
}

You need to display the map's values instead of the original array's values.

This should do:

HashMap<String, Integer> map = sortHashMap(userGains);
for (Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " gained " + entry.getValue() + "  experience.");
}

You only have to reverse the order. Further I recommend to declare against Map instead of HashMap or LinkedHashMap to avoid confusion by yourself and others. Also your sorting can simpler be done with a Comparable. Here's an improvement:

private Map<String, Integer> userGains = new HashMap<String, Integer>();

private Object[][] testUsers = { { "Test user", 15 }, { "Test", 25 }, { "Hello", 11 }, { "I'm a user", 21 }, { "No you're not!", 14 }, { "Yes I am!", 45 }, { "Oh, okay.  Sorry about the confusion.", 0 }, { "It's quite alright.", 0 } };

public static void main(String[] arguments) {
    new Sorting().sortGains();
}

public void sortGains() {
    for (Object[] test : testUsers) {
        userGains.put((String) test[0], (Integer) test[1]);
    }

    Map<String, Integer> map = createSortedMap(userGains);

    for (Entry<String, Integer> entry : map.entrySet()) {
        System.out.println(entry.getKey() + " gained " + entry.getValue() + "  experience.");
    }
}

public Map<String, Integer> createSortedMap(Map<String, Integer> passedMap) {
    List<Entry<String, Integer>> entryList = new ArrayList<Entry<String, Integer>>(passedMap.entrySet());

    Collections.sort(entryList, new Comparator<Entry<String, Integer>>() {

        @Override
        public int compare(Entry<String, Integer> e1, Entry<String, Integer> e2) {
            if (!e1.getValue().equals(e2.getValue())) {
                return e1.getValue().compareTo(e2.getValue()) * -1; // The * -1 reverses the order.
            } else {
                return e1.getKey().compareTo(e2.getKey());
            }
        }
    });

    Map<String, Integer> orderedMap = new LinkedHashMap<String, Integer>();

    for (Entry<String, Integer> entry : entryList) {
        orderedMap.put(entry.getKey(), entry.getValue());
    }

    return orderedMap;
}

Answer 3

It's not possible to sort a HashMap at all. By definition, the keys in a HashMap are unordered. If you want the keys of your Map to be ordered, then use a TreeMap with an appropriate Comparator object. You can create multiple TreeMaps with different Comparators if you want to access the same data multiple ways.