快速数据结构用于随机和顺序访问。

Question

快速数据结构用于随机和顺序访问。

javaperformancedata-structuresasymptotic-complexity

3

我正在寻找一种数据结构或各种数据结构的组合，能够在随机和顺序访问时表现出色。

我需要将（整数）ID映射到（双精度）值并按该值进行排序。这些值可能会出现多次。

数据量可能很大。

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

我使用Java。目前我有一个Guava Multimap，它由TreeMap和ArrayList组成，用于顺序访问。对于随机访问，我同时使用了HashMap。

有什么建议吗？

- thertweck

你的ID是否在某个范围内，还是理论上可以是任意整数？ - isnot2bad

它们可以是任意的整数或长整型，而且它们可以有很多。尽管如此，范围可以被认为是已知的。 - thertweck

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- maaartinus · Accepted Answer

当插入和删除不是关键时，排序数组可能是您的朋友。您可以通过Arrays.binarySearch和自定义Comparator直接在其中搜索。

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

我想这可能比TreeMap更快，后者在插入和/或删除很重要时很好，但受到空间局部性不佳的影响（二叉树具有许多要跟随的指针）。

最优结构将所有数据放入单个数组中，在Java中不可能（您需要C struct）。您可以通过将double放入long中来伪造它，这肯定可以工作并且速度很快（Double.doubleToLongBits和回退是内置函数，并且两种数据类型的长度均为64位）。这意味着需要非常努力地工作，特别是对于排序（如果这不太常见，则在某些可排序数组中进行转换即可）。

为了实现更快的搜索，您可以使用哈希算法，例如通过指向第一个元素并链接元素的 HashMap。由于您的键是 int，一些原始类型实现会有所帮助（例如 trove 或 fastutils 等）。

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