在做android开发很多年的时间里面，很多人都知道要使用 SpareArray，但是并不知道为什么。今天就来聊一聊SpareArray的实现源码，讲解下当前SpareArray的实现原理。
一、首先看下SpareArray的构造函数：
public SparseArray() { this(10); }
public SparseArray(int initialCapacity) { if (initialCapacity == 0) { mKeys = ContainerHelpers.EMPTY_INTS; mValues = ContainerHelpers.EMPTY_OBJECTS; } else { initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); mKeys = new int[initialCapacity]; mValues = new Object[initialCapacity]; } mSize = 0;
}
默认是分配一个数组长度为10，分别分配一个保存int类型的key，一个保存Object类型的值。
二、增加相应的数据 它有两个方法可以添加键值对： public void put( int key, E value) public void append( int key, E value)public void put(int key, E value) { 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); } if (mSize >= mKeys.length) { int n = ArrayUtils.idealIntArraySize(mSize + 1); int[] nkeys = new int[n]; Object[] nvalues = new Object[n]; // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); System.arraycopy(mValues, 0, nvalues, 0, mValues.length); mKeys = nkeys; mValues = nvalues; } if (mSize - i != 0) { // Log.e("SparseArray", "move " + (mSize - i)); System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); System.arraycopy(mValues, i, mValues, i + 1, mSize - i); } mKeys[i] = key; mValues[i] = value; mSize++; }
}
在上面添加数据的代码中发现，里面使用了一个非常重要的方法，就是二分查找法，来查找当前key的位置，然后，在适当的位置把当前值插入进去，因此，SparseArray添加的数组的内容一定是有序的。并且，它存储的数值都是按键值从小到大的顺序排列好的。其实append方法的实现方式和put的实现方式类似，这里不再详细讲解。
三、查 它有两个方法可以取值： public E get(int key) public E get(int key, E valueIfKeyNotFound) 最后一个从传参的变量名就能看出，传入的是找不到的时候返回的值 查看第几个位置的键： public int keyAt( int index) 查看第几个位置的值： public E valueAt( int index) 查看键所在位置，由于采用二分法查找键的位置，所以 没有的话返回小于0的数值，而不是返回-1 ，这点要注意，返回的负数其实是表示它在哪个位置就找不到了，如果你存了5个，查找的键大于5个值的话，返回就是-6： public int indexOfKey( int key) 查看值所在位置，没有的话返回-1： public int indexOfValue(E value) 四、删 它有两个方法： public void delete(int key) public void remove(int key) 但其实，delete和remove的效果是一样的，remove方法中调用了delete方法，remove源码： public void remove( int key) { delete(key); }还有一个clear方法，就是全部清除当前的所有数据。
通过上面的简单分析，基本可以知道，SparseArray使用的是纯数组的方式来实现的，不管是key，还是value都是一个数组。
而HashMap使用的是散列表（数组+链表）的方式实现的，查询数据的计算方式也比数组要复杂。关于HashMap的实现原理，将在下一个章节中讲解。另外，SparseArray实现了Cloneable接口，还可以调用clone方法。
对比当前的性能，总结如下：
1.SpareseArray 也是通过键值对存储数据，只是key为整形int , 类似于key = Interger 的HashMap，但是SpareseArray 的key 为 int 非 Interger ，更省空间。 2. SpareArray 意为稀松数组，其结构类似于数组结构，依次排开；HashMap是散列列表，根据hash值来存储；因此SpareArray 会比 HashMap节省很多空间。 3.从查找速度 和 插入效率来看，如果是正序插入( 0 ->size插入)，SpareArray 的插入效率会高于 HashMap。 4.如果是逆序插入(size -> 0)的顺序插入，则SpareArray 的插入效率表现是最差的，会低于HashMap。 5. SpareArray 在逆序插入效率很低，是因为 每次插入 SpareArray 都会采用二分查找来定位。 6. 从查找速度来来考虑，HashMap的查找速度 会 高于 SparseArray。 于是， 通过以上分析，SpareArray 相对于 HashMap的最大优势在内存空间。 因此谷歌推荐使用 SpareArray 代替 HashMap 。