public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;
    private int[] mKeys;
    private Object[] mValues;
    private int mSize;

public void delete(int key) {
        //查找对应key在数组中的下标，如果存在，返回下标，不存在，返回下标的取反；
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //key存在于mKeys数组中，将元素删除，用DELETED替换原value，起标记作用；
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }
 
    /**
     * @hide
     * Removes the mapping from the specified key, if there was any, returning the old value.
     */
    public E removeReturnOld(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                final E old = (E) mValues[i];
                mValues[i] = DELETED;
                mGarbage = true;
                return old;
            }
        }
        return null;
    }
 
    /**
     * Alias for {@link #delete(int)}.
     */
    public void remove(int key) {
        delete(key);
    }

static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;
        while(lo <= hi) {
            int mid = lo + hi >>> 1;
            int midVal = array[mid];
            if (midVal < value) {
                lo = mid + 1;
            } else {
                if (midVal <= value) {
                    return mid;
                }
                hi = mid - 1;
            }
        }
        return ~lo;
    }

public void put(int key, E value) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //原来已经有key，可能是remove后，value存放着DELETED，也可能是存放旧值，那么就替换
        if (i >= 0) {
            mValues[i] = value;
        } else {
            //没有找到，对i取反，得到i= lo（ContainerHelpers.binarySearch）
            i = ~i;
            //如果i小于数组长度，且mValues==DELETED(i对应的Key被延迟删除了)
            if (i < mSize && mValues[i] == DELETED) {
                //直接取代，实现真实删除原键值对
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            //数组中可能存在延迟删除元素且当前数组长度满，无法添加
            if (mGarbage && mSize >= mKeys.length) {
                //真实删除，将所有延迟删除的元素从数组中清除；
                gc();
                //清除后重新确定当前key在数组中的目标位置；
                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //不存在垃圾或者当前数组仍然可以继续添加元素，不需要扩容，则将i之后的元素全部后移，数组中仍然存在被DELETED的垃圾key；
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            //新元素添加成功，潜在可用元素数量+1
            mSize++;
        }
    }

public static int[] insert(int[] array, int currentSize, int index, int element) {
        assert currentSize <= array.length;
 
        if (currentSize + 1 <= array.length) {
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }
 
        int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }

private void gc() {
        // Log.e("SparseArray", "gc start with " + mSize);
        //n代表gc前数组的长度；
        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;
 
        for (int i = 0; i < n; i++) {
            Object val = values[i];
            //遍历元素，如果value不为DELETED，则用前数据放在o上，o的序号表示当前的有效元素下标。
            //每遇到一次DELETED，则i-o的大小+1；
            if (val != DELETED) {
                //之后遇到非DELETED数据，则将后续元素的key和value往前挪
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }
 
                o++;
            }
        }
        //此时无垃圾数据，o的序号表示mSize的大小
        mGarbage = false;
        mSize = o;
 
        // Log.e("SparseArray", "gc end with " + mSize);
    }

public E get(int key) {
        return get(key, null);
    }
 
    /**
     * Gets the Object mapped from the specified key, or the specified Object
     * if no such mapping has been made.
     */
    @SuppressWarnings("unchecked")
    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];
        }
    }