是否有一种 Java 数据结构实际上是具有双索引和内置插值的 ArrayList？

我正在寻找具有以下特征的预构建 Java 数据结构：

1. 它应该看起来像 ArrayList，但应该允许通过双精度而不是整数进行索引。请注意，这意味着您可能会看到与原始数据点不相符的索引（即询问与键“1.5”对应的值）。EDIT：为了清楚起见，根据评论，我不打算changeArrayList 的实现。我正在寻找类似的界面和开发人员体验。

2. 因此，返回的值可能会被插值。例如，如果键为 1.5，则返回的值可能是键 1.0 处的值和键 2.0 处的值的平均值。

3. 键将被排序，但值不能保证单调递增。事实上，无法保证值的一阶导数是连续的（使其不太适合某些类型的样条线）。

4. 请仅提供免费代码。

为了清楚起见，我知道如何写这样的东西。事实上，我们已经在遗留代码中实现了这个和一些相关的数据结构，由于一些性能和编码问题，我想替换它们。

我试图避免的是花费大量时间来滚动我自己的解决方案，而此时可能已经存在这样的事情了JDK http://java.sun.com/javase/6/docs/api/index.html?overview-summary.html, 阿帕奇共享区 http://commons.apache.org/或另一个标准库。坦率地说，这正是使这些遗留代码陷入现在困境的方法......

免费图书馆里有这样的东西吗？

允许double作为索引的值是相当大的变化从何而来ArrayList does.

这样做的原因是数组或列表double因为根据定义，指数几乎是稀疏数组 http://en.wikipedia.org/wiki/Sparse_array，这意味着它对于几乎所有可能的索引都没有值（或者取决于您的定义：固定的已知值），并且只有有限数量的索引具有显式值集。

Java SE 中没有预构建的类支持所有这些。

就我个人而言，我会实现这样一个数据结构：跳过列表 http://en.wikipedia.org/wiki/Skip_list（或类似的快速搜索数据结构）(index, value)具有适当插值的元组。

Edit:实际上，后端存储有一个非常好的匹配（即除了插值之外的所有内容）：只需使用NavigableMap http://java.sun.com/javase/6/docs/api/java/util/NavigableMap.html比如一个TreeMap http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html存储从索引到值的映射。

这样你就可以轻松使用ceilingEntry() http://java.sun.com/javase/6/docs/api/java/util/NavigableMap.html#ceilingEntry(K)和（如果需要）higherEntry() http://java.sun.com/javase/6/docs/api/java/util/NavigableMap.html#higherEntry(K)获取最接近您需要的索引的值，然后从中进行插值。