java - 用于随机和顺序访问的快速数据结构

Question

我正在寻找一种数据结构或各种数据结构的组合，它们在随机和顺序访问方面表现非常好。

我需要将（整数）id 映射到（双）值并按该值排序。这些值可以出现多次。

数据量可能很大。

插入或删除并不重要。迭代和获取操作是。

我正在使用 Java。目前我有一个 Guava Multimap，它是由 TreeMap 和 ArrayList 构建的，用于顺序访问。对于随机访问，我并行使用 HashMap。

有什么建议么？

Answer 1

当插入和删除不重要时，排序数组可能是您的朋友。您可以直接通过那里搜索Arrays.binarySearch并自定义Comparator.

如果您不知道大小的任何合理上限，您可以切换到ArrayList（或实现您自己的调整大小，但为什么......）。

我想这可能会比 快TreeMap，当插入和/或删除很重要时，这很好，但会受到空间局部性差的影响（二叉树有许多要遵循的指针）。

最佳结构会将所有数据放在一个数组中，这在 Java 中是不可能的（struct为此您需要 C）。double您可以通过将s 放入s来伪造它long，这肯定会起作用并且速度很快（Double.doubleToLongBits并且 back 是内在函数，并且两种数据类型的长度都是 64 位）。这将意味着大量的工作，特别是对于排序（如果这很不常见，则可以在某个可排序数组中进行转换并返回）。

为了获得更快的搜索，您可以使用散列，例如，通过HashMap指向第一个元素并链接元素。由于您的键是ints，因此一些具有原始功能的实现会有所帮助（例如 trove 或 fastutils 或其他）。

有无数种可能性，但保持所有数据同步可能很困难。