how to get key of the most nearest value of a given double value from an existing map <String double>

Question

Since I need to get the key values of double value I' m using BiMap.

BiMap<String,Double>mapObj = HashBiMap.create();
mapObj.put("a1",3.58654);
mapObj.put("a2",4.1567);
mapObj.put("a3",4.2546);

For a particular value like 4.0156 I must get the key value a2.. that is if,

Double value=4.0156; 
mapObj.inverse().get(value)=a2 

I tried many ways but its getting always null, since there is no exact match. please anyone help me... if I have chosen a wrong way please correct it because I'm new in Java.

Answer 1

Iterate through an Entry set like this should do the trick.

String nearestKey = null;
Double nearestValue = null;
for(Entry<String,Double> e : map.entrySet()){
    //if e.getValue() is nearer than prev nearestValue
    // nearestKey = e.getKey();
    // nearestValue = e.getValue();
}

You just have to write a function to determine if the key is nearer than the previous and update the variables.

Answer 2

You will have to iterate through all the key-value pairs and select the one with the value which is nearest to the value you're looking for.

public String searchClosest(Map<String,Double> map, double value)
{
    double minDistance = Double.MAX_VALUE;
    String bestString = null;

    for (Map.Entry<String,Double> entry : map.entrySet()) {
        double distance = Math.abs(entry.getValue() - value);
        if (distance < minDistance) {
            minDistance = distance;
            bestString = entry.getKey();
        }
    }

    return bestString;
}

Answer 3

Convert to a sorted map with the keys and values inverted and applying the following method should work.

 private static Double getClosest(TreeMap<Double, String> mySet, Double d) {
        if (mySet.ceilingKey(d) != null && mySet.floorKey(d) != null){
            if( Math.abs(d - mySet.ceilingKey(d)) < Math.abs(d - mySet.floorKey(d)) )
                return mySet.ceilingKey(d);
            else
                return mySet.floorKey(d);
        }
        else if (mySet.ceilingKey(d) == null && mySet.floorKey(d) != null) {
            return mySet.floorKey(d);
        } else if (mySet.ceilingKey(d) != null && mySet.floorKey(d) == null) {
            return mySet.ceilingKey(d);
        } else
            return null;
    }

Answer 4

First: you probably want to have:

Map<String, Double> mapObj = HashMap<>();
mapObj.put("a1", 3.58654);
mapObj.put("a2", 4.1567);
mapObj.put("a3", 4.2546);
mapObj.put("a4", 4.1567); // Repeated value

And then you want a reverse lookup with nearest value.

For that it would be nice to have all entries sorted by value. This cannot be a Set because of a value occuring multiple times.

List<Map.Entry<String, Double>> entries = new ArrayList<>(mapObj.entrySet());
Comparator<Map.Entry<String, Double>> cmp = (lhs, rhs) ->
    Double.compare(lhs.getValue(), rhs.getValue());
Collections.sort(entries, cmp);

I know of no data structure in Java that combines this. Though there probably is. To not lose information I use the Map.Entry, key-value pair. That needs a Comparator on the values. For shortness, I have borrowed from Java 8 syntax here.

Now search:

Map.Entry<String, Double> nearest(double value) {
    int index = Collections.binarySearch(entries, cmp);
    if (index < 0) { // Not found
        index = -index + 1; // The insertion position
        Map.Entry<String, Double> before = index != 0 ? entries.get(i - 1) : null;
        Map.Entry<String, Double> after = index < entries.size() ?
                entries.get(i) : null;
        if (before == null && after == null) {
            return null;
        } else if (before == null) {
            return after;
        } else if (after == null) {
            return before;
        }
        return value - before.getValue() < after.getValue() - value ? before : after;
    }
    return entries.get(index);
}

To find a sub list of values inside a delta, one would need to use the index.

Now every search costs ²log N, which is acceptable.