java - 如何有效地搜索值之间的映射？

Question

Map<Long, Object> map = new TreeMap<>();
map.put(100, object100);
map.put(120, object120);
map.put(200, object200);
map.put(277, object277);
map.put(300, object300);
map.put(348, object348);
map.put(400, object400);
//...

如果方法获取的值介于 map 的键和下一个 map 的键之间，它将返回第一个键的对象。例如，如果使用值 350 调用搜索方法，它应该返回 object348。

键中值的差异是不固定的。

但这样的搜索需要遍历所有条目，直到获得正确的值。那么，我该如何提高效率呢？

Answer 1

我不是很清楚你是只想要低于目标数字的键的对象，还是下面或上面最近的键的对象。

我怀疑您只是在询问下面键的对象，在这种情况下 NavigableMap.floorKey(K) 应该找到您要找的东西。

但以防万一您希望找到其键的值与目标值最接近的对象，那么这应该可以满足您的需要:

public static Object findNearestTo(long targetNumber) {
    if (map.isEmpty()) {
        return null;  // or throw an appropriate exception.
    }
    Object exactMatch = map.get(targetNumber);
    if (exactMatch != null) {
        return exactMatch;
    }
    Long nearestBelow = map.floorKey(targetNumber);
    Long nearestAbove = map.ceilingKey(targetNumber);
    if (nearestBelow == null) {
        return map.get(nearestAbove);
    } else if (nearestAbove == null) {
        return map.get(nearestBelow);
    }
    if (targetNumber - nearestBelow <= nearestAbove - targetNumber) {
        return map.get(nearestBelow);
    } else {
        return map.get(nearestAbove);
    }
}

请注意，如果目标数字与最近的下方和最近的上方的距离相等，它将偏爱键中具有较低值的对象。但是您可以通过更改 <= 来支持更高的值。至 <在 final 中 if测试。