SpareArray源码分析

---

在Android平台，SpareArray可以替代HashMap实现数据存储，它和HashMap数组+链表的数据结构不同，采用两个数组的数据存储方案。下面是源码中定义的两个数组，分别存储key和value。其中，key必须为int类型。

private int[] mKeys;
private Object[] mValues;

本文主要分析一下SpareArray类数据存取的相关源码，构造方法。

public SparseArray() {
    this(10);
}

无参构造方法，默认容量10。

public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}

根据容量值，初始化两个数组，它们长度是一样。

---

数据存取

put方法，存储数据。

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //key已存在mKey中，直接更新mValue数组。
    if (i >= 0) {
        mValues[i] = value;
    } else {//key不存在mKey中
        i = ~i;//将最后查找的索引位置恢复，此位置对应新key的值正好符合数组排序。
        //key应放置的位置在size数量内，正好对应value处是DELETED。
        //一般情况下根据新key是根据排序插入的，此位置key已经有值了，value也会被占坑。
        //如果value被delete，就可以将key替换这个旧key，同时value也设置新的。
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        //下面的情况说明
        //key最大，应放在size处，0到size-1的值都比它小。
        //或者key值可以放到位置i，位置i处有其他value有用，非DELETED。
        if (mGarbage && mSize >= mKeys.length) {
            gc();
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
         //key插入到合适位置i。mKeys后面的元素需要后移。自增mSize。
         //当遇到数组元素不够时，自动扩容
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

ContainerHelpers工具类，根据key值，在mKeys数组查找索引，如果查到的值>0，同步更新mValues数组相同索引处的value值。
如果未查到，情况比较复杂，根据源码，逻辑如下。
首先，转换(取反)返回值，从binarySearch源码知道(后面有源码)，它采用二分查找算法，当未找到时，返回的值是最后查找的索引位置取反(<0)。转换后，该值就是key在mKeys数组按照从小到大顺序应该插入的位置。
然后，查看索引值是否在mSize范围内，且这个位置的value已经被删除，(DELETED状态)。这时，可以将value值放到mValues数组的此索引位置。不满足条件，说明这个位置已经有(有用)的key值，先不能替换掉。
当key值最大，应该插入索引在mSize，或者mValues数组索引处的值非delete，只能强行插入。
最后，GrowingArrayUtils方法，插入索引位置，它后面的数组其他元素后移，在容量不足时还会自动扩容，自增mSize代表数组中元素又增加了一个。
其实，前面还有一层，有垃圾标志且mSize已经超过数组大小，这时，有一个gc的过程，目的是遍历将带垃圾Object的value清理掉，重新对应并放置数组的key与value，试图减小mSize，重新查找该key放置的位置。

标志mGarbage，代表数组中存在垃圾元素，removeAt方法，从mValues数组删除某项key的value时，将该value位置值指向DELETED，它是一个内部Object对象。

private static final Object DELETED = new Object();

public void removeAt(int index) {
    if (mValues[index] != DELETED) {
        mValues[index] = DELETED;
        mGarbage = true;
    }
}

get方法，查找数据。

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，查找在mKeys中的位置索引，value是该索引在mValues数组中的值。若查找的索引小于0，说明mKeys中不存在key，或mValues数组的值是DELETED，返回默认valueIfKeyNotFound。key和value在数组中有相同的索引。

---

二分查找算法

ContainerHelpers的binarySearch方法，采用二分查找算法，从array中查找value值，返回该值索引。

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值在array的索引，
        }
    }
    return ~lo;  //未找到value，不可能返回一个正确的索引，因此返回负值
}

从0到size-1索引范围查找。二分查找法。

二分查找法，数组升序排列。

---

总结

SpareArray避免key的自动装箱，数据量不大时可以代替HashMap，更省内存。

---