Java SparseArray 与 HashMap

SparseArray vs HashMap

提问by Paul Boddington

I can think of several reasons why HashMaps with integer keys are much better than SparseArrays:

我可以想到几个原因，为什么HashMap带有整数键的SparseArrays比s好得多：

1. The Android documentation for a SparseArraysays "It is generally slower than a traditional HashMap".
2. If you write code using HashMaps rather than SparseArrays your code will work with other implementations of Map and you will be able to use all of the Java APIs designed for Maps.
3. If you write code using HashMaps rather than SparseArrays your code will work in non-android projects.
4. Map overrides equals()and hashCode()whereas SparseArraydoesn't.

1. a 的 Android 文档SparseArray说“它通常比传统的慢HashMap”。
2. 如果您使用HashMaps 而不是SparseArrays编写代码，您的代码将与 Map 的其他实现一起使用，并且您将能够使用为 Maps 设计的所有 Java API。
3. 如果您使用HashMaps 而不是SparseArrays编写代码，您的代码将在非 android 项目中工作。
4. 地图覆盖equals()，hashCode()而SparseArray没有。

Yet whenever I try to use a HashMapwith integer keys in an Android project, IntelliJ tells me I should use a SparseArrayinstead. I find this really difficult to understand. Does anyone know any compelling reasons for using SparseArrays?

然而，每当我尝试HashMap在 Android 项目中使用带有整数键的a时，IntelliJ 都会告诉我应该使用 aSparseArray代替。我觉得这真的很难理解。有谁知道使用SparseArrays 的任何令人信服的理由？

采纳答案by Sarpe

SparseArraycan be used to replace HashMapwhen the key is a primitive type. There are some variants for different key/value types, even though not all of them are publicly available.

SparseArrayHashMap当键是原始类型时可用于替换。不同的键/值类型有一些变体，尽管并非所有变体都是公开可用的。

Benefits are:

好处是：

• Allocation-free
• No boxing

• 免分配
• 没有拳击

Drawbacks:

缺点：

• Generally slower, not indicated for large collections
• They won't work in a non-Android project

• 通常较慢，不适用于大型集合
• 它们不会在非 Android 项目中工作

HashMapcan be replaced by the following:

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 

In terms of memory, here is an example of SparseIntArrayvs HashMap<Integer, Integer>for 1000 elements:

在内存方面，以下是1000 个元素的SparseIntArrayvs示例HashMap<Integer, Integer>：

SparseIntArray:

SparseIntArray：

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

Class = 12 + 3 * 4 = 24 bytes
Array = 20 + 1000 * 4 = 4024 bytes
Total = 8,072 bytes

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

HashMap:

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 bytes
Entry = 32 + 16 + 16 = 64 bytes
Array = 20 + 1000 * 64 = 64024 bytes
Total = 64,136 bytes

类 = 12 + 8 * 4 = 48 字节
条目 = 32 + 16 + 16 = 64 字节
数组 = 20 + 1000 * 64 = 64024 字节
总计 = 64,136 字节

Source: Android Memories by Romain Guyfrom slide 90.

来源：来自幻灯片 90 的Romain Guy 的 Android Memories。

The numbers above are the amount of memory (in bytes) allocated on heap by JVM. They may vary depending on the specific JVM used.

上面的数字是 JVM 在堆上分配的内存量（以字节为单位）。它们可能因所使用的特定 JVM 而异。

The java.lang.instrumentpackage contains some helpful methods for advanced operations like checking the size of an object with getObjectSize(Object objectToSize).

该java.lang.instrument包包含一些用于高级操作的有用方法，例如使用getObjectSize(Object objectToSize).

Extra info is available from the official Oracle documentation.

额外信息可从官方Oracle 文档中获得。

Class = 12 bytes + (n instance variables) * 4 bytes
Array = 20 bytes + (n elements) * (element size)
Entry = 32 bytes + (1st element size) + (2nd element size)

类 = 12 字节 +（n 个实例变量）* 4 字节
数组 = 20 字节 +（n 个元素）*（元素大小）
条目 = 32 字节 +（第一个元素大小）+（第二个元素大小）

回答by suitianshi

The android documentation for a SparseArray says "It is generally slower than a traditional HashMap".

SparseArray 的 android 文档说“它通常比传统的 HashMap 慢”。

Yes,it's right. But when you have only 10 or 20 items , the performance difference should be insignificant.

是的这是对的。但是当你只有 10 或 20 个项目时，性能差异应该是微不足道的。

If you write code using HashMaps rather than SparseArrays your code will work with other implementations of Map and you will be able to use all of the java APIs designed for Maps

如果您使用 HashMaps 而不是 SparseArrays 编写代码，您的代码将与 Map 的其他实现一起使用，并且您将能够使用为 Maps 设计的所有 Java API

I think most often we only use HashMapto search a value associated with a key while SparseArrayis really good at this.

我认为大多数情况下我们只用于HashMap搜索与键相关联的值，而这SparseArray方面非常擅长。

If you write code using HashMaps rather than SparseArrays your code will work in non-android projects.

如果您使用 HashMaps 而不是 SparseArrays 编写代码，您的代码将在非 android 项目中工作。

The source code of SparseArray is fairly simple and easy to understand so that you only pay little effort moving it to other platforms(through a simple COPY&Paste).

SparseArray 的源代码相当简单易懂，因此您只需花费很少的精力将其移动到其他平台（通过简单的 COPY&Paste）。

Map overrides equals() and hashCode() whereas SparseArray doesn't

Map 覆盖 equals() 和 hashCode() 而 SparseArray 不

All I can say is, (to most developers)who care?

我只能说，（对大多数开发人员）谁在乎？

Another important aspect of SparseArrayis that it only uses an array to store all elements while HashMapuses Entry, so SparseArraycosts significant less memory than a HashMap, see this

的另一个重要方面SparseArray是，它仅使用一个数组来存储所有元素而HashMap使用Entry，所以SparseArray成本比一个显著较少的内存HashMap，看到此

回答by Rod_Algonquin

Yet whenever I try to use a HashMap with integer keys in an android project, intelliJ tells me I should use a SparseArray instead.

然而，每当我尝试在 android 项目中使用带有整数键的 HashMap 时，intelliJ 都会告诉我应该改用 SparseArray。

It is only a warning from this documentationof it sparse array:

这只是它稀疏数组的文档中的一个警告：

It is intended to be more memory efficient than using a HashMap to map Integers to Objects

它旨在比使用 HashMap 将整数映射到对象具有更高的内存效率

The SparseArrayis made to be memory efficientthan using the regular HashMap, that is does not allow multiple gaps within the array not like HashMap. There is nothing to worry about it you can use the traditional HashMap if you desire not worrying about the memory allocation to the device.

该SparseArray被制成存储器高效比使用常规的HashMap，即不允许该阵列不喜欢的HashMap内的多个间隙。没有什么可担心的，如果您不想担心设备的内存分配，您可以使用传统的 HashMap。

回答by Ganesh Katikar

A sparse array in Java is a data structure which maps keys to values. Same idea as a Map, but different implementation:

Java 中的稀疏数组是一种将键映射到值的数据结构。与 Map 相同的想法，但不同的实现：

1. A Map is represented internally as an array of lists, where each element in these lists is a key,value pair. Both the key and value are object instances.

2. A sparse array is simply made of two arrays: an arrays of (primitives) keys and an array of (objects) values. There can be gaps in these arrays indices, hence the term “sparse” array.

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

2. 稀疏数组简单地由两个数组组成：（原语）键数组和（对象）值数组。这些数组索引中可能存在间隙，因此称为“稀疏”数组。

The main interest of the SparseArray is that it saves memory by using primitives instead of objects as the key.

SparseArray 的主要兴趣在于它通过使用原语而不是对象作为键来节省内存。

回答by Bruce

It's unfortunate that the compiler issues a warning. I guess HashMap has been way overused for storing items.

不幸的是，编译器发出警告。我猜 HashMap 已经被过度用于存储项目。

SparseArrays have their place. Given they use a binary search algorithm to find a value in an array you have to consider what you are doing. Binary search is O(log n) while hash lookup is O(1). This doesn't necessarily mean that binary search is slower for a given set of data. However, as the number of entries grows, the power of the hash table takes over. Hence the comments where low number of entries can equal and possibly be better than using a HashMap.

SparseArrays 有自己的位置。鉴于他们使用二进制搜索算法在数组中查找值，您必须考虑自己在做什么。二分查找是 O(log n) 而哈希查找是 O(1)。这并不一定意味着二进制搜索对于给定的数据集较慢。然而，随着条目数量的增加，哈希表的力量会接管。因此，条目数量少的评论可能等于并且可能比使用 HashMap 更好。

A HashMap is only as good as the hash and also can be impacted by load factor (I think in later versions they ignore the load factor so it can be better optimized). They also added a secondary hash to make sure the hash is good. Also the reason SparseArray works really well for relatively few entries (<100).

HashMap 与散列一样好，也可能受负载因子的影响（我认为在以后的版本中它们会忽略负载因子，因此可以更好地优化）。他们还添加了一个二级散列以确保散列是好的。这也是 SparseArray 对于相对较少的条目（<100）非常有效的原因。

I would suggest that if you need a hash table and want better memory usage for primitive integer (no auto boxing), etc., try out trove. (http://trove.starlight-systems.com- LGPL license). (No affiliation with trove, just like their library)

我建议，如果您需要一个哈希表并希望更好地使用原始整数（无自动装箱）等的内存，请尝试使用 trove。（http://trove.starlight-systems.com- LGPL 许可）。（与 trove 没有任何关系，就像他们的图书馆一样）

With the simplified multi-dex building we have you don't even need to repackage trove for what you need. (trove has a lot of classes)

使用简化的多 dex 构建，您甚至不需要为您需要的东西重新打包 trove。（trove有很多课程）

回答by Sebastian

After some googling I try to add some information to the already posted anwers:

经过一些谷歌搜索后，我尝试向已经发布的答案添加一些信息：

Isaac Taylormade a performance comparision for SparseArrays and Hashmaps. He states that

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

the Hashmap and the SparseArray are very similar for data structure sizes under 1,000

对于 1,000 以下的数据结构大小，Hashmap 和 SparseArray 非常相似

and

和

when the size has been increased to the 10,000 mark [...] the Hashmap has greater performance with adding objects, while the SparseArray has greater performance when retrieving objects. [...] At a size of 100,000 [...] the Hashmap loses performance very quickly

当大小增加到 10,000 标记时 [...] Hashmap 在添加对象时具有更高的性能，而 SparseArray 在检索对象时具有更高的性能。[...] 大小为 100,000 [...] Hashmap 很快就会失去性能

An comparision on Edgblogshows that a SparseArray need much less memory than a HashMap because of the smaller key (int vs Integer) and the fact that

Edgblog上的比较表明 SparseArray 比 HashMap 需要的内存少得多，因为键较小（int vs Integer）以及

a HashMap.Entry instance must keep track of the references for the key, the value and the next entry. Plus it also needs to store the hash of the entry as an int.

HashMap.Entry 实例必须跟踪键、值和下一个条目的引用。此外，它还需要将条目的哈希存储为 int。

As a conclusion I would say that the difference could matter if you are going to store a lot of data in your Map. Otherwise, just ignore the warning.

作为结论，我会说如果您要在 Map 中存储大量数据，差异可能很重要。否则，只需忽略警告。

回答by Suragch

I came here just wanting an example of how to use SparseArray. This is a supplemental answer for that.

我来到这里只是想要一个如何使用SparseArray. 这是对此的补充答案。

Create a SparseArray

创建一个稀疏数组

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

A SparseArraymaps integers to some Object, so you could replace Stringin the example above with any other Object. If you are mapping integers to integers then use SparseIntArray.

ASparseArray将整数映射到 some Object，因此您可以将String上面的示例中的任何其他Object. 如果要将整数映射到整数，请使用SparseIntArray.

Add or update items

添加或更新项目

Use put(or append) to add elements to the array.

使用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");

Note that the intkeys do not need to be in order. This can also be used to change the value at a particular intkey.

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

Remove items

删除项目

Use remove(or delete) to remove elements from the array.

使用remove(或delete) 从数组中删除元素。

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

The intparameter is the integer key.

该int参数是整数键。

Lookup values for an int key

int 键的查找值

Use getto get the value for some integer key.

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

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

You can use get(int key, E valueIfKeyNotFound)if you want to avoid getting nullfor missing keys.

get(int key, E valueIfKeyNotFound)如果您想避免null丢失钥匙，您可以使用。

Iterate over the items

迭代项目

You can use keyAtand valueAtsome index to loop through the collection because the SparseArraymaintains a separate index distinct from the intkeys.

您可以使用keyAtand valueAtsome index 来循环遍历集合，因为它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

Note that the keys are ordered in ascending value, not in the order that they were added.

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