CODEWITHSUNDEEP
java
zearthur99
zearthur99

Reputation: 111

Obtain key of a hashmap with a range of numbers as value

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

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

The first thought that came in my mind was achive this with 15 if/else if statements or with the switch statement. But in my view, this wouldn't be very elegant and practical.

Is there any other way to do this?

Upvotes: 5

Views: 1251

Answers (3)

Bohemian
Bohemian

Reputation: 424993

A Map is not the appropriate data structure. Use a TreeSet instead:

TreeSet<Float> numbers = new TreeSet<>();
// populate the set with your numbers, in any order, then

int index = numbers.headSet(n).size() + 1;

This will perform very well: TreeSet finds the insertion point in O(log n) time (like a binary search) and the list returned is just a view (a new list is not created), so the whole operation is lightweight.

Also note that the elements don't need to be added in any particular order - TreeSet internally maintains their order so searching is fast.

Here's some test code:

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

Upvotes: 4

fps
fps

Reputation: 34460

If values are always sorted, just use a common 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.

Please note that this approach supports duplicate values, and the index returned is 0-based.

Upvotes: 1

khachik
khachik

Reputation: 28693

Assuming data is your initial map and values are unique, you could 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());

Upvotes: 1

Related Questions