SparseArray原理和源码解析详解编程语言

SparseArray 稀疏数组，Android的特有的数据结构。跟HashMap一样都是存储<Key，Value>的实体。但是不一样的是HashMap利用Hash定位实体位置，而SparseArray利用二分查找法定位位置。

数据结构

SparseArray的数据结构很简单，有mKeys、mValues两个数组，key和value的位置是一一对应的，而key是按照从小到大的

SparseArray使用起来跟HashMap很相似，get()、put()、remove()、clear()

源码分析

重要的变量：

private static final Object DELETED = new Object(); 
// 当某个key被删除时，对应的value会被置为DELETED 
 
private boolean mGarbage = false; 
// 表面看是主动触发gc的标志，实际上是触发重新整理mKeys、mValues的标志 
 
private int[] mKeys; 
private Object[] mValues; 
private int mSize; 
// <key, value>的实际数量 

SparseArray的默认初始化容量是10。

public E get(int key) {
    
    return get(key, null); 
} 
 
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]; 
    } 
} 

ContainerHelpers是一个工具类，binarySearch()表示二分查找

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 
} 

这就是个普通的二分查找算法，比较特别的是：如果查找失败，lo会等于查找的元素的插入位置，比如说在数组[1, 3, 4]中如果查找2，对应结果lo = 1，如果查找5，对应结果lo = 3；

binarySearch返回结果 对lo取反，lo为正数，取反会得到负数，这样做有两个好处：

1. 返回结果是正数，表示查找得到，为对应的位置
2. 返回结果是负数，表示查找不到，但是对结果取反，得到元素待插入的位置，对put()操作可以避免再次查找

public void put(int key, E value) {
    
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);  
    if (i >= 0) {
    // 查找得到，为对应的位置 
        mValues[i] = value; 
    } else {
    // 查找不到，~i为元素待插入的位置 
        i = ~i; 
 
        if (i < mSize && mValues[i] == DELETED) {
     
        	// 如果刚好待插入的位置是被Delete掉的，直接赋值 
            mKeys[i] = key; 
            mValues[i] = value; 
            return; 
        } 
        // mGarbage 表示需要重新整理 
        if (mGarbage && mSize >= mKeys.length) {
    
           gc(); // 重新整理 
 
           // Search again because indices may have changed. 
           // 重新获取一次待插入的位置 
           i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); 
        } 
        // 插入到目标位置key、value 
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); 
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); 
        mSize++; 
    } 
} 

mGarbage 表示需要进行gc()动作，那mGarbage是在哪里设置的呢？答案是在remove移除键值对的时候，就会设置mGarbage

    public void delete(int key) {
    
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 
 
        if (i >= 0) {
    
            if (mValues[i] != DELETED) {
    
                mValues[i] = DELETED; 
                mGarbage = true; // 设置需要gc 
            } 
        } 
    } 

最后看如何gc的

private void gc() {
    
    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; 
} 

gc()其实不是真正意义上的java的gc，指的是从头遍历一遍，让后面的节点往前移动，顶替掉原有的DELETED的节点。

对了，在插入的时候GrowingArrayUtils.insert()方法，可能因为空间不足需要扩容数组，再复制原数组到新的数组，在内部会调用growSize获取新的容量

// GrowingArrayUtils 
public static int growSize(int currentSize) {
    
    return currentSize <= 4 ? 8 : currentSize * 2; 
 } 

一般情况下，新容量为当前容量的两倍

总结

SparseArray 内部利用两个数组存储key、value，key和value位置一一对应，key的按照排序保存在数组中，而插入获取等操作都是利用二分查找算法。