java - 使用 java map 进行范围搜索

Question

我有一个用例，如果一个数字在 0-10 之间，它应该返回 0，如果它在 11-20 之间，它应该返回 1 等等

0 => 0-3, (0 and 3 are inclusive)
1 => 4-15, (4 and 15 are inclusive)
2 => 16-40, (16 and 40 are inclusive)
3 => 41-88, (41 and 88 are inclusive)
5 => 89-300 (89 and 300 are inclusive)

我在考虑如何实现并正在考虑 java map ，但它不允许范围搜索

我对这样的东西很感兴趣，我有一个功能

int foo() {

}

如果 foo 返回 5 ，因为它介于 0 到 10 之间，我会使用 0，如果 foo 返回 25 它会使用 2。

任何想法

编辑:实际上范围并不像 0-10、11-20 那样简单。我希望能够进行范围搜索。很抱歉造成困惑。根据我添加了正确示例的查询，数字是连续的

Answer 1

对于范围不统一且存在“漏洞”的更普遍的问题，我可以想到多种可能的解决方案。最简单的是:

1. 只需为所有有效键值填充一个 Map，多个键映射到同一个值。假设您使用 HashMaps，这应该是最省时的(O(1) 查找)，尽管您在设置时有更多工作并且使用更多空间。
2. 使用 NavigableMap 并使用 floorEntry(key) 进行查找。这应该更节省时间(O(log(N) 查找)，但更节省空间。

这是一个使用 NavigableMaps 的解决方案，它允许在映射中出现“洞”。

private static class Range {
   public int upper, value;
   ...
}

NavigableMap<Integer, Range> map = new TreeMap<Integer, Range>();
map.put(0, new Range(3, 0));       // 0..3     => 0
map.put(5, new Range(10, 1));      // 5..10    => 1
map.put(100, new Range(200, 2));   // 100..200 => 2

// To do a lookup for some value in 'key'
Map.Entry<Integer,Range> entry = map.floorEntry(key);
if (entry == null) {
    // too small
} else if (key <= entry.getValue().upper) {
    return entry.getValue().value;
} else {
    // too large or in a hole
}

另一方面，如果没有“漏洞”，解决方案会更简单:

NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(0, 0);    // 0..4     => 0
map.put(5, 1);    // 5..10    => 1
map.put(11, 2);   // 11..200  => 2

// To do a lookup for some value in 'key'
if (key < 0 || key > 200) {
    // out of range
} else {
   return map.floorEntry(key).getValue();
}