SparseArray源码解析

构造

public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
       "key和value两个数组存储"
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}

put

public void put(int key, E value) {
        "二分法查找key所在的位置，如果没找到会是个负数，取反则是要插入的位置"
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            "如果找到了则把value替换"
            mValues[i] = value;
        } else {
           "取反算出要插入的位置"
            i = ~i;
            "如果要插入的位置没有值（被删除），就直接赋值,"
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            "如果有被删除过就执行gc操作"
            if (mGarbage && mSize >= mKeys.length) {
                gc();

               "再次算出要插入的位置"
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            "在第i个位置里插入数据"
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

GrowingArrayUtils.insert

public static int[] insert(int[] array, int currentSize, int index, int element) {
    assert currentSize <= array.length;

    "如果刚好数组长度能容纳新加的item就把数组"
    "的index后面的向后挪一个位置如[1,2,3,null]->[1,null,2,3]"
    if (currentSize + 1 <= array.length) {
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        ">[1,newvalue,2,3]"
        array[index] = element;
        return array;
    }

    "如果长度不够就扩容"
    int[] newArray = new int[growSize(currentSize)];
    "先copy前部分"
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    "再copy后部分"
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

growsize

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

delete

说到gc，要先看删除

  public void delete(int key) {
        "二分法找到要删除的位置"
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
        "可见删除不会移动数组，只是标记被删除把mGarbage改为true"
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }

gc

 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++;
            }
             "如果是删除了则o不会+1,下次循环的时候o<i"
             "然后会把values[o]=values[i]也就是整体往前挪"
        }

        mGarbage = false;
        mSize = o;

        // Log.e("SparseArray", "gc end with " + mSize);
    }

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];
    }
}