SparseArray简析

HashMap在Android开发中是一种常用的数据结构类型，但是占用内存方面相对会比较大，而且复杂的机制导致运行效率也不高。所以Android系统提供了SparseArray以及ArrayMap来对其进行替代。这也是Android性能优化的一种手段。

SparseArray

SparseArray可以对key为Integer类型的HashMap进行替代。还有

  • LongSparseArray对key为Long型的HashMap
  • SparseIntArray对key为Integer类型，value为Integer类型
  • SparseLongArray对key为Integer类型，value为Long类型
  • SparseBooleanArray对key为Integer类型，value为Boolean类型

等这些类型。内部实现都是相似的，只是可支持的类型不同。

SparseArray允许value为null，并且是线程不安全的。

SparseArray使用场景

  • 数据量不大
  • 空间比时间重要
  • 需要使用到Map型结构，且key为int类型

SparseArray重要参数分析

SparseArray.java
1
2
3
4
5
6
7
8
9
10
//需要删除的标记    
private static final Object DELETED = new Object();
//设置回收标记 实质执行了 删除后的index置为null，协助回收
private boolean mGarbage = false;
//保存每个Item的key
   private int[] mKeys;
//保存每个Item的value，容量和mKeys一致
   private Object[] mValues;
   //保存的数据容量
   private int mSize;

SparseArray源码解析

初始化

1
2
3
4
//无初始值
SparseArray<String> stringSparseArray = new SparseArray<>();
//设置初始值
SparseArray<String> stringSparseArray = new SparseArray<>(5);

对应源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   //默认构造器 初始化容量为10
public SparseArray() {
       this(10);
   }

public SparseArray(int initialCapacity) {
       if (initialCapacity == 0) {
           mKeys = EmptyArray.INT;
           mValues = EmptyArray.OBJECT;
       } else {
           //初始化长度的数组
           mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
           mKeys = new int[mValues.length];
       }
       mSize = 0;
   }

存放的键值对分别放在两个数组mKeys、mValues，数据是一一对应的。

插入数据

1
stringSparseArray.put(1,"android");

对应源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public void put(int key, E value) {
        //利用二分查找，找到key应该插入的位置
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            //找到已存在的值  直接进行覆盖
            mValues[i] = value;
        } else {
            //返回负数  需要取反获取插入的位置
            i = ~i;
            //当前没有越界 且原先该位置的数据已被删除 可以进行复用
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            if (mGarbage && mSize >= mKeys.length) {
                //压缩空间
                gc();①

                // 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);
            //存储数据+1
            mSize++;
        }
    }

①gc()：垃圾回收，对数组进行压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private void gc() {
        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;
        //遍历values
        for (int i = 0; i < n; i++) {
            Object val = values[i];
            //对应值不为删除标记
            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    //防止内存泄露，使用过后置空
                    values[i] = null;
                }
                //重新统计数据量
                o++;
            }
        }
        //标识 GC结束
        mGarbage = false;
        mSize = o;
    }

gc()实质是内部一个for循环，将value不为DELETED的数据重新插入数组中，已实现对数组的压缩，同时重置GC标志。

②GrowingArrayUtils.insert(mKeys, mSize, i, key)：插入数据 可能需要扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int[] insert(int[] array, int currentSize, int index, int element) {
    assert currentSize <= array.length;
    //不需要扩容
    if (currentSize + 1 <= array.length) {
        //将插入位置后的数据向后移一位
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
    }
    //需要进行扩容操作
    int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}
//重新设置数组容量
public static int growSize(int currentSize) {
    return currentSize <= 4 ? 8 : currentSize * 2;
}

insert()内部执行了两段操作：

  • 不需要扩容：将需要插入位置的数据向后移一位，然后数据插入到对应位置。
  • 需要扩容：扩容数据为原容量的2倍(容量<=4时，扩容至8，其他情况下为2倍。)，然后将原数组对应位置前的数据以及之后的数据分别插入扩容后数组。

put()需要通过二分查找法找到可以插入的位置，如果当前位置的key相同，则直接覆盖原数据。如果key不相同但是value为DELETED，可以拿新的数据直接覆盖；如果不是，需要先判断mGarabge为true，就需要执行gc()压缩数组空间(有效的数据按照顺序重新排布)，然后再去插入新数据，过程中可能需要扩容。

获取数据

1
2
3
4
5
6
7
//获取key对应的数据
stringSparseArray.get(1)
stringSparseArray.get(1,"iOS")
//获取key对应的下标
stringSparseArray.indexOfKey(1)  
//根据下标获取key
stringSparseArray.keyAt(0)

对应源码

根据key获取value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public E get(int key) {
       return get(key, null);
   }

   @SuppressWarnings("unchecked")
   public E get(int key, E valueIfKeyNotFound) {
       //寻找key对应位置
       int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

       if (i < 0 || mValues[i] == DELETED) {
           return valueIfKeyNotFound;
       } else {
           return (E) mValues[i];
       }
   }
根据key获取index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int keyAt(int index) {
      //需要先判断是否GC
      if (mGarbage) {
          gc();
      }

      return mKeys[index];
  }

  public E valueAt(int index) {
      if (mGarbage) {
          gc();
      }

      return (E) mValues[index];
  }
根据index获取key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int indexOfKey(int key) {
    //查询下标时，也需要考虑是否先GC
       if (mGarbage) {
           gc();
       }
       //二分查找返回 对应的下标 ,可能是负数
       return ContainerHelpers.binarySearch(mKeys, mSize, key);
   }
   public int indexOfValue(E value) {
    //查询下标时，也需要考虑是否先GC
       if (mGarbage) {
           gc();
       }
       //不像key一样使用的二分查找。是直接线性遍历去比较，而且不像其他集合类使用equals比较，这里直接使用的 ==
       //如果有多个key 对应同一个value，则这里只会返回一个更靠前的index
       for (int i = 0; i < mSize; i++)
           if (mValues[i] == value)
               return i;

       return -1;
   }

删除数据

1
2
3
4
5
6
//删除对应key的数据
stringSparseArray.remove(1);
//删除对应index的数据
stringSparseArray.removeAt(0)；
//删除对应区间的数据
stringSparseArray.removeAtRange(0,1);

对应源码

根据key删除数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void remove(int key) {
        delete(key);
    }

public void delete(int key) {
    //二分查找到对应的index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //找到了对应位置
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                //打上已删除标记
                mValues[i] = DELETED;
                //标记需要执行 gc()
                mGarbage = true;
            }
        }
    }
根据index删除数据
1
2
3
4
5
6
public void removeAt(int index) {
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }
根据区间删除数据
1
2
3
4
5
6
public void removeAtRange(int index, int size) {
    final int end = Math.min(mSize, index + size);
    for (int i = index; i < end; i++) {
        removeAt(i);
    }
}

remove()相关方法并不是直接删除数据，而是使用DELETED占据被删除数据的位置，同时设置mGarabge=true，等待调用gc()进行数据压缩。

设置DELETED的目的：如果put()时也要用到该位置，就可以不用进行数据复制，而直接放入数据即可。

SparseArray拓展

  • SparseArray的key是按照顺序从小到大排列的
  • 由于压缩数组的原因，所以占用空间会比HashMap小，当数据量上来时，二分查找将会成为其性能瓶颈，所以适合数据量小的情况
  • key为int类型，省去Integer拆箱的性能消耗。
  • 由于SparseArray没有实现Serializable接口，所以不支持序列化即无法进行传递。
源码解析

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！