Sorting a collection of HashSets

Question

I apologize if this is a duplicate, but I couldn't find any answer that specifically answered this particular issue.

I have a HashMap that contains a string key paired with a Set value. I want to sort the values in my map based on the length of the set. Consider:

HashMap<String, Set<String>> myMap;

Contains:

{"A", {"Dukmerriot", "King", "Pumpkin"}}  
{"B", {"Steve"}}
{"C", {"Jib", "Jab", "John", "Julie"}}
{"D", {"Apple", "Amy", "Unicorn", "Charlie", "Raptor"}}
{"E", {}}

I want to be able to get the list {"D", "C", "A", "B", E"} (which designates the order of the sets from largest to smallest) from myMap efficiently.

Is there a way to sort a collection of sets based on their length other than creating a wrapper class that implements Set and overriding the compareTo method?

EDIT: I should specify that I don't NEED to use a HashMap to maintain this collection. I could use a TreeMap or something, but I'm not sure if that's possible since Set doesn't implement Comparable.

_"I want to be able to get the set `{"D", "C", "A", "B", E"}` from `myMap` efficiently."_ Did you mean a list? Sets are unordered, so you might as well just use `myMap.keySet()` there. — Matt Ball, Feb 25 '13 at 20:36
Yeah, sorry. Essentially I just want that list in that order. — Devin, Feb 25 '13 at 20:38
Look at http://stackoverflow.com/questions/8119366/sorting-hashmap-by-values — VAV, Feb 25 '13 at 20:41

Matt Ball · Answer 1 · 2013-02-25T21:22:30.343

Is there a way to sort a collection of sets based on their length other than creating a wrapper class that implements Set and overriding the compareTo method?

That's a completely viable way to do it. You could also use a Comparator:

List<Set<String>> mySets = new ArrayList<>(myMap.values());
mySets.sort(new Comparator<Set<String>>() {
    @Override
    public int compare(Set<String> a, Set<String> b) {
        return Integer.compare(a.size(), b.size());
    }
});

...but now you've lost the corresponding key for each set. So let's just sort the map entries!

List<Entry<String, Set<String>>> entries = new ArrayList<>(myMap.entrySet());
entries.sort(new Comparator<Entry<String, Set<String>>>() {
    @Override
    public int compare(Entry<String, Set<String>> a,Entry<String, Set<String>> b) {
        return Integer.compare(a.getValue().size(), b.getValue().size());
    }
});

and you can now "easily" get the keys:

List<String> sortedKeys = new ArrayList<>();
for (Entry<String, Set<String>> e : entries) {
    sortedKeys = e.getKey();
}

This list won't be a live view of the keys, but is going to be your best bet if that's an acceptable restriction.

do you mean "entries.sort(...)" instead of mySets? – Devin Feb 25 '13 at 21:21 — Devin, Feb 25 '13 at 21:21

score 2 · Accepted Answer · answered Feb 25 '13 at 21:11

final Map<String, Set<String>> map = new HashMap<>();

map.put("A", ImmutableSet.of("Dukmerriot", "King", "Pumpkin"));
map.put("B", ImmutableSet.of("Steve"));
map.put("C", ImmutableSet.of("Jib", "Jab", "John", "Julie"));
map.put("D", ImmutableSet.of("Apple", "Amy", "Unicorn", "Charlie", "Raptor"));
map.put("E", new HashSet<String>());

List<String> keys = new ArrayList<>(map.keySet());
Collections.sort(keys, new Comparator<String>() {

    @Override
    public int compare(String o1, String o2) {
        return Integer.valueOf(map.get(o2).size()).compareTo(map.get(o1).size());
    }
});

for (String key : keys) {
    System.out.println(key);
}

Prints

D
C
A
B
E

I used Google Guava's ImmutableSet, just to make the code short. You might want to look at their Multimap as you may find it useful.

score 0 · Answer 3 · answered Feb 25 '13 at 20:36

0

HashMaps are not sortable. They are optimized for looking values up by the keys.

answered Feb 25 '13 at 20:36

Rylander

19,449
25
93
144

poitroae · Answer 4 · 2013-02-25T20:53:52.057

0

Since HashMaps don't maintain an internal order, you cannot do it like that. The best thing you can do there is getting all the values with map.values(), iterate over it and see which one's the longest.

HashMap<T, V> map = ...
Collection<V> values = map.values();

int maxLen = Integer.MIN_VALUE;
Set<String> winner = null;
for(V v : values) {
   if(v.size() > maxLen) {
     winner = v;
   }
}

T and V are arbitrary types. In your case, T equals String, V equals Set.

edited Feb 25 '13 at 20:53

answered Feb 25 '13 at 20:40

poitroae

21,129
10
63
81

This is not sorting, this is determining the keyed value with the largest size. – Perception Feb 25 '13 at 20:51
Just a heads up (since I deleted my answer) my implementation neither sorted nor copied values from the map. It used a `TreeSet`, not a `TreeMap`. – Matt Ball Feb 25 '13 at 20:52
This would give me the longest one, but in order to get the sorted list, this would be an n^2 operation. I can implement a log(n) sorting algorithm for the sets while maintaining the correct order of the keys, but I was just wondering if there was a simpler way that Java gave you. – Devin Feb 25 '13 at 20:53

Rob Audenaerde · Answer 5 · 2013-02-25T21:05:53.107

I would create a custom object to hold both the Set and the String. Let the class implement Comparable, implement is usign the set size. Then just use a List to fill it up and Collections.sort() to get the desired result.

class A implements Comparable {
    Set set;
    String string;

    ...constructor etc....

    @Override
    public int compare(A a,A b) {
        return Integer.compare(a.set.size(), b.set.size());
    }
}

Sorting a collection of HashSets

5 Answers5