nth item of hashmap

Question

HashMap selections = new HashMap<Integer, Float>();

How can i get the Integer key of the 3rd smaller value of Float in all HashMap?

Edit im using the HashMap for this

for (InflatedRunner runner : prices.getRunners()) {
       for (InflatedMarketPrices.InflatedPrice price : runner.getLayPrices()) {
           if (price.getDepth() == 1) {
             selections.put(new Integer(runner.getSelectionId()), new Float(price.getPrice()));
           }
         }                    

}

i need the runner of the 3rd smaller price with depth 1

maybe i should implement this in another way?

Answer 1

Michael Mrozek nails it with his question if you're using HashMap right: this is highly atypical scenario for HashMap. That said, you can do something like this:

• get the Set<Map.Entry<K,V>> from the HashMap<K,V>.entrySet().
• addAll to List<Map.Entry<K,V>>
• Collections.sort the list with a custom Comparator<Map.Entry<K,V>> that sorts based on V.
  • If you just need the 3rd Map.Entry<K,V> only, then a O(N) selection algorithm may suffice.

---

//after edit

It looks like selection should really be a SortedMap<Float, InflatedRunner>. You should look at java.util.TreeMap.

Here's an example of how TreeMap can be used to get the 3rd lowest key:

TreeMap<Integer,String> map = new TreeMap<Integer,String>();
map.put(33, "Three");
map.put(44, "Four");
map.put(11, "One");
map.put(22, "Two");

int thirdKey = map.higherKey(map.higherKey(map.firstKey()));
System.out.println(thirdKey); // prints "33"

Also note how I take advantage of Java's auto-boxing/unboxing feature between int and Integer. I noticed that you used new Integer and new Float in your original code; this is unnecessary.

---

//another edit

It should be noted that if you have multiple InflatedRunner with the same price, only one will be kept. If this is a problem, and you want to keep all runners, then you can do one of a few things:

• If you really need a multi-map (one key can map to multiple values), then you can:
  • have TreeMap<Float,Set<InflatedRunner>>
  • Use MultiMap from Google Collections
• If you don't need the map functionality, then just have a List<RunnerPricePair> (sorry, I'm not familiar with the domain to name it appropriately), where RunnerPricePair implements Comparable<RunnerPricePair> that compares on prices. You can just add all the pairs to the list, then either:
  • Collections.sort the list and get the 3rd pair
  • Use O(N) selection algorithm

Answer 2

Are you sure you're using hashmaps right? They're used to quickly lookup a value given a key; it's highly unusual to sort the values and then try to find a corresponding key. If anything, you should be mapping the float to the int, so you could at least sort the float keys and get the integer value of the third smallest that way