转载自

No1：

Android官方推荐:当使用HashMap(K, V),如果K为整数类型时,使用SparseArray的效率更高.

No2：

HashMap是使用数组+链表的数据结构存储键值对,而SparseArray只是用了两个数组进行存储.

No3：

ContainerHelpers类提供了二分查找算法,从而降低了时间复杂度. 

// This is Arrays.binarySearch(), but doesn't do any argument validation.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;        } else {            return mid;  // value found        }    }    return ~lo;  // value not present}

No4：

put函数的步骤:

1）通过二分查找算法,计算key的索引值.

2）如果索引值大于0,说明有key对应的value存在,直接替换value即可.

3）如果索引值小于0,对索引值取反,获取key应该插入的坐标i.

4）判断是否需要扩容:1.需要扩容,则先扩容; 2.不需要扩容,则利用System.arraycopy移动相应的元素,进行(key,value)键值对插入

最终用到了这个函数

System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);

No5：

delete操作只是根据二分算法查找出key对应的下标,然后将object[] value中的对应下标值设置为DELETED.

No6：

delete()函数中将被删除的key对应的value设置为DELETED,并设置gc标志mGarbage为ture,SparseArray是在put函数的时候执行了gc:

gc函数的原理:遍历一遍数组,将非DELETED资源全部移动到数组前面.

private void gc() {    // Log.e("SparseArray", "gc start with " + mSize);    int n = mSize;    int o = 0;    int[] keys = mKeys;    Object[] values = mValues;    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++;        }    }    mGarbage = false;    mSize = o;    // Log.e("SparseArray", "gc end with " + mSize);}

No7：

SparseArray vs HashMap:

1）首先,这是两种完全不同的数据结构.SparseArray是两个数组:int[]和Object[], HashMap是数组+链表.

2）查找效率上: 首先,SparseArray不需要对key进行hash运算,并且通过二分查找保证查询效率为O(lgn).而HashMap在未冲突的情况下是O(1),冲突的情况下是O(n).