Find The Closest Answer in HashMap

Question

I want to search for a key in a hashmap and find the nearest one to that key!

    HashMap<Long, Object> map = new HashMap<Long , Object>();

so basically I want to search for a long and if it didn't exist in the map find the nearest match to that long value! How can I do that!?

Thanx in advance

Solution 1

You cannot do it with HashMap without iterating over all of its keys. I assume that this is not what you are after, so here is a way do it with a TreeMap:

TreeMap<Long,Object> map = new TreeMap<Long,Object>();
Long key = 42;
Map.Entry<Long,Object> low = map.floorEntry(key);
Map.Entry<Long,Object> high = map.ceilingEntry(key);
Object res = null;
if (low != null && high != null) {
    res = Math.abs(key-low.getKey()) < Math.abs(key-high.getKey())
    ?   low.getValue()
    :   high.getValue();
} else if (low != null || high != null) {
    res = low != null ? low.getValue() : high.getValue();
}

Solution 2

Using a NavigableMap like a TreeMap

long key = 
NavigableMap<Long, Object> map = new TreeMap<Long , Object>();

Long before = map.floorKey(key);
Long after = map.ceilingKey(key);
if (before == null) return after;
if (after == null) return before;
return (key - before < after - key 
       || after - key < 0) 
       && key - before > 0 ? before : after;

Solution 3

Iterate over all the keys to find the key with the lowest difference to your target key.

Here's some code that does that:

public static Long nearestKey(Map<Long, Object> map, Long target) {
    double minDiff = Double.MAX_VALUE;
    Long nearest = null;
    for (long key : map.keySet()) {
        double diff = Math.abs((double) target - (double) key);
        if (diff < minDiff) {
            nearest = key;
            minDiff = diff;
        }
    }
    return nearest;
}

All that casting to double is to guard against a rollover when target is a large negative and the map key is a large positive

Solution 4

Solution :

1. If you are inserting values into the hashMap in a sorted order you could use a LinkedHashMap so that the insertion order can be maintained.

2. Now we can perform a binary search over the keys instead of iterating over all keys (like in some of the other answers).

3. If iteration over all keys took n comparisons, binary search would take log(n)with base 2 comparisons.

The point to note here would be that this works only if the map is sorted.

Comparison of diff maps :

• A hash map is good as a general purpose map implementation that provides rapid storage and retrieval operations. However, it falls short because of its chaotic and unorderly arrangement of entries.

  This causes it to perform poorly in scenarios where there is a lot of iteration as the entire capacity of the underlying array affects traversal other than just the number of entries.

• A linked hash map possesses the good attributes of hash maps and adds order to the entries. It performs better where there is a lot of iteration because only the number of entries is taken into account regardless of capacity.
• A tree map takes ordering to the next level by providing complete control over how the keys should be sorted. On the flip side, it offers worse general performance than the other two alternatives.

We could say a linked hash map reduces the chaos in the ordering of a hash map without incurring the performance penalty of a tree map.

View more solutions

Comments

[Bohemian]

What about the edge case of key - before rolling over? The keys could be hashes, so it could happen. Even so, +1!

[Khashayar]

Thanks alot! just one more thing is this treemap fast ? compare to maps? and compare to arraylists? (i know they are faster than arraylist but just to get sure) :D

[Sergey Kalinichenko]

@KhashayarNapster Tree maps are reasonably fast, though generally not as fast as hash maps. They slow down as the number of keys increases, but the slowdown is relatively small (it's logarithmic). For example, if tree map A has 1,000 entries and tree map B has 1,000,000 entries, searching B is only twice as slow as searching A.

[Vishy]

hashes are designed to be pseudo random and in no predictable order, but you are right that there could be an overflow.

[hBrent]

This seems to answer the original question, to get the nearest key (not value). It's not clear to me what some of the other answers are doing.