常用类（63）
SparseArray
& & & & Java的HashMap使用的是数组+链表的实现结构，无论有没有是否添加数据，都会分配一个数组(该数组用于存放链表的头元素)。这在某种程度上浪费了一部分的内存空间，而且HashMap的key,value必须是Object，所以对于基本数据类型来说，在存储到HashMap时必须经过一个自动装箱的过程，这又浪费了一部分性能。这算是HashMap的缺点。
& & & & 对于SparseArray来说，它避免了HashMap的自动装拆箱的过程：因为它的key值是int类型的。它内部采用双数组实现：一个int[]类型数组，用于存储key值；一个Object[]数组，用于存储value。这里就有一个与ArrayList类似的问题：数组扩容——当初始容量不够，需要扩展一下key数组，value数组。
& & & & 因此，在SparseArray的使用时，应该考虑初始容量的大小。大了，浪费内存；小了，数组扩容频繁，导致性能降低。
public SparseArray() {
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
mSize = 0;
& & & & 很简单，初始化两个数组，并将mSize设置为0。mSize指的是当前数组中具体存有的元素的个数，此处不能用数组的length——它只数组能存储的元素的个数，并不代表着数组中已存储了多少个元素。
public E get(int key) {
return get(key, null);
@SuppressWarnings(&unchecked&)
public E get(int key, E valueIfKeyNotFound) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i & 0 || mValues[i] == DELETED) {
return valueIfKeyNotF
return (E) mValues[i];
& & & & ContainerHelpers.binarySearch()使用的是二分查找。为什么可以直接用二分查找，是因为mKeys数组中是已经排好序的，在put方法时可以看出。代码如下：
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo &= hi) {
final int mid = (lo + hi) &&& 1;
final int midVal = array[mid];
if (midVal & value) {
lo = mid + 1;
} else if (midVal & value) {
hi = mid - 1;
// value found
// value not present
& & & & 这个方法有一点要注意，如果没有找到指定value时的返回值：~lo(取反)，而整个代码中可以看出：lo是不可能小于0的，所以~lo是小于0的。
& & & & 因此，binarySearch()的返回值有两个作用：大于0，则代表所查找value在array中的下标；小于0，则代表array中没有该value，并且此时的返回值取反后为value应该插入到array中的下标。一个返回值两个作用：太帅了！！
& & & & 知道这点后，就可以看出get的逻辑，其中==DELETED的逻辑在remove时说。其余略。
& & & & 但，这里的无参get写的不太好，因为SparseArray本身的value可以是null。如果当前没有该key，并且调用了无参数的get方法，返回的也是null，容易造成模糊。
* Removes the mapping from the specified key, if there was any.
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i &= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage =
* Removes the mapping from the specified key, if there was any, returning the old value.
public E removeReturnOld(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i &= 0) {
if (mValues[i] != DELETED) {
final E old = (E) mValues[i];
mValues[i] = DELETED;
mGarbage =
* Alias for {@link #delete(int)}.
public void remove(int key) {
delete(key);
}& & & & 逻辑很简单，并且remove与delete可以认为是同一个方法。removeReturnOld时，将旧有的值给返回了。
& & & & 在remove时，并不是将当前key对应的value设置为null，而是设置成DELETED，它的定义如下：
private static final Object DELETED = new Object();
& & & & 这样做的目的有两个：其一不用remove/delete时直接移动数组，因为内部采用的是双数组结构，对于数组来说查找方便，但插入删除很耗性能，所以并没有在每一次删除时都移动数组。这里使用DELETED相当于占位符，不用移数组，而且也知道该位置已经被remove/delete掉了，get时就能知道返回何值。其二，并没有直接设置为null，这样保证了SparseArray中可以存储null值。
& & & & 这是一个private方法，但这个方法很有意思，而且对gc()方法的调用时机也很有意思。如下：
private void gc() {
// Log.e(&SparseArray&, &gc start with & + mSize);
int n = mS
int o = 0;
int[] keys = mK
Object[] values = mV
for (int i = 0; i & i++) {
Object val = values[i];
if (val != DELETED) {
if (i != o) {
keys[o] = keys[i];
values[o] =
values[i] =
mGarbage =
& & & & 该方法的功能很简单：移除掉那些被remove/delete过的key。为什么要这么做？为了节约内存。为什么不直接在remove/delete时删掉，原因见remove部分。
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i &= 0) {
mValues[i] =
if (i & mSize && mValues[i] == DELETED) {
mKeys[i] =
mValues[i] =
if (mGarbage && mSize &= mKeys.length) {
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
& & & & 先查找key的位置，如果当前key已经存在，直接覆盖对应的value。如果没有，但要插入的位置上的元素为DELETED，就直接用新key,value取代原有的。否则就直接使用insert进行插入。
& & & & 这中间有一个判断，当remove/delete(mGarbage只有在remove时才会被赋值为true)过，并且数组已经存储满了，那么就调用gc删除其中的deleted，然后再插入——这是为了在尽可能不影响性能的情况下节约内存。如果mGarbage为false，表示没有remove过，那么就不需要调用gc()。如果mSize&mKeys.length表明当前的数组并没有存满，现在不需要移动deleted。如果两个条件都满足，就表示当前数组中有脏数据，gc()之后就会空余出一部分空间，就不需要重新扩容了。
& & & & 在put时也涉及到数组的扩容，即思路与ArrayList中完全一样。代码如下：
public static &T& T[] More ...insert(T[] array, int currentSize, int index, T element) {
assert currentSize &= array.
//断言，当前的size肯定要小于数组的长度
if (currentSize + 1 &= array.length) {//数组容量足够，不需要扩容，只是将index后面的往后挪一位
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] =
@SuppressWarnings(&unchecked&)
//growSize代码为currentSize &= 4 ? 8 : currentSize * 2;
T[] newArray = ArrayUtils.newUnpaddedArray((Class&T&)array.getClass().getComponentType(),
growSize(currentSize));//生成一个新数组，容易为growSize。这里就是进行了扩容，逻辑完全与ArrayList相同
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] =
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newA
& & & & 后面还有一些方法，比较简单，捡其中两个说下：
& & & & clear()：清空value数组，将其中的value全部设置为null。
& & & & append()：类似于put，但比put的要求要多一个：使用append的前提时你知道你的key是比SparseArray中所有的key都大的。因为二分查找时要求Key时从小到大排列的。在满足这一点的前提下，使用append比put效率高。
& & & & 1，采用双数组结构可以模拟Map。扩展一下，采用多个数组，就可以模拟一对多的情况：一个数组值key，多个数组存value。当然，也可将多个value组建成珍上Object，直接使用SparseArray。
& & & & 2，善用函数返回值。一个返回值可以表达多种信息。
& & & & 3，将可能执行延误性能的操作尽量延迟到必须执行时才进行，因为有可能不执行。如上面的并不有在remove时直接移动数组，而是用DELETED做标识，到容量不够时才gc。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：52740次
积分：2117
积分：2117
排名：第14832名
原创：159篇
(2)(3)(3)(2)(5)(6)(11)(14)(8)(1)(5)(6)(2)(2)(11)(2)(1)(3)(2)(4)(10)(2)(4)(8)(5)(2)(2)(1)(4)(2)(4)(4)(14)(5)(2)Posts - 26,
Articles - 0,
Comments - 1
14:00 by 熠熠闪光, ... 阅读,
在Android开发时，我们使用的大部分都是Java的api，比如HashMap这个api，使用率非常高，但是对于Android这种对内存非常敏感的移动平台，很多时候使用一些java的api并不能达到更好的性能，相反反而更消耗内存，所以针对Android这种移动平台，也推出了更符合自己的api，比如SparseArray、ArrayMap用来代替HashMap在有些情况下能带来更好的性能提升。
介绍它们之前先来介绍一下HashMap的内部存储结构，就明白为什么推荐使用SparseArray和ArrayMap
HashMap内部是使用一个默认容量为16的数组来存储数据的，而数组中每一个元素却又是一个链表的头结点，所以，更准确的来说，HashMap内部存储结构是使用哈希表的拉链结构（数组+链表），如图：&这种存储数据的方法叫做拉链法&&且每一个结点都是Entry类型，那么Entry是什么呢？我们来看看HashMap中Entry的属性：
HashMapEntry&K, V&
从中我们得知Entry存储的内容有key、value、hash值、和next下一个Entry，那么，这些Entry数据是按什么规则进行存储的呢？就是通过计算元素key的hash值，然后对HashMap中数组长度取余得到该元素存储的位置，计算公式为hash(key)%len，比如：假设hash(14)=14,hash(30)=30,hash(46)=46，我们分别对len取余，得到&hash(14)%16=14，hash(30)%16=14，hash(46)%16=14，所以key为14、30、46的这三个元素存储在数组下标为14的位置，如：&&从中可以看出，如果有多个元素key的hash值相同的话，后一个元素并不会覆盖上一个元素，而是采取链表的方式，把之后加进来的元素加入链表末尾，从而解决了hash冲突的问题，由此我们知道HashMap中处理hash冲突的方法是链地址法，在此补充一个知识点，处理hash冲突的方法有以下几种：
开放地址法
建立公共溢出区
讲到这里，重点来了，我们知道HashMap中默认的存储大小就是一个容量为16的数组，所以当我们创建出一个HashMap对象时，即使里面没有任何元素，也要分别一块内存空间给它，而且，我们再不断的向HashMap里put数据时，当达到一定的容量限制时（这个容量满足这样的一个关系时候将会扩容：HashMap中的数据量&容量*加载因子，而HashMap中默认的加载因子是0.75），HashMap的空间将会扩大，而且扩大后新的空间一定是原来的2倍，我们可以看put()方法中有这样的一行代码：
int newCapacity = oldCapacity * 2;
所以，重点就是这个，只要一满足扩容条件，HashMap的空间将会以2倍的规律进行增大。假如我们有几十万、几百万条数据，那么HashMap要存储完这些数据将要不断的扩容，而且在此过程中也需要不断的做hash运算，这将对我们的内存空间造成很大消耗和浪费，而且HashMap获取数据是通过遍历Entry[]数组来得到对应的元素，在数据量很大时候会比较慢，所以在Android中，HashMap是比较费内存的，我们在一些情况下可以使用SparseArray和ArrayMap来代替HashMap。
SparseArray
SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型），它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value，为了优化性能，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间，我们从源码中可以看到key和value分别是用数组表示：
private int[] mK
private Object[] mV
我们可以看到，SparseArray只能存储key为int类型的数据，同时，SparseArray在存储和读取数据时候，使用的是二分查找法，我们可以看看：
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
public E get(int key, E valueIfKeyNotFound) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
也就是在put添加数据的时候，会使用二分查找法和之前的key比较当前我们添加的元素的key的大小，然后按照从小到大的顺序排列好，所以，SparseArray存储的元素都是按元素的key值从小到大排列好的。&而在获取数据的时候，也是使用二分查找法判断元素的位置，所以，在获取数据的时候非常快，比HashMap快的多，因为HashMap获取数据是通过遍历Entry[]数组来得到对应的元素。
public void put(int key, E value)
public void remove(int key)
public void delete(int key)
其实remove内部还是通过调用delete来删除数据的
public E get(int key)
public E get(int key, E valueIfKeyNotFound)
该方法可设置如果key不存在的情况下默认返回的value
在此之外，SparseArray还提供了两个特有方法，更方便数据的查询：&获取对应的key：
public int keyAt(int index)
获取对应的value：
public E valueAt(int index)
SparseArray应用场景：
虽说SparseArray性能比较好，但是由于其添加、查找、删除数据都需要先进行一次二分查找，所以在数据量大的情况下性能并不明显，将降低至少50%。
满足下面两个条件我们可以使用SparseArray代替HashMap：
数据量不大，最好在千级以内
key必须为int类型，这中情况下的HashMap可以用SparseArray代替：
HashMap&Integer, Object& map = new HashMap&&();
用SparseArray代替:
SparseArray&Object& array = new SparseArray&&();
这个api的资料在网上可以说几乎没有，然并卵，只能看文档了&ArrayMap是一个&key,value&映射的数据结构，它设计上更多的是考虑内存的优化，内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值，它和SparseArray一样，也会对key使用二分法进行从小到大排序，在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作，所以，应用场景和SparseArray的一样，如果在数据量比较大的情况下，那么它的性能将退化至少50%。
public V put(K key, V value)
public V get(Object key)
public V remove(Object key)
它和SparseArray一样同样也有两个更方便的获取数据方法：
public K keyAt(int index)
public V valueAt(int index)
ArrayMap应用场景
数据量不大，最好在千级以内
数据结构类型为Map类型
【注】：如果我们要兼容aip19以下版本的话，那么导入的包需要为v4包
import android.support.v4.util.ArrayMap
SparseArray和ArrayMap都差不多，使用哪个呢？&假设数据量都在千级以内的情况下：
1、如果key的类型已经确定为int类型，那么使用SparseArray，因为它避免了自动装箱的过程，如果key为long类型，它还提供了一个LongSparseArray来确保key为long类型时的使用
2、如果key类型为其它的类型，则使用ArrayMapSparseArrayE详解_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
SparseArrayE详解
上传于||文档简介
&&Android编程
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢