Sort Map Largest First Into List Efficiently?

Question

I have a ConcurrentMap<String, Integer>, and I'd like to get a List<String> from it with the String mapping to the largest Integer first, second largest second, etc.

Right now I have something along the lines of this:
Loop through the keySet of the map
In that loop, loop through a "sorted" List<String>
Keep looping until the key String's respective value is less than element i of the "sorted" List, and insert it.

Now this will work, but I doubt it's very efficient. Does Java 8 have any built in sorting algorithms that could help me here?

It would be easier to understand what you are doing if you showed your code rather than describe it. — assylias, Jul 01 '15 at 22:21
Sorry, I hadn't tested my code and didn't want to confuse people with possibly incorrect code — Rogue, Jul 01 '15 at 22:24
This is also a question in data structures. I would create an inverse-map - i.e. a map from Integer to List. Instead of using `HashMap`, in which the keys order is based on the hash function, I would use `TreeMap` - so the keys are actually sorted while they are inserted to the map. Then, I can iterate over the keys, already ordered by their values, I can get the list of strings that match that integer key, and I can concatenate it to a main list of strings, which is the final list you need — SomethingSomething, Jul 02 '15 at 12:42
Though you probably better use a built-in way to do it, like they described in the answers. My algorithm is reinventing the wheel — SomethingSomething, Jul 02 '15 at 12:45

assylias · Accepted Answer · 2015-07-02T12:33:28.210

9

Using streams, you could write it like this:

List<String> sorted = map.entrySet().stream()
                         .sorted(reverseOrder(comparing(Entry::getValue)))
                         .map(Entry::getKey)
                         .collect(toList());

Or as commented by Holger:

List<String> sorted = map.entrySet().stream()
                         .sorted(comparingByValue(reverseOrder()))
                         .map(Entry::getKey)
                         .collect(toList());

Note static imports:

import static java.util.Collections.reverseOrder;
import static java.util.Comparator.comparing;
import static java.util.stream.Collectors.toList;

I don't know if that's more efficient than your method but you can profile both and decide based on actual measurement.

edited Jul 02 '15 at 12:33

answered Jul 01 '15 at 22:24

assylias

321,522
82
660
783

Short and uses Java 8, perfect! Thank you! – Rogue Jul 01 '15 at 22:28
1

Sorry to bother you. I was wondering why `.sorted(Comparator.comparing(Map.Entry::getValue))` compiles/works fine, but `.sorted(Comparator.comparing(Map.Entry::getValue).reversed())` doesn't want to compile claiming that `getValue` expects no arguments, but it finds `Object`. It will also compile if I explicitly add generic types to `Map.Entry`. Do you think I should create separate question about this type inference problem, or did I missed some obvious fact which was already explained on already asked on SO question? – Pshemo Jul 01 '15 at 22:43
1

@Pshemo yes it's annoying - I think it's due to type inference not being very efficient with method chaining... See also: http://stackoverflow.com/questions/25172595/comparator-reversed-not-compiles-using-lambda – assylias Jul 01 '15 at 23:00
1

Thanks. That question is quite close to what I have. So for now I will probably use your way or `comparing(extractor, comparator)` like `.sorted(Comparator.comparing(Map.Entry::getValue, Comparator.reverseOrder()))` which also works fine without need to explicitly add generic types. – Pshemo Jul 01 '15 at 23:06
2

@Pshemo: [It’s even easier](http://docs.oracle.com/javase/8/docs/api/java/util/Map.Entry.html#comparingByValue-java.util.Comparator-): `.sorted(comparingByValue(reverseOrder()))` – Holger Jul 02 '15 at 08:24

score 1 · Answer 2 · answered Jul 01 '15 at 22:24

Yes, it does. You could do something like this:

ConcurrentMap<String, Integer> map = /* something */;

// entrySet just returns a view of the entries, so copy it into a new List
List<Map.Entry<String, Integer>> entries = new ArrayList<>(yourMap.entrySet());

// sort entries by their int values
Collections.sort(entries, (entry1, entry2) -> Integer.compare(entry1.getValue(), entry2.getValue()));

// copy just the keys into a new List
List<String> result = new LinkedList<>();
for (Map.Entry<String, Integer> entry : entries) {
  result.add(entry.getKey());
}

score 0 · Answer 3 · answered Jul 01 '15 at 22:34

import java.util. TreeSet;

import java.util.Set; import java.util.concurrent.ConcurrentHashMap;

public class Test {

public static void main(String[] args){
    ConcurrentHashMap< String, Integer> map = new ConcurrentHashMap<String , Integer>();
    map.put("Fish", 1);
    map.put("Bird", 100);
    map.put("Reptile", 2);
    map.put("Mammal", 10);
    TreeSet <Integer> sortedList = new TreeSet <Integer>(map.values());
    for(Integer i :sortedList){
        System.out.println(i);
    }
}

}

Sort Map Largest First Into List Efficiently?

3 Answers3