java - 用于存储大量长值列表的数据结构

Question

我在我的 Java 程序中缓存长索引列表，它导致内存溢出。因此，决定只缓存所有连续索引的开始和结束索引，并重写 ArrayList 所需的 API。现在，什么数据结构最适合实现起始索引缓存？使用 TreeMap 并将开始索引作为键并将结束索引作为值是否更好？

Answer 1

最紧凑的表示将在很大程度上取决于您的特定应用程序中的索引分布。

如果您的索引密集聚集，则 mvp 建议的基于范围的表示可能会很好地工作（您可能会查看光栅图形的行程编码的实现，因为它们是类似的问题）。

如果您的索引未在密集运行中聚集，则该编码实际上会增加内存消耗。对于稀疏的列表，您可以查看原始数据结构，例如 FastUtil 中的 LongArrayList 或LongOpenHashSet ，或Gnu Trove或Colt中的类似结构。在大多数 VM 中，ArrayList 中的每个 Long 对象消耗 20 多个字节，而原始 long 仅消耗 8 个字节。因此，您通常可以使用特定于类型的原始集合而不是标准集合框架来实现显着的内存节省。

我对 FastUtil 非常满意，但您可能会发现另一种更适合您的解决方案。一点模拟和内存分析应该可以帮助您确定您自己的数据的最有效表示。

Answer 2

如果我是你，我会使用位串存储的一些变体。

在 Java 中，位字符串由BitSet实现。

例如，要表示唯一的 32 位整数的任意列表，您可以将其存储为 40 亿位长的单个位字符串，因此这将占用 4 bln / 8 位 = 512MB 的内存。这是很多，但这是最坏的情况。

但是，你可以比这聪明得多。例如，您可以将其存储为一些较小的固定（或动态）大小的位字符串的列表或二叉树，例如 65536 位或更少（或 8KB 或更少）。换句话说，这棵树中的每个叶子对象都有一个小标题，表示起始偏移量和长度（为简单起见，可能是 2 的幂，但不一定是），以及存储实际数组成员的位串。为了提高效率，您可以选择使用 gzip 或类似算法压缩此位字符串 - 它会使访问速度变慢，但可以将内存效率提高 10 倍或更多。

如果您的 2000 万个索引元素几乎是连续的（不是很稀疏），那么在内存中表示它应该只需要大约 2000 万/8 位 ~= 200 万位 = 2 MB。如果你对它进行 gzip，它的总大小可能低于 1MB。

Answer 3

大多数 BitSet（压缩或未压缩）实现都是针对整数的。这是一个长期的：http ://www.censhare.com/en/aktuelles/censhare-labs/yet-another-compressed-bitset ，它的工作方式类似于有序的原始长散列集或长到长散列映射。