Java 中的内存高效稀疏数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12626135/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Memory-efficient sparse array in Java
提问by Jesse Glick
(There are some questions about time-efficient sparse arrays but I am looking for memory efficiency.)
（有一些关于节省时间的稀疏数组的问题，但我正在寻找内存效率。）
I need the equivalent of a List<T>or Map<Integer,T>which
我需要相当于 aList<T>或Map<Integer,T>which
- Can grow on demand just by setting a key larger than any encountered before. (Can assume keys are nonnegative.)
- Is about as memory-efficient as an
ArrayList<T>in the case that most of the indices are notnull, i.e. when the actual data is not very sparse. - When the indices are sparse, consumes space proportional to the number of non-
nullindices. - Uses less memory than
HashMap<Integer,T>(as this autoboxes the keys and probably does not take advantage of the scalar key type). - 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.
- Implemented in a nonviral open-source pure Java library (preferably in Maven Central).
- 只需设置一个比以前遇到的任何密钥都大的密钥，就可以按需增长。（可以假设键是非负的。）
ArrayList<T>在大多数索引都不是的情况下null，即实际数据不是很稀疏时，它的内存效率大致相同。- 当索引稀疏时，消耗的空间与非
null索引的数量成正比。 - 使用的内存少于
HashMap<Integer,T>（因为这会自动装箱键并且可能不利用标量键类型）。 - 可以在摊销 log(N) 时间内获取或设置元素，其中 N 是条目数：不需要是线性时间，二进制搜索是可以接受的。
- 在非病毒开源纯 Java 库中实现（最好在 Maven Central 中）。
Does anyone know of such a utility class?
有谁知道这样的实用程序类？
I would have expected Commons Collections to have one but it did not seem to.
我原以为 Commons Collections 会有一个，但似乎没有。
I came across org.apache.commons.math.util.OpenIntToFieldHashMapwhich looks almost right except the value type is a FieldElementwhich 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.
我发现org.apache.commons.math.util.OpenIntToFieldHashMap它看起来几乎是正确的，除了值类型是 aFieldElement似乎是无缘无故的；我只是想要T extends Object。看起来很容易编辑其源代码以使其更通用，但如果可用，我宁愿使用二进制依赖项。
采纳答案by Hyman
I would try with trovecollections, there is TIntObjectMapwhich can work for your intents.
我会尝试宝库收藏，有TIntObjectMap它可以为您的意图工作。
回答by Florian Laplantif
I would look at Android's SparseArray implementation for inspiration. You can view the source by downloading AOSP's source code here http://source.android.com/source/downloading.html
我会从 Android 的 SparseArray 实现中寻找灵感。您可以通过在此处下载 AOSP 的源代码来查看源代码http://source.android.com/source/downloading.html
回答by abhi
回答by Jesse Glick
I have saved my test case as jglick/inthashmap. The results:
我已将我的测试用例保存为jglick/inthashmap。结果：
HashMap size: 1017504
TIntObjectMap size: 853216
IntHashMap size: 846984
OpenIntObjectHashMap size: 760472
回答by NateS
Late to this question, but there is IntMapin libgdx which uses cuckoo hashing. If anything it would be interesting to compare with the others.
这个问题迟到了，但是libgdx中有 IntMap 使用 cuckoo hashing。如果有的话，与其他人进行比较会很有趣。
