SparseArray vs HashMap

Question

我可以想到为什么HashMap带有整数键的SparseArrays 比s 更好的几个原因:

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

然而,每当我尝试HashMap在Android项目中使用带整数键的时候,IntelliJ告诉我应该使用一个SparseArray代替.我觉得这很难理解.有谁知道使用SparseArrays的任何令人信服的理由？

Answer 1

SparseArrayHashMap当键是基本类型时,可以用来替换.对于不同的键/值类型,存在一些变体,即使并非所有键/值都是公开可用的.

好处是:

• 分配无
• 没拳击

缺点:

• 通常较慢,不适用于大型集合
• 它们不适用于非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 

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

SparseIntArray:

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

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

资料来源:Romain Guy的Android Memories,来自幻灯片90.

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

该java.lang.instrument软件包包含一些有用的高级操作方法,例如检查对象的大小getObjectSize(Object objectToSize).

可从Oracle官方文档中获取更多信息.

Class = 12字节+(n个实例变量)*4个字节
数组= 20个字节+(n个元素)*(元素大小)
Entry = 32个字节+(第1个元素大小)+(第2个元素大小)

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参数是整数键.

查找int键的值

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

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

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

迭代这些项目

您可以使用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

请注意,键按升序排序,而不是按添加顺序排序.

Answer 3

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

它只是来自稀疏数组的这个文档的警告:

与使用HashMap将整数映射到对象相比,它的内存效率更高

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

Answer 4

Java中的稀疏数组是将键映射到值的数据结构.与Map相同的想法,但不同的实现:

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

2. 稀疏数组简单地由两个数组组成:(基元)键的数组和(对象)值的数组.这些数组索引中可能存在间隙,因此称为"稀疏"数组.

SparseArray的主要兴趣在于它通过使用基元而不是对象作为关键来节省内存.

Answer 5

在谷歌搜索后,我尝试将一些信息添加到已经发布的答案中:

Isaac Taylor对SparseArrays和Hashmaps进行了性能比较.他说

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

和

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

对Edgblog的比较表明SparseArray需要比HashMap少得多的内存,因为密钥较小(int vs Integer),而且事实是

HashMap.Entry实例必须跟踪密钥,值和下一个条目的引用.另外,它还需要将条目的哈希值存储为int.

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

Answer 6

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

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

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

我认为大多数情况下我们只用来HashMap搜索与键关联的值，而SparseArray它确实擅长于此。

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

SparseArray 的源代码相当简单且易于理解，因此您只需花费很少的精力将其移动到其他平台（通过简单的复制和粘贴）。

Map 重写 equals() 和 hashCode() 而 SparseArray 则不然

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

的另一个重要方面是，它在使用SparseArray时仅使用数组来存储所有元素，因此比 a 消耗更少的内存，请参阅此HashMapEntrySparseArrayHashMap