CODEWITHSUNDEEP
java
ThatGuy343
ThatGuy343

Reputation: 2424

Fastest way to arrange sort and print large HashMap?

Lets say i have a hashmap with about 40k values.

I need to get the top 10 keys with high values in descending order.

HashMap<String,Double> balances = new HashMap<String,Double>();

I know that I can get the highest balance easily by just looping and checking against the last value, but how can i get the top 10 efficiently without multiple loops?

Desired output:

1. <key> has balance of 500
2. <key> has balance of 400
3. <key> has balance of 300
4. <key> has balance of 200
5. <key> has balance of 100
6. <key> has balance of 50
7. <key> has balance of 45
8. <key> has balance of 40
9. <key> has balance of 30
10. <key> has balance of 10

Upvotes: 0

Views: 179

Answers (1)

nitishagar
nitishagar

Reputation: 9403

A min priority heap data structure would be handy in this case. You can just add elements to it in one go and every time the size crosses 10 remove the top element (min element).

Here is a basic implementation for the data structure HashMap:

import java.util.*;

public class Test
{
  public static void main(String[] args)
  {
    PriorityQueue<Map.Entry<String,Double>> queue = new PriorityQueue<>(10, new Comparator<Map.Entry<String, Double>>() {
      @Override
      public int compare(Map.Entry<String,Double> x, Map.Entry<String,Double> y)
      {
        if (x.getValue() < y.getValue())
        {
          return -1;
        }
        if (x.getValue() > y.getValue())
        {
          return 1;
        }
        return 0;
      }
    });

    HashMap<String,Double> balances = new HashMap<String,Double>();
    balances = Test.populateBalances(); // return the populated map

    for (Map.Entry<String, Double> entry : balances.entrySet()) {
      queue.add(entry);
      if (queue.size() > 10)
      queue.poll();
    }

    for (Map.Entry<String, Double> entry : queue)
      System.out.println(entry.getKey() + ":" + entry.getValue());
  }

  public static HashMap<String, Double> populateBalances() {
    HashMap<String,Double> balances = new HashMap<String,Double>();
    balances.put("test1", 1000.2);
    balances.put("test2", 200.3);
    balances.put("test3", 12000.2);
    balances.put("test4", 2050.3);
    balances.put("test5", 1034.2);
    balances.put("test6", 210.3);
    balances.put("test7", 10.2);
    balances.put("test8", 0.3);
    balances.put("test9", 13210.2);
    balances.put("test10", 2223.3);
    balances.put("test11", 101.2);
    balances.put("test12", 200.1);

    return balances;
  }

}

Upvotes: 1

Related Questions