【Java源码分析】Android-SparseArray源码分析

男娘i 2022-07-20 12:05 200阅读 0赞

类的定义

public class SparseArray<E> implements Cloneable {}

将int映射为对象，比HashMap更节省内存。一方面是避免了对key的自动装箱；另外一个方面是它的键值对不依赖于外部的实体对象来保存键值映射而HashMap需要额外的存储空间来保存键值对之间的映射关系。

1.  该容器将映射存储在一个数组数据结构中，使用二分查找找到对应的key.这种设计不太适合于存储大量的数据。由于查找的时候需要进行二分查找，添加和删除的时候需要插入和删除数组中的实体，因此时间效率上并不高效。在只有几百个键值对的情况下，性能损失低于Hashmap的50%
2.  为了弥补性能上的损失，在删除元素的时候容器实现了一个优化。仅仅将该实体标记为已删除，而不是在数组中执行实际的删除操作。这样被标记为删除的实体，可以被相同的key对应的实体复用。或者不复用而是在一段时间之后统一进行内存的回收。这个思路有点像内存回收策略中的标记清除
3.  可以使用keyAt()和valueAt()对SparseArray进行迭代
4.  由于按key查找的时候使用的是二分查找，那么key是有序的，所以使用keyAt(i)的时候，对应的从大到小的i得到的key也是从大到小的

主要成员变量

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

构造函数

public SparseArray() {
        this(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;
    }

构造函数中如果指定initialCapacity为0，那么不会做实际的内存分配操作

get方法

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

查找指定的key对应的值，如果无法查找到该key对应的键值对，那么返回null或者指定的值

删除

// 1
    public void delete(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }
    
    // 2
    public void remove(int key) {
        delete(key);
    }
    
    // 3
    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;
    }
    
    // 4
    public void removeAt(int index) {
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }
    
    // 5
    public void removeAtRange(int index, int size) {
        final int end = Math.min(mSize, index + size);
        for (int i = index; i < end; i++) {
            removeAt(i);
        }
    }

删除指定的key对应的键值对。第二个方法和第一个方法是一样的，只是名字不一样。低三个方法会返回该key对应的值。第四个是根据下标删除，前面的删除方法中都有一个二分查找对应下标的过程

添加操作

public void put(int key, E value) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    
        if (i >= 0) {
            mValues[i] = value;
        } else {
            i = ~i;
    
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
    
            if (mGarbage && mSize >= mKeys.length) {
                gc();
    
                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
    
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

添加新的键值对，如果对应的key已经存在，那么替换该key对应的旧值。注意在查找失败的时候，也就是下标小于0的时候，进行了按位取反的一个操作`i = ~i;`不是很清楚这里为什么不是直接取反而是按位取反。另外在添加之后会根据实际的占用情况决定是否进行GC，注意这里的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++;
            }
        }
    
        mGarbage = false;
        mSize = o;
    
        // Log.e("SparseArray", "gc end with " + mSize);
    }

获取大小

public int size() {
        if (mGarbage) {
            gc();
        }
    
        return mSize;
    }

由于前面描述的，SparseArray采用了一个标记删除的加速方法，所以在获取大小的时候需要先实际的清除一遍然后获取真实的大小。

根据下标获取key和value

public int keyAt(int index) {
        if (mGarbage) {
            gc();
        }
    
        return mKeys[index];
    }
    
    @SuppressWarnings("unchecked")
    public E valueAt(int index) {
        if (mGarbage) {
            gc();
        }
    
        return (E) mValues[index];
    }

上述方法分别根据下标返回该下标对应的键值对的key或者value，注意index需要在0-size()-1范围内；此外还需要判断是否执行gc()

根据key或者value获取对应的下标

public int indexOfKey(int key) {
        if (mGarbage) {
            gc();
        }
    
        return ContainerHelpers.binarySearch(mKeys, mSize, key);
    }
    
    public int indexOfValue(E value) {
        if (mGarbage) {
            gc();
        }
    
        for (int i = 0; i < mSize; i++)
            if (mValues[i] == value)
                return i;
    
        return -1;
    }

两个方法实现的略微不一样，因为键值对中对键的查找要更加频繁，所以使用了二分查找，而使用值进行查找的机会比较少，所以直接使用for循环。如果查找到了对应的下标，就返回，否则返回负数

清空容器

public void clear() {
        int n = mSize;
        Object[] values = mValues;
    
        for (int i = 0; i < n; i++) {
            values[i] = null;
        }
    
        mSize = 0;
        mGarbage = false;
    }

这里有一点不是很理解的是for循环中为什么不是`mValues[i] = null;`使用一个引用values\[\]的意义在哪里

追加

public void append(int key, E value) {
        if (mSize != 0 && key <= mKeys[mSize - 1]) {
            put(key, value);
            return;
        }
    
        if (mGarbage && mSize >= mKeys.length) {
            gc();
        }
    
        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
        mValues = GrowingArrayUtils.append(mValues, mSize, value);
        mSize++;
    }

该操作如果要插入的key介于最大的key和最小的key之间，那么直接执行普通的put操作，如果大于最大的key，直接追加到尾部

补充一直用到的二分查找

// 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
    }

比较基本的一个二分查找算法，数据结构上都有的