有效搜索 [​​=10=] 个 Comparable 对象集合

Question

我有一个带有任意 Map<T, String> 的 Java 8 应用程序，其中 T 扩展 Comparable<T>.

最简单的示例使用整数：

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

我想在此 Map 中搜索接近任意输入值的键，向上取整，除非不存在更大的键，否则向下取整。例如：

• input -5 returns key 10（四舍五入到大于输入的最小key）
• input 8 returns key 10（四舍五入到比输入大的最小key）
• 输入10 return键10（完全匹配）
• input 11 returns key 20 (四舍五入到大于输入的最小key)
• 输入40 return键40（完全匹配）
• input 100 returns key 40（向下舍入，不存在大于10的key）

我有一个工作实现，它天真地遍历所有键，进行所有必要的比较，return根据这些标准选择最匹配的键。我的应用程序需要经常检查同一个 Map 的不同值，因此这种天真的查找可能成为瓶颈。正如 中所展示的，我相信排序的 TreeMap 可能会显着增加查找时间，但是这个 class 有点太复杂了，如果没有一些指导我是无法理解的。

• 我可以使用TreeMap的哪些方法来实现这个查找？
• 如何利用 TreeMap 已排序这一事实来简化下面的算法？
• 如果不是 TreeMap，是否有其他数据结构更适合这个？

这是天真的（但有效）实现。 Collection 实际上是 Map 的 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 的下限和上限方法完全符合您的要求：

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