SparseArray原始碼分析

總結

• 在Android中，某些場景推薦使用SparseArray替代HashMap，其原因是SparseArray更加節省記憶體，查詢效率更高，
• SparseArray內部使用雙陣列，分別存盤Key值和Value值，Key是int型別陣列，Value是Object型別陣列，
• SparseArray內部使用二分查找定位Key陣列中索引值，Key陣列的元素是有序的，
• 使用DELETE標記表面洗掉元素時移動陣列，

基本使用

val sparseArray = SparseArray<String>(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<E> 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()

可以通過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()

可以通過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()

可以通過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;
        }
    }
}

gc()

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

其他

ContainerHelpers類

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

GrowingArrayUtils類

package com.android.internal.util;

public final class GrowingArrayUtils {

    /**
     * Appends an element to the end of the array, growing the array if there is no more room.
     * @param array The array to which to append the element. This must NOT be null.
     * @param currentSize The number of elements in the array. Must be less than or equal to
     *                    array.length.
     * @param element The element to append.
     * @return the array to which the element was appended. This may be different than the given
     *         array.
     */
    public static <T> T[] append(T[] array, int currentSize, T element) {
        assert currentSize <= array.length;

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

    /**
     * Primitive int version of {@link #append(Object[], int, Object)}.
     */
    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;
    }

    /**
     * Primitive long version of {@link #append(Object[], int, Object)}.
     */
    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;
    }

    /**
     * Primitive boolean version of {@link #append(Object[], int, Object)}.
     */
    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;
    }

    /**
     * Primitive float version of {@link #append(Object[], int, Object)}.
     */
    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;
    }

    /**
     * Inserts an element into the array at the specified index, growing the array if there is no
     * more room.
     *
     * @param array The array to which to append the element. Must NOT be null.
     * @param currentSize The number of elements in the array. Must be less than or equal to
     *                    array.length.
     * @param element The element to insert.
     * @return the array to which the element was appended. This may be different than the given
     *         array.
     */
    public static <T> 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<T>)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;
    }

    /**
     * Primitive int version of {@link #insert(Object[], int, int, Object)}.
     */
    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;
    }

    /**
     * Primitive long version of {@link #insert(Object[], int, int, Object)}.
     */
    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;
    }

    /**
     * Primitive boolean version of {@link #insert(Object[], int, int, Object)}.
     */
    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;
    }

    /**
     * Given the current size of an array, returns an ideal size to which the array should grow.
     * This is typically double the given size, but should not be relied upon to do so in the
     * future.
     */
    public static int growSize(int currentSize) {
        return currentSize <= 4 ? 8 : currentSize * 2;
    }

    // Uninstantiable
    private GrowingArrayUtils() {}
}