Java 中的内存高效稀疏数组 [英] Memory-efficient sparse array in Java

问题描述

(有一些关于节省时间的稀疏数组的问题，但我正在寻找内存效率.)

(There are some questions about time-efficient sparse arrays but I am looking for memory efficiency.)

我需要一个 List 或 Map 的等价物

I need the equivalent of a List<T> or Map<Integer,T> which

1. 只需设置一个比之前遇到的任何密钥都大的密钥，即可按需增长.(可以假设键是非负的.)
2. 在大多数索引不是 null 的情况下，与 ArrayList 的内存效率差不多，即当实际数据不是很稀疏时.
3. 当索引稀疏时，消耗的空间与非null 索引的数量成正比.
4. 比 HashMap 使用更少的内存(因为这会自动装箱键并且可能没有利用标量键类型).
5. 可以在平均 log(N) 时间内获取或设置元素，其中 N 是条目数:不需要是线性时间，二进制搜索是可以接受的.
6. 在非病毒式开源纯 Java 库中实现(最好在 Maven Central 中).

1. Can grow on demand just by setting a key larger than any encountered before. (Can assume keys are nonnegative.)
2. Is about as memory-efficient as an ArrayList<T> in the case that most of the indices are not null, i.e. when the actual data is not very sparse.
3. When the indices are sparse, consumes space proportional to the number of non-null indices.
4. Uses less memory than HashMap<Integer,T> (as this autoboxes the keys and probably does not take advantage of the scalar key type).
5. Can get or set an element in amortized log(N) time where N is the number of entries: need not be linear time, binary search would be acceptable.
6. Implemented in a nonviral open-source pure Java library (preferably in Maven Central).

有人知道这样的实用程序类吗?

Does anyone know of such a utility class?

我原以为 Commons Collections 会有一个，但似乎没有.

I would have expected Commons Collections to have one but it did not seem to.

我遇到了 org.apache.commons.math.util.OpenIntToFieldHashMap，它看起来几乎是正确的，除了值类型是一个看起来毫无意义的 FieldElement ；我只想要T extends Object.看起来很容易将其源代码编辑为更通用，但如果可用，我更愿意使用二进制依赖项.

I came across org.apache.commons.math.util.OpenIntToFieldHashMap which looks almost right except the value type is a FieldElement which seems gratuitous; I just want T extends Object. It looks like it would be easy to edit its source code to be more generic, though I would rather use a binary dependency if one is available.

推荐答案

我会尝试使用 trove集合，有 TIntObjectMap 可以满足您的意图.

I would try with trove collections, there is TIntObjectMap which can work for your intents.

这篇关于Java 中的内存高效稀疏数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！