问题标签 [range-map]

假设我有一张 Java 地图，如下所示：

如果键按排序顺序（使用树图或链接哈希图）。现在如果我尝试获取 >=39 和 <41 的值。那么我应该得到字符串“39 到 41”。我如何有效地做到这一点?

我试图找到一个数据结构，它从一系列值中获取特定值并将其映射到一个键。

例如，我有以下条件：

1. 从1到2.9，我想把它映射到A。
2. 从4到6，我想把它映射到B。
3. 从6.5到10，我想把它映射到C。

我的值为 5，我想将它映射到一个键。所以基于上述条件，我应该把它映射到B。

是否有任何人可以向我推荐来解决问题的 Java 数据结构？

目前我正在使用一个只能将一个值映射到一个键的哈希表。我试图将值的范围映射到哈希表中存在的特定值。但是，我陷入了将值范围映射到特定值的过程中。所以现在我正在尝试另一种将值范围映射到键的方法。有谁知道我该如何解决这个问题？

编辑：

感谢 Martin Ellis，我决定使用 TreeMap 来解决这个问题。

我的问题与可以将一系列键映射到值的数据结构中提到的几乎相同，但对于 Scala。

也就是说，我想要一个可变的非重叠一维范围[a[i], b[i])系统，它可以映射到某种值v[i]。完成此类工作的标准底层数据结构是红黑树。

我希望它拥有的操作，最好是所有操作都应该具有 O(log n) 的复杂性：

• 通过指定范围内的任何点来查询并获取给定范围（开始、结束、存储值）或缺少范围
• 在此结构中插入一个新范围
• 从结构中删除范围

所以，我想到目前为止，我看到了以下变体，所有这些变体都有其缺点：

• 在Java 的 TreeMap上滚动你自己的容器- 快速且肮脏，但由于缺乏适当的维护，长期来看可能很糟糕
• 使用 Guava 的RangeMap - 可能，但在 Scala 集合世界中会很尴尬
• 尝试使用 Scala 的红黑树实现并尝试自己滚动，但是，我想这将非常困难，因为Scala 的 TreeMap是仅不可变的并且缺少简单的查找方法，例如 Java 的 TreeMapfloorEntry

我在这里错过了什么吗？是否有任何使用以 Scala 为中心的 API 扩展基本 Scala 集合的类似 Guava 且维护良好的集合扩展库？

密切相关的问题：

• 将 Java TreeMap 代码迁移到 Scala？- 提到“只使用 Java 的 TreeMap”而忘记其他任何事情
• 此问题的 Java 版本：
  • 可以将一系列键映射到值的数据结构
  • 整数区间内的哈希表键
  • 使用 java map 进行范围搜索
  • Java - 适合搜索区间的数据结构

我看到我可以用1:3. 我还可以将函数应用于数字，例如sin(1). 但是，如何用函数映射数字范围？我想 $1,2,3 \to sin(1), sin(2), sin(3)$。

我有一个用例，其中需要预先构建番石榴 RangeMap 并将其加载到 redis 中。在将来的某个时候，它会从 redis 中检索并再次使用。

这样做是为了减少构建 rangeMap 本身的时间。

有什么建议或建议吗？RangeMap可以序列化存储到redis中吗？这是最好的方法吗？

此外，单个数据点的范围图的平均查找时间是多少？

日志（n）？m-> 范围数，n-> 平均值。范围的大小

我正在尝试找到一个数据结构，以便我得到这个：

会变成这样：

我正在使用 RangeMap，我想像示例中那样合并范围，但它没有帮助，我也浏览了文档，但没有找到相关的解决方案。这个数据结构中有解决方案还是我可以使用更好的解决方案？谢谢！