使用SparseIntArray替代HashMap <Integer, Integer>与putSerializable

Question

当我在Android中使用HashMap，键为Integer类型，值为数据时，在Eclipse中会出现以下消息：

Use new SparseIntArray(...) for better performance

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

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

2. 我是否应该费力将 SparseIntArray 变成可序列化的对象？（我的第一个想法是创建一个实现了 Serializable 的包装类，这样做正确吗？）

- VM4

Answer 1

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

这取决于您的使用方式。但除非您正在尝试表示许多和/或大型类似数组的内容，否则差异不太可能显著。

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

2) 我是否应该费心使 SparseIntArray 可序列化？（我最初的想法是创建一个实现 Serializable 的包装器类，这样做正确吗？）

参见上文和下文。

如果你需要这么费力实现一个包装器，那听起来是合理的...另一种方法可能是声明一个可序列化的 SparseIntArray 子类。建议声明自定义的 readObject 和 writeObject 方法。

---

SparseIntArray 类(源代码)使用一对 int 数组表示映射中的键和值，并使用二进制搜索进行查找。键以无“空洞”的顺序保持，并使用二进制搜索执行查找。这意味着以下：

• 与等效的 HashMap 相比，SparseIntArray 的内存使用量大约少了10倍左右。这是由多种因素造成的：

  • 哈希表数组每个条目（取决于表格有多满...）需要大约1个引用。

  • 在 HashMap 中，键和值必须作为 Integer 对象进行“包装”，

  每个 HashMap 条目需要一个“节点”对象，这在标准实现中是比较庞大的 - 有 4 个字段。
  
  （但是，如果以正确的方式创建 Integer 对象，则“装箱”开销可以通过 Integer 类的实例缓存来减轻。）
  
  相比之下，稀疏版本需要 2 * capacity 4 字节字。
  
  查找（即 get）为 O(logN)，与 HashMap 的 O(1) 相比。
  
  随机插入为 O(N)，与 HashMap 的 O(1) 相比。（这是因为插入平均需要移动一半的现有条目，以便新条目可以添加到数组的正确位置。）
  
  顺序插入（即按键升序）为 O(1)。
  
  因此，“哪个最好”显然取决于您要优化什么，如何使用数据结构以及它会变得多大。

- Stephen C

Answer 2

使用HashMap<Integer, Integer>的问题在于每个键和值都需要装箱。这可能会对系统产生从垃圾生成和/或内存使用的巨大负载（更不用说装箱/拆箱值的轻微性能惩罚）的影响，但也促使开发了几个第三方基元集合框架。如果您认为使用SparseIntArray带来的好处是值得的，那么我认为您的包装类方法是合理的。另一种选择是使其实现Parcelable，这也可以用于保存/恢复实例状态。

- Ted Hopp