Finding the n largest values in a hashmap

Question

I have a hashmap containing <String, integer>, with entries such as:

("a",2)
("ab", 3)
("c",5) etc..

I have seen questions where they find the single largest value and store it in another hashmap, but how would I be able to loop that so that the "n" largest numbers can be found and put in the result hash map

e.g for the above hashmap entries, if n was 2, it would find the 2 largest values and put in the result hashmap

    ("ab", 3)
    ("c", 5)

Thank you very much in advances.

Welcome to Stackoverflow. The purpose of this forum is to help you learn how to program, not do the work for you (except for fun maybe) What have you tried, and what are you having trouble with? — Peter Lawrey, May 22 '14 at 11:46
@TAsk : actually I don't find this is a duplicate of the question you're marked. This question has less to relate with Map iteration, actually it is more related on how find the N largest values within a collection of values. — WoDoSc, May 22 '14 at 12:25
Take a look at this: http://www.java2s.com/Code/Java/Collections-Data-Structure/Sortsmapbyvaluesinascendingorder.htm, you want to get the entry set, sort it, and then add the first n items of the sorted entry sets to a new map — cowls, May 22 '14 at 12:53

WoDoSc · Answer 1 · 2014-05-22T12:31:31.483

Probably this is not the most efficient way to do, but it should solve your problem:

static HashMap<String, Integer> nLargest(HashMap<String, Integer> map, int n) { //map and n largest values to search for

    Integer value;
    ArrayList<String> keys = new ArrayList<>(n); //to store keys of the n largest values
    ArrayList<Integer> values = new ArrayList<>(n); //to store n largest values (same index as keys)
    int index;
    for (String key : map.keySet()) { //iterate on all the keys (i.e. on all the values)
        value = map.get(key); //get the corresponding value
        index = keys.size() - 1; //initialize to search the right place to insert (in a sorted order) current value within the n largest values
        while (index >= 0 && value > values.get(index)) { //we traverse the array of largest values from smallest to biggest
            index--; //until we found the right place to insert the current value
        }
        index = index + 1; //adapt the index (come back by one)
        values.add(index, value); //insert the current value in the right place
        keys.add(index, key); //and also the corresponding key
        if (values.size() > n) { //if we have already found enough number of largest values
            values.remove(n); //we remove the last largest value (i.e. the smallest within the largest)
            keys.remove(n); //actually we store at most n+1 largest values and therefore we can discard just the last one (smallest)
        }
    }
    HashMap<String, Integer> result = new HashMap<>(values.size());
    for (int i = 0; i < values.size(); i++) { //copy keys and value into an HashMap
        result.put(keys.get(i), values.get(i));
    }
    return result;
}

I hope this will help you.

Finding the n largest values in a hashmap

1 Answers1