应该使用哪种数据结构进行范围查找？

Question

我正在考虑使用 HashMap，但我认为我要么必须对其进行自定义，要么必须为其创建自定义数据结构。正如我们所知，HashMap 存储键值对，但我需要一个数据结构，而不是单个键，我应该能够放置一个范围。例如：

Range        Should return
0 to 50      Object1
51 to 100    Object2
90 to 150    Object3

所以如果用户搜索 10。他应该能够得到 Object1，如果用户搜索 55。他应该能够得到 Object2，如果用户搜索 95。他应该能够同时获得 Object2 和 Object3。

我正在考虑将范围放入每个对象并将所有对象放入 ArrayList 或 LinkedList 中，然后我可以对其进行迭代并找到满足输入的所有对象。但是它的时间复杂度会更多。对于每个输入，我都必须遍历整个列表。我也考虑过树，但在重叠范围（如 51 到 100 和 90 到 150）的情况下，我不知道这会有什么帮助。

让我知道你的观点，我的目标是时间复杂度应该不太像或接近 hashmap

Answer 1

您可以使用 B-Tree：B-Tree
or maybe a Disjoint-set structure: Disjoint-set
Another S.O. user suggests a TreeMap: TreeMap
The final possibility (Possibly solving your overlapping range dilemma) is the R-Tree: R-Tree

R 树可视化：

使用 B-Tree，您可以在每个节点对象中放置一个小的 "directory" 字段，它可以立即告诉您每个 Node/object。但是，你必须考虑当包含节点充满对象时会发生什么，你必须 donate/adopt 一个对象到另一个节点或从另一个节点。

话虽如此，使用 路径压缩 的 不相交集结构 为您提供了 O(1) 的分摊运行时间，以及 O 的最坏情况（日志 * N）！这也非常容易实现；你真的只需要一些核心方法，（联合、查找、按大小联合、按大小查找），就可以得到它运行。

R-Trees 可以让您处理重叠范围的情况，但您也会牺牲一些运行时间。在最坏的情况下，您最终的搜索时间为 O(M logMn)，这比 HashMap 慢。

应该使用哪种数据结构进行范围查找？

Which data structure should be used for range look up?

data-structures