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?

score 5 · Answer 1 · answered Jan 13 '12 at 19:10

5

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.

answered Jan 13 '12 at 19:10

Ernest Friedman-Hill

80,601
10
150
186

Is there a way that I could sort the user's experience gained then? I have a **User** superclass which has all of the information in it, then an ArrayList of users, which contains all of them. – Aeterna Jan 13 '12 at 19:11
Of course, you can definitely sort an `ArrayList`; use `Collections.sort()` and provide a suitable `Comparator` implementation. – Ernest Friedman-Hill Jan 13 '12 at 19:14
Ah I see. I was looking earlier and found the provided method to sort a `HashMap` but I guess it was too good to be true. Does using `Collections.sort()` allow me to keep duplicates, or is that done within the `Comparator`? – Aeterna Jan 13 '12 at 19:19
OP's code works. His code has only mislead you because he declared a `LinkedHashMap` instance against the `HashMap` type. – BalusC Jan 13 '12 at 19:28
@Aeterna: you can't have duplicate keys in a `Map`. You *can* have a `Map` that maps keys to collections of some kind, so one key can have multiple values. This is often called a *multimap*. The Apache Commons collections library has some nice multimap classes. – Ernest Friedman-Hill Jan 13 '12 at 19:35
I'm not sure that I follow that. The output of what BalusC provided works with duplicate keys. – Aeterna Jan 13 '12 at 19:37

BalusC · Accepted Answer · 2012-01-13T19:33:03.017

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

Awesome! It's backwards though, do you know how could I reverse what the method outputs? Edit: Changing `Collections.sort(mapValues);` to `Collections.sort(mapValues, Collections.reverseOrder());` worked just fine :) Thanks again. — Aeterna, Jan 13 '12 at 19:28
Thanks, that's a lot easier to understand than the one I use! — Aeterna, Jan 13 '12 at 19:31

score 1 · Answer 3 · edited May 23 '17 at 12:12

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

Sorting a HashMap, while keeping duplicates

3 Answers3

Linked