Get a key from a hash map with a range of numbers as a value

Question

I have a HashMap<Integer, Float> with entries:

  1 -> 0.127 2 -> 0.167 3 -> 0.207 4 -> 0.247 5 -> 0.237 6 -> 0.327 7 -> 0.367 8 -> 0.407 9 -> 0.447 10 -> 0.487 11 -> 0.527 12 -> 0.567 13 -> 0.607 14 -> 0.647 15 -> 0.652 

Suppose I want a key to Float 0.465 (which is not an existing value). 0.465 is between 0.447 and 0.487 , so I would like to get key 10 .

The first thought that came to my mind was achieved using the 15 if / else if commands or the switch statement. But, in my opinion, this would not be very elegant and practical.

Is there any other way to do this?

Answer 1

A map is not an appropriate data structure. Use TreeSet :

 TreeSet<Float> numbers = new TreeSet<>(); // populate the set with your numbers, in any order, then int index = numbers.headSet(n).size() + 1; 

This will be very good: TreeSet finds the insertion point in O (log n) time (for example, binary search), and the returned list is just a view (no new list is created), so the whole operation is easy.

Also note that the elements do not need to be added in any particular order - the TreeSet internally maintains its order, so the search is quick.

---

Here are some test codes:

 TreeSet<Float> numbers = new TreeSet<>(Arrays.asList( 0.607F, 0.647F, 0.127F, 0.167F, 0.207F, 0.247F, 0.237F, 0.327F, 0.367F, 0.407F, 0.447F, 0.487F, 0.527F, 0.567F, 0.652F)); 

Output:

 10 

Answer 2

Assuming data is your original map, and the values ​​are unique, you can do:

 java.util.NavigableMap<Double, Integer> reverseMap = new java.util.TreeMap<>(); for(java.util.Map.Entry<Double, Integer> entry : data.entrySet()) { reverseMap.put(entry.getValue(), entry.getKey()); } System.out.println(reverseMap.ceilingEntry(0.465).getValue()); 

Answer 3

If the values ​​are always sorted, just use a shared array:

 double[] values = {0.127, ..., 0.652}; 

And then call the Arrays.binarySearch() method, which returns the index of the value that is immediately greater than the given value.

Note that this approach supports duplicate values, and the return index is 0-based .