Android SparseArray源码分析

• SparseArray源码分析
• • 总结
  • 基本使用
  • 源码分析
  • • 基本属性
    • get()
    • put()
    • delete()
    • gc()
  • 其他
  • • ContainerHelpers类
    • GrowingArrayUtils类

• 在Android中，某些场景推荐使用SparseArray替代HashMap，其原因是SparseArray更加节省内存，查询效率更高。
• SparseArray内部使用双数组，分别存储Key值和Value值，Key是int类型数组，Value是Object类型数组。
• SparseArray内部使用二分查找定位Key数组中索引值，Key数组的元素是有序的。
• 使用DELETE标记表面删除元素时移动数组。

val sparseArray = SparseArray(5) //存储的数据类型

//增和改
sparseArray.put(1, "A")
sparseArray.put(3, "B")
sparseArray.put(5, "C")
sparseArray.put(2, "D")
sparseArray.put(4, "E")

//删
sparseArray.delete(2) //删除指定key
sparseArray.remove(3) //最终调用delete()
sparseArray.removeAt(0)  //删除指定索引

//查
val value = sparseArray.get(1) //根据key值获取value值
val key = sparseArray.keyAt(0) //根据索引获取key值
val value = sparseArray.valueAt(0) //根据索引索取value值

//遍历
sparseArray.forEach { 
    key, value ->
    Log.e("TAG", "$key ~ $value")
}

public class SparseArray implements Cloneable {
    //DELETE标记
    private static final Object DELETED = new Object();
    
    //是否可以调用gc()回收
    private boolean mGarbage = false;

    //Key数组
    private int[] mKeys;
    //Value数组
    private Object[] mValues;
    
    //元素数量
    private int mSize;

    //无参构造器
    public SparseArray() {
        //默认容量为10
        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;
    }
}

可以通过get()获取指定位置的元素

public E get(int key) {
    return get(key, null);
}

public E get(int key, E valueIfKeyNotFound) {
    //通过二分查找获取key的索引值，
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        //没找到key或value被删除，返回valueIfKeyNotFound值
        return valueIfKeyNotFound;
    } else {
        //合法的key返回具体值
        return (E) mValues[i];
    }
}

可以通过put()存储元素

public void put(int key, E value) {
    //二分查找获取key的索引值
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        //如果找到key，直接赋值
        mValues[i] = value;
    } else {
        //如果没有找到
        i = ~i;

        if (i < mSize && mValues[i] == DELETED) {
            //如果value值被DELETE标记，则直接赋值
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        if (mGarbage && mSize >= mKeys.length) {
            gc();

            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        //向Key数组中插入数据，GrowingArrayUtils.insert()会将元素插入到指定位置上，
        //如果空间不够，则会扩容，扩容机制：如果当前空间小于等于4，则扩容到8；如果当前空间大于4则2被扩容
        //本质操作是调用System.arraycopy()
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        //向Value数组中插入数据
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

可以通过delete()方法删除元素

SparseArray在做删除操作时，为了避免删除元素导致数组移动，同时为了方便插入数据时不移动数组，引入了DELETE标记，避免了频繁操作数组。

public void delete(int key) {
    //二分查找获取索引值
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        //value值被DELETE标记，表示元素被删除了
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}

整理Key数组和Value数组

引入DELETE标记后，虽然数据被删除，但是仍然在数组中占据空间，会影响到一些操作，这时引入gc()方法清除DELETE标记，put() / size()等方法会触发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];

        //清理双数组中被DELETE标记的元素
        if (val != DELETED) {
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }
            o++;
        }
    }

    mGarbage = false;
    mSize = o;
}

package android.util;

class ContainerHelpers {

    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
    }

    static int binarySearch(long[] array, int size, long value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final long 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
    }
}

package com.android.internal.util;

public final class GrowingArrayUtils {

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

        if (currentSize + 1 > array.length) {
            @SuppressWarnings("unchecked")
            T[] newArray = ArrayUtils.newUnpaddedArray(
                    (Class) array.getClass().getComponentType(), growSize(currentSize));
            System.arraycopy(array, 0, newArray, 0, currentSize);
            array = newArray;
        }
        array[currentSize] = element;
        return array;
    }

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

        if (currentSize + 1 > array.length) {
            int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
            System.arraycopy(array, 0, newArray, 0, currentSize);
            array = newArray;
        }
        array[currentSize] = element;
        return array;
    }

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

        if (currentSize + 1 > array.length) {
            long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize));
            System.arraycopy(array, 0, newArray, 0, currentSize);
            array = newArray;
        }
        array[currentSize] = element;
        return array;
    }

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

        if (currentSize + 1 > array.length) {
            boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize));
            System.arraycopy(array, 0, newArray, 0, currentSize);
            array = newArray;
        }
        array[currentSize] = element;
        return array;
    }

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

        if (currentSize + 1 > array.length) {
            float[] newArray = ArrayUtils.newUnpaddedFloatArray(growSize(currentSize));
            System.arraycopy(array, 0, newArray, 0, currentSize);
            array = newArray;
        }
        array[currentSize] = element;
        return array;
    }

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

        if (currentSize + 1 <= array.length) {
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }

        @SuppressWarnings("unchecked")
        T[] newArray = ArrayUtils.newUnpaddedArray((Class)array.getClass().getComponentType(),
                growSize(currentSize));
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }

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

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

        if (currentSize + 1 <= array.length) {
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }

        long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize));
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }

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

        if (currentSize + 1 <= array.length) {
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }

        boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize));
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }

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

    // Uninstantiable
    private GrowingArrayUtils() {}
}