java 使用 SparseIntArray 而不是 HashMap <Integer, Integer> 和 putSerializable

Using SparseIntArray instead of HashMap <Integer, Integer> with putSerializable

提问by VM4

When I use a HashMapwith an Integerkey and data values in Android I get this message in Eclipse:

当我在 Android 中使用HashMap带有Integer键和数据值的 a 时，我在 Eclipse 中收到此消息：

Use new SparseIntArray(...) for better performance

Now the problem is that SparseIntArray()doesn't implement the Serializableinterface and can't be used with getSerializable()and putSerializable()in onRestoreInstanceState().

现在的问题是SparseIntArray()没有实现Serializable接口，不能与getSerializable()and putSerializable()in一起使用onRestoreInstanceState()。

1. How important is using SparseIntArray()instead of the HashMap<Integer, Integer>?

2. Should I go through the trouble of making SparseIntArrayserializable? (My first idea is making a wrapper class that implements Serializable, is this the right way to go?)

1. 使用SparseIntArray()而不是有多重要HashMap<Integer, Integer>？

2. 我应该经历使可SparseIntArray序列化的麻烦吗？（我的第一个想法是制作一个实现 的包装类，Serializable这是正确的方法吗？）

回答by Stephen C

1) How important is using SparseIntArrayinstead of the HashMap?

1) 使用SparseIntArray而不是有多重要HashMap？

It depends on how you are using it. But unless you are trying to represent many and/or large "arrays" like this, the difference is unlikely to be significant.

这取决于您如何使用它。但是除非您尝试像这样表示许多和/或大型“数组”，否则差异不太可能很大。

Note that Java SE doesn't have any sparse array classes, and it is not normally an issue.

请注意，Java SE 没有任何稀疏数组类，这通常不是问题。

2) Should I go through the trouble of making SparseIntArrayserializable? (My first idea is making a wrapper class that implements Serializable, is this the right way to go?)

2）我应该经历使可SparseIntArray序列化的麻烦吗？（我的第一个想法是制作一个实现 的包装类，Serializable这是正确的方法吗？）

See above, and below.

见上，见下。

Implementing a wrapper sounds reasonable ... if you need to go to this trouble. Another approach might be to declare a serializable subclass of SparseIntArray. It would be advisable to declare custom readObjectand writeObjectmethods.

实现包装器听起来很合理……如果您需要解决这个问题。另一种方法可能是声明SparseIntArray. 建议声明自定义readObject和writeObject方法。

---

---

The SparseIntArrayclass (source code) uses a pair of intarrays to represent the keys and values in the mapping, and uses binary search to do the lookup. The keys are kept in order with no "holes" and lookup is performed using binary search. This means the following:

的SparseIntArray类（源代码）使用的一对int阵列来表示映射中的键和值，并使用二进制搜索做查找。键按顺序排列，没有“漏洞”，查找使用二分查找。这意味着：

• Memory usage for a SparseIntArraywill be roughly a factor of 10 less that for an equivalent HashMap. This is due to a combination of things:

  • the hash table array holds roughly 1 reference per entry (depending on how full the table is ...),

  • the keys and values have to be "boxed" as Integerobjects in a HashMap, and

  • each entry in a HashMaprequires a "node" object that is fairly heavy weight - 4 fields in the standard implementation.

  (However, if you create the Integerobjects the right way, the "boxing" overhead can be mitigated by the effects of the Integerclasses instance cache.)

  By contrast, the sparse version requires 2 * capacity4 byte words.

• Lookup (i.e. get) is O(logN)compared with O(1)for a HashMap.

• Random insertion is O(N)compared with O(1)for a HashMap. (This is because an insertion has to move on average half of the existing entries so that the new entry can be added at the correct position in the arrays.)

• Sequential insertion (i.e. in ascending in key order) is O(1).

• a 的内存使用量SparseIntArray大约是等效HashMap.的 10 倍。这是由于多种因素的组合：

  • 哈希表数组每个条目大约包含 1 个引用（取决于表的填充程度......），

  • 键和值必须“装箱”为 a 中的Integer对象HashMap，并且

  • a 中的每个条目都HashMap需要一个相当重的“节点”对象——标准实现中有 4 个字段。

  （但是，如果您Integer以正确的方式创建对象，则可以通过Integer类实例缓存的影响来减轻“装箱”开销。）

  相比之下，稀疏版本需要2 * capacity4 个字节的字。

• 查找（即get）O(logN)与O(1)for a进行比较HashMap。

• 随机插入O(N)与O(1)for a进行比较HashMap。（这是因为插入必须平均移动现有条目的一半，以便可以将新条目添加到数组中的正确位置。）

• 顺序插入（即按键顺序升序）是O(1)。

So "which is best" clearly depends on what you are optimizing for, how you use the data structure, and how big it is going to get.

因此，“哪个最好”显然取决于您要优化的对象、数据结构的使用方式以及数据结构的大小。

回答by Ted Hopp

The problem with using a HashMap<Integer, Integer>is that every key and value needs to be boxed. The impact of this can range from nothing to being a heavy load on the system from huge amounts of garbage generation and/or memory use (not to mention the slight performance penalty of boxing/unboxing values). (These concerns have also driven the development of several third-party collection frameworks for primitives.)

使用 a 的问题HashMap<Integer, Integer>是每个键和值都需要装箱。其影响范围可以从无到对系统造成沉重负担，因为大量垃圾生成和/或内存使用（更不用说装箱/拆箱值的轻微性能损失）。（这些担忧也推动了几个第三方原语集合框架的开发。）

If you decide that the benefits of SparseIntArrayare worth having, then I think your approach of a wrapper class is reasonable. An alternative would be to make it implement Parcelable, which can also be used to save/restore the instance state.

如果您认为 的好处SparseIntArray值得拥有，那么我认为您使用包装类的方法是合理的。另一种方法是让它实现Parcelable，它也可以用来保存/恢复实例状态。