SparseArray到底哪点比HashMap好详解编程语言

SparseArray是android里为<Interger,Object>这样的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存储的<key,value>键值对个数为0. 
    mSize = 0; 
}

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

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

ContainerHelpers

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

<span style="font-size:12px;">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 <= 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 
    } 
}

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<mSize,则i之后的元素需要依次向后移动一位. 
        if (mSize - i != 0) { 
            System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 
            System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 
        } 
        // 设置值,存储数量+1 
        mKeys[i] = key; 
        mValues[i] = value; 
        mSize++; 
    } 
}

put函数的逻辑：

1. 通过二分查找算法,计算key的索引值.
2. 如果索引值大于0,说明有key对应的value存在,直接替换value即可.
3. 如果索引值小于0,对索引值取反,获取key应该插入的坐标i.
4. 判断是否需要扩容:1.需要扩容,则先扩容; 2.不需要扩容,则利用System.arraycopy移动相应的元素,进行(key,value)键值对插入.

get()函数

/** 
 * 根据指定的key获取value. 
 */ 
public E get(int key) { 
    return get(key, null); 
} 
/** 
 * 利用二分查找算法根据key获取指定的value. 
 */ 
public E get(int key, E valueIfKeyNotFound) { 
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 
    if (i < 0 || mValues[i] == DELETED) { 
        return valueIfKeyNotFound; 
    } else { 
        return (E) mValues[i]; 
    } 
}

/** 
 * 根据key删除指定的value. 
 */ 
public void delete(int key) { 
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 
 
    if (i >= 0) { 
        if (mValues[i] != DELETED) { 
            // 标记i的值为private static final Object DELETED = new Object(); 
            mValues[i] = DELETED; 
            // 设置gc标记为true. 
            mGarbage = true; 
        } 
    } 
} 
/** 
 * Alias for [email protected] #delete(int)}. 
 */ 
public void remove(int key) { 
    delete(key); 
}

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