2

上SortedMap.subMap

这是 API SortedMap<K,V>.subMap：

SortedMap<K,V> subMap(K fromKey, K toKey)：返回此地图部分的视图，其键范围从fromKey, 包含 , 到toKey, 不包含。

这种包容性的下限、独占的上限组合（“半开范围”）在 Java 中很普遍，虽然它确实有它的好处，但它也有它的怪癖，我们很快就会看到。

以下代码段说明了 的简单用法subMap：

static <K,V> SortedMap<K,V> someSortOfSortedMap() {
    return Collections.synchronizedSortedMap(new TreeMap<K,V>());
}
//...

SortedMap<Integer,String> map = someSortOfSortedMap();
map.put(1, "One");
map.put(3, "Three");
map.put(5, "Five");
map.put(7, "Seven");
map.put(9, "Nine");

System.out.println(map.subMap(0, 4));
// prints "{1=One, 3=Three}"

System.out.println(map.subMap(3, 7));
// prints "{3=Three, 5=Five}"

最后一行很重要：7=Seven由于 的排他性上限而被排除在外subMap。现在假设我们实际上需要一个包容性上限，那么我们可以尝试编写一个这样的实用方法：

static <V> SortedMap<Integer,V>
subMapInclusive(SortedMap<Integer,V> map, int from, int to) {
    return (to == Integer.MAX_VALUE)
      ? map.tailMap(from)
      : map.subMap(from, to + 1);
}

然后，继续上面的代码片段，我们得到：

System.out.println(subMapInclusive(map, 3, 7));
// prints "{3=Three, 5=Five, 7=Seven}"

map.put(Integer.MAX_VALUE, "Infinity");
System.out.println(subMapInclusive(map, 5, Integer.MAX_VALUE));
// {5=Five, 7=Seven, 9=Nine, 2147483647=Infinity}

需要进行一些关键观察：

  • 好消息是我们不关心值的类型，但是......
  • subMapInclusive假定Integer密钥to + 1工作。
    • 一个通用版本也需要例如Long键是不可能的（请参阅相关问题）
    • 更不用说 for 了，Long我们需要对比Long.MAX_VALUE
    • 数字原始盒装类型的重载Byte，Character等，作为键，都必须单独编写
    • 需要对 进行特殊检查toInclusive == Integer.MAX_VALUE，因为+1会溢出，并且subMap会抛出IllegalArgumentException: fromKey > toKey
  • 一般来说，这是一个过于丑陋和过于具体的解决方案
    • String钥匙呢？或者一些甚至可能不是的未知类型Comparable<?>？

所以问题是：是否有可能编写一个通用subMapInclusive方法，该方法采用SortedMap<K,V>, and K fromKey, K toKey, 并执行包含范围的subMap查询？

相关问题

上NavigableMap

应该提到的是，有一个NavigableMap.subMap重载需要两个额外boolean的变量来表示边界是包含还是排除。如果这是在 中提供的SortedMap，那么上面的任何一个都不会被问到。

因此，使用NavigableMap<K,V>for 包含范围查询本来是理想的，但是虽然Collections为（除其他外）提供了实用方法，但SortedMap我们无法享受与NavigableMap.

相关问题

在仅提供独占上限范围查询的 API 上

  • 这是否突出了排他上限范围查询的问题？
  • 过去，当独占上限是唯一可用的功能时，包含范围查询是如何完成的？
4

3 回答 3

3

这是我对一般包容性子图的实现。在这里我假设由于地图是排序的，所以tailmap的时间复杂度会很低，所以诀窍是从尾部开始并查看返回的键，然后根据这些键获取尾部，常规子图，或带有下一个键的子图：

static <K, V> SortedMap<K,V>
subMapInclusive(SortedMap<K,V> map, K from, K to) {
    if(to == null) return map.tailMap(from);

    //What appears at key "to" or later?
    Iterator<K> keys = map.tailMap(to).keySet().iterator();

    //Nothing, just take tail map.
    if(!keys.hasNext()) return map.tailMap(from);

    K key = keys.next();

    //The first item found isn't to so regular submap will work
    if(!to.equals(key)) return map.subMap(from, to);

    //to is in the map

    //it is not the last key
    if(keys.hasNext()) return map.subMap(from, keys.next());

    //it is the last key
    return map.tailMap(from);
}
于 2010-05-18T14:01:42.497 回答
1

使用 Guava 的 Maps.filterKeys 怎么样？

Maps.filterKeys(map, Range.closed(0, 4)); //includes 1 and 3
Maps.filterKeys(map, Range.closed(3, 7)); //includes 3, 5, and 7

Range 谓词的参数必须实现 Comparable，但您也可以使用 Predicates.in 来使用集合进行过滤：

Set<Integer> filterSet = Sets.newHashSet();
filterSet.add(3);
filterSet.add(5);
filterSet.add(7);
Maps.filterKeys(map, Predicates.in(filterSet)); //includes 3, 5, and 7
于 2014-02-11T03:06:04.030 回答
0

也许您可以执行以下操作：

static <K, V> SortedMap<K,V>
subMapInclusive(SortedMap<K,V> map, K from, K to) {
  SortedMap<K,V> result = map.subMap(from, to);
  V last = map.get(to);
  if (last != null) result.put(to, last);
  return result;
}

编辑：TreeMap 似乎也有一个 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) 方法；也许您可以使用它来代替 SortedMap。

于 2010-05-18T13:46:36.970 回答