Get top 10 values in hash map

Question

I am trying to figure out how could I get the top 10 values from the HashMap. I was initially trying to use the TreeMap and have it sort by value and then take the first 10 values however it seems that that is not the option, as TreeMap sorts by key.

I want to still be able to know which keys have the highest values, the K, V of the map are String, Integer.

Solution 1

Maybe you should implement the Comparable Interface to your value objects stored in the hashmap. Then you can create a array list of all values:

List<YourValueType> l = new ArrayList<YourValueType>(hashmap.values());
Collection.sort(l);
l = l.subList(0,10);

Regards

Solution 2

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class Testing {

    public static void main(String[] args) {

        HashMap<String,Double> map = new HashMap<String,Double>();
        ValueComparator bvc =  new ValueComparator(map);
        TreeMap<String,Double> sorted_map = new TreeMap<String,Double>(bvc);

        map.put("A",99.5);
        map.put("B",67.4);
        map.put("C",67.4);
        map.put("D",67.3);

        System.out.println("unsorted map: "+map);

        sorted_map.putAll(map);

        System.out.println("results: "+sorted_map);
    }
}

class ValueComparator implements Comparator<String> {

    Map<String, Double> base;
    public ValueComparator(Map<String, Double> base) {
        this.base = base;
    }

    // Note: this comparator imposes orderings that are inconsistent with equals.    
    public int compare(String a, String b) {
        if (base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }
}

Solution 3

I am afraid you'll have to iterate over the entire map. Heap is a commonly-used data structure for finding top K elements, as explained in this book.

Comments

[jlordo]

This will only work if the value type Foo implements Comparable<Foo> and you don't use the raw type of list.

[aymeric]

I would have put the raw type if the OP specified it in his question :)

[Tohmas]

Oh wow, I think that might just do it, going to give it a shot now,THANKS!

[Rushi]

@Biswajit, can you explain me the complexity of this code? Your code is working perfectly and its very easy approach, just wanted to calculate the complexity of this code....

[Awesome_girl]

@Biswajit, you code is great, but how do you ensure the size of TreeMap is 10 at all times? Because you only want to TOP TEN right? Everytime you insert a key-value pair into the Tree Map, you need to check if the current size is greater than ten, if it is, you need to delete the smallest key-value pair in the TreeMap. How do you do this last part in the code? I didn't think people would answer my question here, so I asked a new question referencing this post Here

[Sebastian D'Agostino]

Quite good solution. I just needed something similar. Since you are only providing values, but I also needed the keys. I made a slight modification and added a Comparator in order to use the entry set. The comparator has to compare the entry values in descending order. List<Entry<String,Integer>> results = new ArrayList<>(hashmap.entrySet()); Collections.sort(results, new EntryComparator()); results = results.subList(0, 10);

[Sebastian D'Agostino]

I am adding it as another answer because it looks bad as a comment