使用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那样简单。我想能够进行范围搜索。对于我的请求，抱歉导致了混淆。根据我的查询，我已添加了正确的示例，数字是连续的。

- kal

---

请提供一个您想要做的真实示例。 - Thorbjørn Ravn Andersen

示例中给出的范围不是连续的。如果搜索4或50，您想要一个“null”结果、上面的范围、下面的范围、最近的范围还是什么？ - erickson

你不断更改需求的方式，可能会成为地狱般的经理 :-) - Stephen C

抱歉如果这增加了很多困惑 :) - kal

可能是可以将一系列键映射到值的数据结构的重复问题。 - Vadzim

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();
}

- Stephen C

---

这是对现有的TreeMap进行简单范围搜索的非常好的应用。请注意，如果存在重叠的区间，则该方法将返回与查找键最接近的较低键的间隔。同样，此方法不支持搜索所有包含给定搜索键的重叠间隔，如https://dev59.com/gHI-5IYBdhLWcg3w-92b中所讨论的那样。 - stackoverflowuser2010

如果存在重叠的范围，则这些范围（很可能）被错误地指定。至少，这是我对此问题的理解。 - Stephen C

Answer 2

伪代码：

1. 将范围边界存储在一个扁平数组中：new int[] {0, 3, 5, 15, 100, 300}。
2. 二分搜索该数组，就好像将一个数字插入到数组中一样。请参见Arrays.binarySearch()。
3. 如果插入点是偶数，则该数字不适合任何范围。
4. 如果插入点是奇数，则它适合相应的范围。例如，在上面的数组中，10的插入点是3，将其放置在5和15之间，因此它属于第二个范围。

- John Kugelman

---

注意：这仅适用于我们映射到整数 {0，1，2，...}的情况。对于更一般的情况，应使用某种类型的映射表。 - Stephen C

Answer 3

如果无法使用算术解决更一般的情况，您可以创建一个具有适当比较器的TreeMap。添加边界值的映射，然后使用ceilingEntry或floorEntry查找适当的匹配项。

- Ken

Answer 4

我认为你想要的是类似于foo()/10的东西，但这会给你略微偏离你所请求的范围。如果它们不遵循简单的模式，你可以始终对你的“映射”中的每个项目的两个端点进行比较。

- Sophie Alpert

Answer 5

我认为最简单的解决方案是将范围的上限映射到该范围映射到的值，并且只需增加您的数字（映射中的键），直到达到映射（这是您的数字所在范围的上限）。

另一种方法是填充地图中的所有条目，并为每个条目添加映射。

哪种方法更有效取决于您是否有可能需要重复请求范围内的所有数字（使用后者解决方案），还是仅多次请求其中一些数字（使用前者）

- Jorn

Answer 6

基于John Kugelman的回答，我需要类似于日期范围搜索的东西，它与日期范围相关联的数据...这是我如何应用它的一个例子。 "dates"将是您的键，"rangeData"将是相关联的数据。

  long[] dates = new long[] {
    Instant.parse("1900-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1950-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1960-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1970-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1980-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1990-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2000-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2010-01-01T00:00:00Z").toEpochMilli()
  };
  String[] rangeData = new String[] {
    "Before 1900 data", "Before 1950 data", "Before 1960 data", 
    "Before 1970 data", "Before 1980 data", "Before 1990 data", 
    "Before 2000 data", "Before 2010 data"
  };
  
  long searchDate = Instant.parse("1949-02-15T00:00:00Z").toEpochMilli();
  int result = Arrays.binarySearch(dates, searchDate);
  
  System.out.println("Result: " + result); 
  if (result == dates.length) {
      System.out.println("Date is after all ranges");
      System.out.println("Data: none");
  }
  else if (result >= 0) {
      System.out.println("Date is an exact match of " + Instant.ofEpochMilli(dates[result]));
      System.out.println("Data: " + rangeData[result]);
  }
  else {
      int resultIndex = Math.abs(result) - 1;
      System.out.println("Date is before idx: "+ resultIndex + " date " + Instant.ofEpochMilli(dates[resultIndex]));
      System.out.println("Data: " + rangeData[resultIndex]);
  }

结果

Result: -2
Date is before idx: 1 date 1950-01-01T00:00:00Z
Data: Before 1950 data

- xer21