10

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

我需要相当于 a List<T>or Map<Integer,T>which

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

有谁知道这样的实用程序类？

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

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

4

5 回答 5

6

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

于 2012-09-27T16:49:08.270 回答
5

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

于 2013-04-22T03:50:34.127 回答
1

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

HashMap size: 1017504
TIntObjectMap size: 853216
IntHashMap size: 846984
OpenIntObjectHashMap size: 760472
于 2012-09-27T17:08:52.870 回答
1

我会建议你使用 Colt 库中的 OpenIntObjectHashMap。关联

于 2014-05-13T19:30:25.090 回答
0

这个问题迟到了，但是libgdx中有 IntMap 使用 cuckoo hashing。如果有的话，与其他人比较会很有趣。

于 2018-09-19T23:06:33.160 回答