使用 java map 进行范围搜索
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1314650/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using java map for range searches
提问by kal
I have a use case where if a number lies between 0-10 it should return 0 and if it lies between 11-20 it should return 1 etc
我有一个用例，如果一个数字在 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)
I was thinking how could I implement and was thinking java maps, but it does not allow range searching
我在想如何实现并在考虑 java 映射，但它不允许范围搜索
I am interested in something like this , I have a function
我对这样的东西感兴趣，我有一个功能
int foo() {
}
if foo returns 5 , since it lies between 0 to 10 I would use 0, if foo return 25 it would use 2.
如果 foo 返回 5 ，因为它位于 0 到 10 之间，我将使用 0，如果 foo 返回 25 它将使用 2。
Any ideas
有任何想法吗
Edit : Actually the ranges are not as simple as 0-10, 11-20. I want to be able to do range searches. Sorry about the confusion. Based on the queries I have added the correct example, the numbers are continous
编辑：实际上范围并不像 0-10、11-20 那样简单。我希望能够进行范围搜索。很抱歉造成混乱。根据我添加了正确示例的查询，数字是连续的
采纳答案by Stephen C
I can think of a number of possible solutions for the more general problem where the ranges are not uniform and there are 'holes'. The simplest are:
对于范围不均匀且存在“漏洞”的更一般问题，我可以想到许多可能的解决方案。最简单的是：
- Simply populate a Map for all valid key values, with multiple keys mapping to the same value. Assuming that you use HashMaps, this should be the most time efficient (O(1) lookups), though you have more work at setup time and you use more space.
- Use a NavigableMap and use
floorEntry(key)to do the lookups. This should be less time efficient (O(log(N) lookups) but more space efficient.
- 只需为所有有效键值填充一个 Map，多个键映射到相同的值。假设您使用 HashMap，这应该是最省时的（O(1) 查找），尽管您在设置时有更多工作并且使用了更多空间。
- 使用 NavigableMap 并用于
floorEntry(key)进行查找。这应该时间效率较低（O（log（N）查找），但空间效率更高。
Here's a solution using NavigableMaps that allows for 'holes' in the mapping.
这是一个使用 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
}
On the other hand, if there are no 'holes' the solution is simpler:
另一方面，如果没有“洞”，解决方案更简单：
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();
}
回答by Sophie Alpert
I think what you want is something along the lines of foo()/10, but that will give you ranges slightly off from what you requested. You can always just do comparisons with the two endpoints for each item in your "map" if they don't follow an easy pattern.
我认为您想要的是类似于 的东西foo()/10，但这会使您的范围与您所要求的略有不同。如果“地图”中的每个项目不遵循简单的模式，您始终可以与两个端点进行比较。
回答by Ken
In a more general case that can't be solved with arithmetic, you can create a TreeMap with an appropriate Comparator. Add mappings for the boundary values, and then use ceilingEntry or floorEntry to find the appropriate match.
在不能用算术解决的更一般的情况下，您可以使用适当的比较器创建一个 TreeMap。添加边界值的映射，然后使用天花板条目或地板条目来查找适当的匹配项。
回答by John Kugelman
Pseudo-code:
伪代码：
- Store the range bounds in a flat array:
new int[] {0, 3, 5, 15, 100, 300}. - Binary search through the array as if inserting a number into the array. See
Arrays.binarySearch(). - If the insertion point is even, the number does not fit into any range.
- If the insertion point is odd, it fits into the corresponding range. For example, the insertion point for
10in the above array would be3, placing it between5and15, so it belongs in the second range.
- 存储在一个扁平阵列的范围界限：
new int[] {0, 3, 5, 15, 100, 300}。 - 对数组进行二分查找，就像在数组中插入一个数字一样。见
Arrays.binarySearch()。 - 如果插入点是偶数，则数字不适合任何范围。
- 如果插入点是奇数，则它适合相应的范围。例如，
10上述数组中的插入点为3，将其放置在5和之间15，因此它属于第二个范围。
回答by Jorn
I think the easiest solution would be to add mappings from the upper boundaries of your ranges to the value that range maps to, and just keep incrementing your number (key in the map) until you reach a mapping (which is the upper boundary for the range your number is in).
我认为最简单的解决方案是添加从范围上边界到范围映射到的值的映射，然后不断增加您的数字（映射中的键）直到到达映射（这是您的号码所在的范围）。
Another way would be to populate the map with all entries in a range, and add a mapping for each.
另一种方法是使用范围内的所有条目填充地图，并为每个条目添加一个映射。
Which one is more efficient depends on whether it's likely you need to request all numbers in a range repeatedly (use the latter solution), or just some of the numbers a few times (use the first)
哪个更有效取决于您是需要重复请求范围内的所有数字（使用后一种解决方案），还是只请求一些数字几次（使用第一种）
