Finding the highest-n values in a Map

Question

I have a large map of String->Integer and I want to find the highest 5 values in the map. My current approach involves translating the map into an array list of pair(key, value) object and then sorting using Collections.sort() before taking the first 5. It is possible for a key to have its value updated during the course of operation.

I think this approach is acceptable single threaded, but if I had multiple threads all triggering the transpose and sort frequently it doesn't seem very efficient. The alternative seems to be to maintain a separate list of the highest 5 entries and keep it updated when relevant operations on the map take place.

Could I have some suggestions/alternatives on optimizing this please? Am happy to consider different data structures if there is benefit.

Thanks!

Answer 1

Well, to find the highest 5 values in a Map, you can do that in O(n) time where any sort is slower than that.

The easiest way is to simply do a for loop through the entry set of the Map.

for (Entry<String, Integer> entry: map.entrySet()) {
    if (entry.getValue() > smallestMaxSoFar) 
        updateListOfMaximums();
}

Answer 2

You could use two Maps:

// Map name to value
Map<String, Integer> byName

// Maps value to names
NavigableMap<Integer, Collection<String>> byValue

and make sure to always keep them in sync (possibly wrap both in another class which is responsible for put, get, etc). For the highest values use byValue.navigableKeySet().descendingIterator().