Java中的内存高效稀疏数组

Question

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

我需要相当于一个List<T>或Map<Integer,T>哪个

1. 可以通过设置比以前遇到的任何键更大的键来按需增长.(可以假设键是非负的.)
2. ArrayList<T>在大多数索引不是的情况下null,即在实际数据不是非常稀疏的情况下,就像存储器效率一样.
3. 当指数稀疏时,消耗与非null指数数量成比例的空间.
4. 使用的内存少于HashMap<Integer,T>(因为这会自动锁定密钥并且可能不会利用标量密钥类型).
5. 可以在分摊日志(N)时间内获取或设置元素,其中N是条目数:不必是线性时间,二元搜索是可接受的.
6. 在非病毒开源纯Java库中实现(最好在Maven Central中).

有谁知道这样的实用类？

我本来期望Commons Collections有一个,但它似乎没有.

我遇到的org.apache.commons.math.util.OpenIntToFieldHashMap看起来几乎是正确的,除了价值类型FieldElement似乎是无偿的; 我只想要T extends Object.它看起来很容易编辑它的源代码更通用,但我宁愿使用二进制依赖,如果有一个可用.

Answer 1

我会尝试用宝库收藏,有TIntObjectMap它可以为您的意图工作.

Answer 2

我会从 Android 的 SparseArray 实现中寻找灵感。您可以通过在此处下载 AOSP 的源代码来查看源代码http://source.android.com/source/downloading.html