Java中内存高效的稀疏数组

Question

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

我需要一个等价于List<T>或Map<Integer,T>的东西，它：

1. 可以通过将键设置为大于之前遇到的任何键来随需增长。（可以假设键是非负的。）
2. 在大多数索引不为null的情况下，与ArrayList<T>一样占用内存效率，即实际数据不是非常稀疏的情况下。
3. 当索引稀疏时，消耗与非null索引数量成比例的空间。
4. 使用比HashMap<Integer,T>更少的内存（因为这会自动装箱键，并且可能不利用标量键类型的优势）。
5. 可以在摊销log(N)时间内获取或设置条目，其中N是条目数：不需要是线性时间，二分查找也可以接受。
6. 在非病毒开源纯Java库中实现（最好在Maven Central中）。

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

我本来以为Commons Collections会有一个，但似乎没有。

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

- Jesse Glick

Answer 1

我建议尝试使用Trove集合，其中有TIntObjectMap适用于您的意图。

- Jack

---

看起来不错。我尝试将OpenIntToFieldHashMap适应为通用值类型，经过约10分钟的工作，似乎已经成功了，但它的性能仅比TIntObjectMap略好。 - Jesse Glick

Answer 2

我会建议你参考Android的SparseArray实现。你可以通过下载AOSP源代码在这里查看源代码：http://source.android.com/source/downloading.html。

- Florian Laplantif

---

https://code.google.com/p/android-source-browsing/source/browse/core/java/android/util/SparseArray.java?spec=svn.platform--frameworks--base.58aff7debfdab8ca99dd6bfcfa0c7bebdf2d303b&repo=platform--frameworks--base&r=58aff7debfdab8ca99dd6bfcfa0c7bebdf2d303b 看起来很合适 - 摊销运行时间未经记录，但从检查中我猜测它是对数级别的 - 并且在 ASL 2.0 下，这很好。不幸的是，我不知道它是否在 Central 中，并且希望它与无关的东西（如 Android 蓝牙支持）分离开来，这些东西都在同一个源根目录中。 - Jesse Glick

这里有一个自包含版本，它使用了来自Android的所有必要代码。https://github.com/frostwire/frostwire-jlibtorrent/blob/b4b3f9a90d7a1dade864d7e3eaa88b616f200a9a/src/com/frostwire/jlibtorrent/SparseArray.java - Gubatron

你可能更精确地寻找 SparseIntArray，它可以避免装箱/拆箱索引的成本。https://developer.android.com/reference/android/util/SparseIntArray 如果需要，源代码是可用的，并且具有易于使用的许可证，您可以从 Google 代码库中提取并进行适应。 - Yann TM

Answer 3

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

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

- Jesse Glick

---

我在哪里可以找到IntHashMap？ - oleh

@oleh 可能是 apache commons（？） - Karussell

抱歉，IntHashMap 是我从 Commons Math 中改编的 OpenIntToFieldHashMap。由于它几乎比 TIntObjectMap 好不了多少，所以我放弃了这种方法。 - Jesse Glick

@JesseGlick 请查看 http://java.dzone.com/articles/time-memory-tradeoff-example 和 https://gist.github.com/leventov/bc14ea790b4d3cfd238d#file-memory-txt。 - leventov

在你的回答中，只比较了不同的哈希表实现。我参考了另一个比较，其中包括你测试过的所有实现以及更多内容。 - leventov

Answer 4

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

- abhi

---

谢谢你的建议。它确实比其他替代方案具有适度但显著较低的空间消耗。我已经将其包含在我的修订测试用例中。 - Jesse Glick

Answer 5

虽然回答晚了，但是在libgdx中有IntMap，它使用cuckoo hashing。如果可以的话，与其他方法进行比较会很有趣。

- NateS