SparseArray到底哪点比HashMap好

SparseArray是android里为这样的Hashmap而专门写的class,目的是提高效率，其核心是折半查找函数（binarySearch）。

HashMap底层是一个Hash表，是数组和链表的集合实现，有需要的可以去看看我关于Hashmap的分析。hashmap源码分析

所以Android开发中官方推荐：当使用HashMap(K, V),如果K为整数类型时,使用SparseArray的效率更高。

那我们看源码来分析下，

构造函数：

/**
 * 存储索引集合.
 */
private int[] mKeys;
/**
 * 存储对象集合.
 */
private Object[] mValues;
/**
 * 存储的键值对总数.
 */
private int mSize;
/**
 * 采用默认的构造函数,则初始容量为10.
 */
public SparseArray() {
    this(10);
}
/**
 * 使用指定的初始容量构造SparseArray.
 *
 * @param initialCapacity 初始容量
 */
public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        // Effective Java中第43条:返回零长度的数组或者集合,而不是:null
        mKeys = ContainerHelpers.EMPTY_INTS;
        mValues = ContainerHelpers.EMPTY_OBJECTS;
    } else {
        // 构造initialCapacity大小的int数组和object数组
        mKeys = new int[initialCapacity];
        mValues = new Object[initialCapacity];
    }
    // 设置SparseArray存储的键值对个数为0.
    mSize = 0;
}

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

我们知道链表的时间复杂度是很高的，这估计也是造成hashmap时间复杂度高的一个原因。

ContainerHelpers ContainerHelpers类提供了二分查找算法，这也一定程度上提高了查找的效率

class 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 >> 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
    }
}

put()函数

/**
 * 在SparseArray中存储键值对.
 */
public void put(int key, E value) {
    // 通过二分查找算法计算索引
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        // key已经存在对应的value,则直接替换value.
        mValues[i] = value;
    } else {
        i = ~i;
        if (i < mSize && mValues[i] == DELETED) {
            // 特殊的case,直接存储key-value即可
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        if (mGarbage && mSize >= mKeys.length) {
            // 如果有元素被删除,并且目前容量不足,先进行一次gc
            gc();
            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        // 扩容
        if (mSize >= mKeys.length) {
            // 获取扩容的数组大小
            int n = mSize + 1;
            int[] nkeys = new int[n];
            Object[] nvalues = new Object[n];
            // 数组拷贝最好使用System.arraycopy,而不是自己重撸一遍
            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
            mKeys = nkeys;
            mValues = nvalues;
        }
        // i为插入位置,如果i= 0) {
        if (mValues[i] != DELETED) {
            // 标记i的值为private static final Object DELETED = new Object();
            mValues[i] = DELETED;
            // 设置gc标记为true.
            mGarbage = true;
        }
    }
}
/**
 * Alias for {@link #delete(int)}.
 */
public void remove(int key) {
    delete(key);
}

gc()函数

if (mGarbage && mSize >= mKeys.length) {
    // 如果有元素被删除,并且目前容量不足,先进行一次gc
    gc();
    // Search again because indices may have changed.
    i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}

通过上面的源码分析，我们不难得出：