Java中的内存高效稀疏数组

（关于时间有效的稀疏数组有一些问题，但我正在寻找内存效率。）

我需要等效的List或Map

1. 只需设置一个比以前遇到的更大的密钥，就可以按需增长。 （可以假设密钥是非负的。）
2. 在大多数索引不为null的情况下，即当实际数据不是非常稀疏时，与ArrayList一样具有内存效率。
3. 当索引稀疏时，消耗与非null索引的数量成比例的空间。
4. 使用比HashMap更少的内存（因为这会自动锁定密钥并且可能不利用标量密钥类型）。
5. 可以在分摊日志（N）时间内获取或设置元素，其中N是条目数：不必是线性时间，二进制搜索是可接受的。
6. 在非病毒开源纯Java库中实现（最好在Maven Central中）。

有谁知道这样的实用类？

我本来期望Commons Collections有一个，但似乎没有。

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

Answer 1

我会尝试使用trove集合，有TIntObjectMap可以为你的意图工作。

Answer 2

我会看看Android的SparseArray实现的灵感。 您可以在http://source.android.com/source/downloading.html上下载AOSP的源代码来查看源代码

Answer 3

我建议你使用Colt库中的OpenIntObjectHashMap。 链接

Answer 4

我已将测试用例保存为jglick / inthashmap 。 结果：

 HashMap size: 1017504 TIntObjectMap size: 853216 IntHashMap size: 846984 OpenIntObjectHashMap size: 760472 

Answer 5

在这个问题的后期，但libgdx中有IntMap使用cuckoo 哈希 。 如果有的话，与其他人比较会很有趣。