SparseArray与HashMap的区别

Question

我能想到几个原因，解释为什么使用整数键的 HashMap 比 SparseArray 好：

1. SparseArray 的 Android 文档中说 "它通常比传统的 HashMap 慢"。
2. 如果你使用 HashMap 而不是 SparseArray 编写代码，你的代码将与 Map 的其他实现一起工作，并且可以使用为 Maps 设计的所有 Java API。
3. 如果你使用 HashMap 而不是 SparseArray 编写代码，你的代码将在非 Android 项目中工作。
4. Map 覆盖了 equals() 和 hashCode()，而 SparseArray 没有。

然而，每当我尝试在 Android 项目中使用具有整数键的 HashMap 时，IntelliJ 都会告诉我应该使用 SparseArray。我发现这真的很难理解。有人知道使用 SparseArray 的令人信服的理由吗？

- Paul Boddington

Answer 1

SparseArray可用于替换HashMap，当键是原始类型时。

有一些变量适用于不同的键/值类型，尽管并非所有变量都是公开的。

优点如下：

• 无需分配内存
• 无装箱操作

缺点如下：

• 通常速度较慢，不适用于大型集合
• 它们在非Android项目中无法使用

HashMap可以被以下内容替换：

SparseArray          <Integer, Object>
SparseBooleanArray   <Integer, Boolean>
SparseIntArray       <Integer, Integer>
SparseLongArray      <Integer, Long>
LongSparseArray      <Long, Object>
LongSparseLongArray  <Long, Long>   //this is not a public class                                 
                                    //but can be copied from  Android source code 

关于内存，这里是 SparseIntArray 与 HashMap<Integer, Integer> 在1000个元素下的比较实例：

SparseIntArray:

class SparseIntArray {
    int[] keys;
    int[] values;
    int size;
}

类 = 12 + 3 * 4 = 24 字节
数组 = 20 + 1000 * 4 = 4024 字节
总计 = 8,072 字节

HashMap：

class HashMap<K, V> {
    Entry<K, V>[] table;
    Entry<K, V> forNull;
    int size;
    int modCount;
    int threshold;
    Set<K> keys
    Set<Entry<K, V>> entries;
    Collection<V> values;
}

Class = 12 + 8 * 4 = 48 字节
Entry = 32 + 16 + 16 = 64 字节
Array = 20 + 1000 * 64 = 64024 字节
Total = 64,136 字节

来源：Romain Guy 的《Android Memories》第 90 张幻灯片。

以上数字表示 JVM 在堆上分配的内存量（以字节为单位）。具体取决于所使用的 JVM。

java.lang.instrument 包中包含一些有用的方法，如使用 getObjectSize(Object objectToSize) 检查对象大小等高级操作。

更多信息可以在官方 Oracle 文档 中找到。

Class = 12 字节 + （n 个实例变量）* 4 字节
Array = 20 字节 + （n 元素）*（元素大小）
Entry = 32 字节 + （第一个元素大小）+ （第二个元素大小）

- Sarpe

---

有人能告诉我那些"12 + 3 * 4"和"20 + 1000 * 4"是从哪里来的吗？请翻译这段文字。 - Marian Paździoch

@MarianPaЕәdziochеұ•зӨәдәҶдёҖдёӘжј”зӨәж–ҮзЁҝпјҲhttps://speakerdeck.com/romainguy/android-memoriesпјүпјҢе…¶дёӯдёҖдёӘзұ»еҚ з”Ё12дёӘеӯ—иҠӮ+3дёӘ4дёӘеӯ—иҠӮзҡ„еҸҳйҮҸпјҢдёҖдёӘж•°з»„пјҲеј•з”ЁпјүеҚ з”Ё20дёӘеӯ—иҠӮпјҲdlmalloc-4пјҢеҜ№иұЎејҖй”Җ-8пјҢе®ҪеәҰе’ҢеЎ«е……-8пјүгҖӮ - CoolMind

值得一提的是，SparseArray 的另一个关键缺点是作为 Android 对象，需要在单元测试中进行模拟。在可能的情况下，我现在使用 Java 自己的对象来简化测试。 - David G

@DavidG 你可以使用 unmock 插件 来模拟 Android 依赖项。 - blizzard

即使您不是在做Android，将该类复制到您的项目中也不难，它只依赖于其他3个类。APL许可证意味着无论您使用哪种许可证都可以这样做。 - Yann TM

Answer 2

我来这里只是想找一个如何使用SparseArray的示例。以下是这个问题的补充答案。

创建一个SparseArray

SparseArray<String> sparseArray = new SparseArray<>();

SparseArray 是一种将整数映射到某些 Object 的数据结构，因此您可以在上面的示例中将 String 替换为任何其他 Object。如果您正在将整数映射到整数，则请使用SparseIntArray。

添加或更新项

使用put（或append）向数组中添加元素。

sparseArray.put(10, "horse");
sparseArray.put(3, "cow");
sparseArray.put(1, "camel");
sparseArray.put(99, "sheep");
sparseArray.put(30, "goat");
sparseArray.put(17, "pig");

请注意，int键不需要按顺序排列。这也可用于更改特定 int 键处的值。

删除项目

使用 remove（或 delete）从数组中删除元素。

sparseArray.remove(17); // "pig" removed

int参数是整数键。

查找整数键的值

使用get获取某个整数键的值。

String someAnimal = sparseArray.get(99);  // "sheep"
String anotherAnimal = sparseArray.get(200); // null

如果你想避免获取缺少键时的null值，可以使用get(int key, E valueIfKeyNotFound)。

要遍历集合，可以使用keyAt和valueAt方法以某个索引开始循环，因为SparseArray维护了一个与int键不同的单独索引。

int size = sparseArray.size();
for (int i = 0; i < size; i++) {

    int key = sparseArray.keyAt(i);
    String value = sparseArray.valueAt(i);

    Log.i("TAG", "key: " + key + " value: " + value);
}

// key: 1 value: camel
// key: 3 value: cow
// key: 10 value: horse
// key: 30 value: goat
// key: 99 value: sheep

请注意，键按升序排列，而不是按它们添加的顺序排列。

- Suragch

Answer 3

无论何时，我尝试在Android项目中使用带有整数键的HashMap时，IntelliJ都会告诉我应该使用SparseArray。

只是来自稀疏数组文档的一个警告：

它旨在比使用HashMap将整数映射到对象更节省内存。

SparseArray被设计为比常规HashMap更加节省内存，它不允许数组内有多个间隙，这与HashMap不同。如果您不担心设备的内存分配，可以使用传统的HashMap，没有什么可担心的。

- Rod_Algonquin

---

关于节省内存的观点显然是有效的，但我从未理解为什么Android不能使SparseArray<T>实现Map<Integer, T>，这样你就可以得到一个高效的内存Map实现 - 两全其美。 - Paul Boddington

请注意 SparseArray 可以避免将键整数自动装箱为对象，因此可以提高性能。与使用 Map 不同，它不会将基本类型整数自动装箱为 Integer 对象。 - Rod_Algonquin

集合是基于对象而不是基本类型的，因此它在集合API中无法使用。 - Rod_Algonquin

@PaulBoddington，如果SparseArray<T>实现了Map<Integer, T>并且还定义了一个重载方法，例如接受int的put方法，那么有两种可能性： - Davide Cannizzo

2/4：如果您持有类型为SparseArray的引用并在其上调用put，则使用重载的put方法且不涉及装箱 - 但这会破坏实现Map的目的。 - Davide Cannizzo

Answer 4

经过一番搜索，我试图给已有答案添加一些信息：

Isaac Taylor 对SparseArrays和Hashmaps进行了性能比较。他指出：

当数据结构的大小小于1,000时，Hashmap和SparseArray非常相似。

而且

当大小增加到10,000个标记时[...] Hashmap在添加对象方面具有更好的性能，而SparseArray在检索对象时具有更好的性能。[...] 当大小达到100,000 [...]时，Hashmap的性能迅速下降。

Edgblog上的比较表明，由于键（int vs Integer）更小，以及事实上一个HashMap.Entry实例必须跟踪键，值和下一个条目的引用，再加上需要将该条目的哈希存储为int，因此SparseArray需要比HashMap少得多的内存。

总之，如果您打算在Map中存储大量数据，则这种差异可能很重要。否则，只需忽略警告。

- Sebastian

Answer 5

Java中的稀疏数组是一种将键映射到值的数据结构。和映射（Map）的概念相同，但实现不同：

1. 映射（Map）在内部表示为列表数组，其中这些列表中的每个元素都是键值对。键和值都是对象实例。

2. 稀疏数组仅由两个数组组成：一个由基本类型的键组成的数组和一个由对象值组成的数组。这些数组索引中可能存在空隙，因此称之为“稀疏”数组。

稀疏数组的主要优点在于它使用基本类型的键而非对象作为键，从而节省了内存。

- Ganesh Katikar

Answer 6

Android文档中对SparseArray的描述是“它通常比传统的HashMap慢”。是的，这是正确的。但是当你只有10或20个项时，性能差异应该是微不足道的。

如果您使用HashMap而不是SparseArray编写代码，则您的代码将适用于Map的其他实现，并且您将能够使用为Map设计的所有Java API。

我认为我们大多数人只使用HashMap来搜索与键相关联的值，而SparseArray确实非常擅长此项工作。

如果您使用HashMap而不是SparseArray编写代码，则您的代码将在非Android项目中运行。

SparseArray的源代码非常简单易懂，因此只需付出很少的努力即可将其移植到其他平台（通过简单的复制和粘贴）。

Map覆盖了equals()和hashCode()，而SparseArray没有。我所能说的是，对于大多数开发人员来说，谁会关心呢？

另一个重要方面的 SparseArray 是它只使用数组来存储所有元素，而 HashMap 使用 Entry。因此，SparseArray 比 HashMap 使用的内存少得多，详情请参见this。

- suitianshi

Answer 7

很遗憾编译器发出了警告。我猜HashMap已经被过度使用来存储项目了。

SparseArrays有它们的用处。考虑到它们使用二进制搜索算法在数组中查找值，你必须考虑你正在做什么。二进制搜索是O(log n)，而哈希查找是O(1)。这并不一定意味着对于给定的数据集，二进制搜索会更慢。然而，随着条目数量的增加，哈希表的优势开始显现。因此，在条目数量较少时，使用SparseArray可能等效甚至比使用HashMap更好。

一个哈希表只有它的哈希函数好才能够发挥好的性能，并且也会受到负载因素的影响（我认为在后面的版本中，它们忽略了负载因素，所以可以进行更好的优化）。他们还添加了一个次级哈希来确保哈希的质量。同样的原因，SparseArray对于相对较少的项（<100）非常有效。

如果您需要哈希表并想要更好的原始整数内存使用情况（没有自动装箱等），请尝试使用trove。（http://trove.starlight-systems.com - LGPL许可证）。 （与trove无关，只是喜欢他们的库）

随着简化的多DEX构建，您甚至不需要重新打包trove以获取您所需的内容。（trove有很多类）

- Bruce