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

You could do it with the google collections BiMap, assuming that the Floats are unique.

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

Answer 3

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 4

You have to do it in steps:

1. Get the Collection<V> of values from the Map
2. Sort the values
3. Choose the index of the nth smallest

Think about how you want to handle ties.

Answer 5

If you regularly need to get the key of the nth item, consider:

• using a TreeMap, which efficiently keeps keys in sorted order
• then using a double map (i.e. one TreeMap mapping integer > float, the other mapping float > integer)

You have to weigh up the inelegance and potential risk of bugs from needing to maintain two maps with the scalability benefit of having a structure that efficiently keeps the keys in order.

You may need to think about two keys mapping to the same float...

P.S. Forgot to mention: if this is an occasional function, and you just need to find the nth largest item of a large number of items, you could consider implementing a selection algorithm (effectively, you do a sort, but don't actually bother sorting subparts of the list that you realise you don't need to sort because their order makes no difference to the position of the item you're looking for).