SparseArray vs HashMap

我可以想到为什么HashMap与整数键比SparseArray更好的几个原因:

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

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

当密钥是原始types时,可以使用稀疏数组来replace哈希映射。 尽pipe不是所有的都是公开的,但是对于不同的键/值types有一些变体。

好处是:

  • 分配无
  • 没有拳击

缺点:

  • 一般来说比较慢,不适用于大集合
  • 他们不会在非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 vs HashMap 1000个元素的例子

SparseIntArray:

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

Class = 12 + 3 * 4 = 24个字节
arrays= 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个字节
条目= 32 + 16 + 16 = 64字节
arrays= 20 + 1000 * 64 = 64024字节
总计= 64,136字节

来源:幻灯片90中Romain Guy的Android Memories

上面的数字是JVM在堆上分配的内存量(以字节为单位)。 它们可能会根据所使用的特定JVM而有所不同。

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

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

类= 12字节+(n个实例variables)* 4字节
数组= 20字节+(n个元素)*(元素大小)
条目= 32字节+(第一个元素大小)+(2ns元素大小)

然而,无论何时我尝试在Android项目中使用带有整数键的HashMap,intelliJ告诉我应该使用SparseArray。

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

它的目的是比使用HashMap将整数映射到对象更有效率

SparseArray与使用常规HashMap相比,具有更高的内存效率 ,即不会像HashMap那样允许多个间隙。 没有什么可担心的,你可以使用传统的HashMap,如果你不想担心分配给设备的内存。

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

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

  2. 一个稀疏数组只是由两个数组组成:一个(基元)键数组和一个(对象)数组数组。 这些数组索引中可能存在间隙,因此术语“稀疏”数组。

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

一些谷歌search后,我尝试添加一些信息到已经发布的awers:

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

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

当大小增加到10,000时,Hashmap在添加对象时具有更高的性能,而SparseArray在检索对象时具有更高的性能。 […]在10万个大小的Hashmap失去了很快的performance

Edgblog上的一个比较表明,SparseArray需要比HashMapless得多的内存,因为较小的键(int vs Integer)和事实

HashMap.Entry实例必须跟踪关键字,值和下一个条目的引用。 另外它还需要将条目的散列存储为int。

作为一个结论,我会说,如果你要在你的地图中存储大量的数据,差异可能会很重要。 否则,只要忽略警告即可。

我来这里只是想要一个如何使用SparseArray的例子。 这是一个补充答案。

创build一个SparseArray

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

SparseArray将整数映射到某个Object ,因此可以用上面的示例中的Stringreplace其他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的键丢失。

迭代项目

您可以使用keyAtvalueAt某个索引来循环访问集合,因为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 

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

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

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

如果您使用HashMap而不是SparseArrays编写代码,则您的代码将与Map的其他实现一起工作,您将能够使用为Mapsdevise的所有Java API

我想大多数情况下,我们只使用HashMap来search与一个关键字相关的值,而SparseArray真的很擅长这个。

如果你使用HashMap而不是SparseArrays编写代码,你的代码将在非android项目中工作。

SparseArray的源代码相当简单,易于理解,因此只需付出很less的努力就可以将其移植到其他平台(通过简单的复制和粘贴)。

映射覆盖equals()和hashCode(),而SparseArray则不

我能说的是,(对于大多数开发者)谁在乎?

SparseArray另一个重要方面是它只使用一个数组来存储所有元素,而HashMap使用Entry ,所以SparseArrayHashMap花费less得多的内存,看到这个

我的基准testing表明,稀疏与哈希相同的速度添加和5! 使用get(int)进行search时速度更快。 但是,在桌面处理器上速度可能不同。

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

SparseArrays有他们的位置。 鉴于他们使用二进制searchalgorithm来查找数组中的值,你必须考虑你在做什么。 二进制search是O(log n),而散列查找是O(1)。 这并不一定意味着二进制search对于给定的一组数据是较慢的。 但是,随着条目数量的增长,散列表的能力将会被接pipe。 因此,条目数量less的评论可能相当于可能比使用HashMap更好。

一个HashMap只有散列一样好,也可以受到负载因素的影响(我认为在以后的版本,他们忽略了负载因素,所以它可以更好地优化)。 他们还添加了一个二级散列,以确保散列很好。 同样,SparseArray对于相对较less的条目(<100)也适用。

我会build议,如果你需要一个哈希表,并希望更好的内存使用原始整数(没有自动装箱)等,尝试特洛伊。 ( http://trove.starlight-systems.com – LGPL许可证)。 (与图书馆没有联系,就像他们的图书馆一样)

通过简化的多层次build筑,我们甚至不需要重新包装你需要的东西。 (trove有很多类)