我正在寻找一种数据结构或各种数据结构的组合，它们在随机和顺序访问上表现非常出色。
我需要将一个(整数)id 映射到一个( double )值并按该值排序。这些值可以出现多次。
数据量可能很大。
插入或删除并不重要。迭代和获取操作是。
我正在使用 Java。目前我有一个 Guava Multimap，它是从 TreeMap 和 ArrayList 构建的，用于顺序访问。对于随机访问，我并行使用 HashMap。
有什么建议吗？
最佳答案
当插入和删除不重要时，排序数组可能是您的 friend 。您可以直接通过 Arrays.binarySearch 在那里搜索，并自定义 Comparator。
如果您不知道大小的任何合理上限，您可以切换到 ArrayList(或实现您自己的大小调整，但为什么...)。
我猜这可能比 TreeMap 更快，这在插入和/或删除很重要时很好，但空间局部性不好(有许多指针要遵循的二叉树)。
最佳结构会将所有数据放在一个数组中，这在 Java 中是不可能的(为此您需要 C struct)。您可以通过将 double 放入 long 来伪造它，这肯定会工作并且速度很快(Double.doubleToLongBits 和后面是内在函数，并且两种数据类型的长度都是 64 位)。这将意味着大量的工作，尤其是排序(如果这种情况不常见，则可以在某些可排序数组中进行转换并返回)。
为了获得更快的搜索，您可以使用哈希，例如，通过指向第一个元素并链接元素的 HashMap。由于您的 key 是 int，因此一些具有原始能力的实现会有所帮助(例如 trove 或 fastutils 或其他)。
有无数种可能性，但保持所有数据同步可能很困难。
关于java - 用于随机和顺序访问的快速数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19905389/