21

假设我有一张 Java 地图，如下所示：

{ 
 39:"39 to 41",
 41:"41 to 43",
 43:"43 to 45",
 45:">=45"
}

如果键按排序顺序（使用树图或链接哈希图）。现在如果我尝试获取 >=39 和 <41 的值。那么我应该得到字符串“39 到 41”。我如何有效地做到这一点?

4

6 回答 6

55

看起来你想要的不仅仅是SortedMap; 你想要一个NavigableMap！具体可以使用floorKey操作。

这是一个例子：

    NavigableMap<Integer,String> map =
        new TreeMap<Integer, String>();

    map.put(0, "Kid");
    map.put(11, "Teens");
    map.put(20, "Twenties");
    map.put(30, "Thirties");
    map.put(40, "Forties");
    map.put(50, "Senior");
    map.put(100, "OMG OMG OMG!");

    System.out.println(map.get(map.floorKey(13)));     // Teens
    System.out.println(map.get(map.floorKey(29)));     // Twenties
    System.out.println(map.get(map.floorKey(30)));     // Thirties
    System.out.println(map.floorEntry(42).getValue()); // Forties
    System.out.println(map.get(map.floorKey(666)));    // OMG OMG OMG!

请注意，还有ceilingKey, lowerKey, higherKey, and also …Entryinstead of…Key操作，它们返回 aMap.Entry<K,V>而不仅仅是K.

于 2010-08-19T09:12:31.833 回答
7

试试 Java 6 java.util.NavigableMap。http://download.oracle.com/javase/6/docs/api/java/util/NavigableMap.html。

特殊用途floorKey/ floorEntry。

例如：floorKey(40)应该返回39. floorEntry 将返回您正在寻找的值。

于 2010-08-19T08:58:10.307 回答
1

使用排序后的地图，您可以执行以下操作：

SortedMap<Integer,String> head = map.headMap(value+1);
if (head.isEmpty()) {
    return null;
} else {
    return head.get(head.lastKey());
}
于 2010-08-19T08:37:57.393 回答
0

我不确定这会很容易。一个建议是“填补空白”，即输入一个值40->"39 to 41"等。我想只有当您知道地图中可能的整个数字范围时，这才有可能。

或者可能会覆盖的东西get检查以查看该值是否在地图中，并展开直到找到某些东西。我不确定在当前的情况下这是否可行，因为您最终必须解析值字符串。

于 2010-08-19T08:27:28.460 回答
0

您可以递归地寻找下边界。

public String descriptionFor(int value) {
    String description = map.get(value);
    return description == null ? descriptionFor(value--) : description;
}

您将需要有一个最小边界。

于 2010-08-19T08:34:46.057 回答
0

我相信你必须自己实现这样的地图。您是对的，必须对其进行排序；的实现get必须遍历键，直到找到小于或等于参数的最大键。

如果您TreeMap将其子类化，最初看起来您可以通过简单地覆盖该get()方法来使其工作。但是，为了尽可能多地维护 Map 契约，您必须重写其他方法以保持一致性。

那么例如containsKey()呢？您的 main 是否包含映射40？如果您返回，则客户端可以根据此信息false决定不调用；get()由于这些原因（以及正式定义），您必须返回true. 但是，很难确定映射是否“真正包含”给定映射；如果您希望在不覆盖任何已经存在的情况下进行更新等操作。

该remove()方法也可能很棘手。根据我对界面的阅读，

// Calling map.remove "Removes the mapping for a key from this map if it is present."
map.remove(x);

// Now that the mapping is removed, I believe the following must hold
assert map.get(x) == null;
assert map.containsKey(x);

在这里始终如一地行事将非常棘手。例如，如果您有一个从 35-40 的映射，并且您调用remove(38)，那么据我所知，您必须返回null键 38 的任何后续获取，但返回键 35-37 或 39-40 的上述映射.

因此，虽然您可以通过覆盖 TreeMap 来开始这一点，但也许整个概念Map并不是您想要的。除非您需要将此行为插入到采用的现有方法中，否则您Map自己将其创建为一个不同的类可能会更容易，因为它不是一个Map，您定义它的方式。

于 2010-08-19T08:39:19.530 回答