Effectivey searching a Java collection of Comparable objects

Question

I have a Java 8 application with an arbitrary Map<T, String>, where T extends Comparable<T>.

The easiest example uses integers:

Map<Integer,String> numbers = new HashMap<>(4);
numbers.put(10,"value10");
numbers.put(20,"value20");
numbers.put(30,"value30");
numbers.put(40,"value40");

I want to search this Map for the key that is close to an arbitrary input value, rounding up, unless no key exists that is greater, then round down. For instance:

• input -5 returns key 10 (round up to the smallest key that is larger then input)
• input 8 returns key 10 (round up to the smallest key that is larger then input)
• input 10 return key 10 (exact match)
• input 11 returns key 20 (round up to the smallest key that is larger then input)
• input 40 return key 40 (exact match)
• input 100 returns key 40 (round down, no key exists that is greater than 10)

I have a working implementation that naively loops over all keys, does all necessary comparisons and returns the best matching key based on these criteria. My application needs to check the same Map for different values often so this naive lookup can become a bottleneck. As demonstrated in this other question, I believe a sorted TreeMap might significantly increase the lookup time, but this class is a bit too complex for me to understand without some guidance .

• Which methods of TreeMap can I use to implement this lookup?
• How would the algorhitm below be simplified by using advantage of the fact that a TreeMap is sorted?
• If not TreeMap, is another data structure more suited for this?

Here is the naive (but working) implementation. The Collection is actually the Map's Keyset:

private T getBestMatchingKeyForValue(Collection<T> keys, T value)
{
    T bestMatchingKeySoFar = null;

    for (T keyToCheck : keys)
    {
        if (bestMatchingKeySoFar == null)
        {
            bestMatchingKeySoFar = keyToCheck;
        }
        else
        {
            int valueComparedToBestMatching = value.compareTo(bestMatchingKeySoFar);
            int valueComparedToKeyToCheck = value.compareTo(keyToCheck);
            int partitionTocheckComparedToBestMatching = keyToCheck.compareTo(bestMatchingKeySoFar);

            int signValueComparedToBestMatching = Integer.signum(valueComparedToBestMatching);
            int signValueComparedToKeyToCheck = Integer.signum(valueComparedToKeyToCheck);
            int signKeyToCheckComparedToBestMatching = Integer.signum(partitionTocheckComparedToBestMatching);

            if (signValueComparedToBestMatching == signValueComparedToKeyToCheck)
            {
                if (signValueComparedToBestMatching == signKeyToCheckComparedToBestMatching)
                {
                    bestMatchingKeySoFar = keyToCheck;
                }
            }
            else if (valueComparedToKeyToCheck == 0)
            {
                bestMatchingKeySoFar = keyToCheck;
            }
            else if (valueComparedToBestMatching != 0)
            {
                if ((this.preferUpperBound && partitionTocheckComparedToBestMatching > 0)
                        || (!this.preferUpperBound && partitionTocheckComparedToBestMatching < 0))
                {
                    bestMatchingKeySoFar = keyToCheck;
                }
            }
        }
    }

    return bestMatchingKeySoFar;
}

Answer 1

TreeMap's floor and ceiling methods do exactly what you're looking for:

TreeMap<K, V> map = ...
K search = ...
K closest = map.ceilingKey(search);
if (closest == null) {
    closest = map.floorKey(search);
}