java - 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

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 2log N, which is acceptable.