SparseArray源碼分析

• SparseArray(稀疏數(shù)組)是什么鸠澈？

  類似于map隧哮，可以儲存key-value鍵值對苛萎，與HashMap不同因為其key只能是整型int而且內(nèi)部存儲結(jié)構(gòu)是數(shù)組（最新HashMap存儲結(jié)構(gòu)為紅黑樹+鏈表+數(shù)組）；為android的工具類掂墓，用于優(yōu)化HashMap<Integer, V>這種情況。由于其內(nèi)部使用數(shù)組來存儲key和value看成，且數(shù)組內(nèi)容可能大部分都并未使用君编，因此叫稀疏數(shù)組。

• SparseArray的優(yōu)勢劣勢川慌？

  與HashMap相對比吃嘿，SparseArray的內(nèi)存效率更高，因為它避免了自動裝箱鍵梦重，并且沒有HashMap中額外的節(jié)點(鏈表節(jié)點兑燥，紅黑樹節(jié)點)內(nèi)存開銷。但是由于SparseArray將key放在一個數(shù)組結(jié)構(gòu)中琴拧，且使用二分查找降瞳，因此其不適用于大數(shù)據(jù)量的儲存。例如儲存數(shù)百個數(shù)據(jù)蚓胸，速度和HashMap相當(dāng)挣饥，性能差異不明顯，并且兩者之間性能差異小于50%沛膳。相比于HashMap扔枫，SparseArray更節(jié)省內(nèi)存，但是在大數(shù)據(jù)量的時候锹安，插入和查找的效率都會比HashMap低短荐。

• SparseArray的應(yīng)用場景倚舀？

  適用于儲存小容量數(shù)據(jù)，key必須為int型

下面分析源碼：

類成員變量：

private static final Object DELETED = new Object();
private boolean mGarbage = false;

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

• DELETED：用于標(biāo)記已刪除的key-value
• mGarbage：用于標(biāo)記是否需要回收被刪除的數(shù)據(jù)
• mKeys：用于儲存key
• mValues：用于儲存values
• mSize：當(dāng)前包含非空元素(value)的條目(key-value)忍宋，未調(diào)用gc前痕貌，包括value為DELETED的情況，這里的gc并非為java中的System.gc()糠排，而是SparseArray中的gc方法舵稠。

構(gòu)造函數(shù)

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

• 默認(rèn)構(gòu)造函數(shù)：調(diào)用帶參構(gòu)造函數(shù)，指定容量為10
• 帶參(指定數(shù)組容量)構(gòu)造函數(shù)：容量為空則賦值mKeys和mValues為長度為0的數(shù)組乳讥，否則創(chuàng)建最小長度為initialCapacity的Unpadded Object數(shù)組，再將key數(shù)組的大小指定為value數(shù)組的大小廓俭。

關(guān)于EmptyArray：

點我查看源碼

//版本名稱:  Oreo API Level:  26
public final class EmptyArray {
    private EmptyArray() {}

    public static final boolean[] BOOLEAN = new boolean[0];
    public static final byte[] BYTE = new byte[0];
    public static final char[] CHAR = new char[0];
    public static final double[] DOUBLE = new double[0];
    public static final float[] FLOAT = new float[0];
    public static final int[] INT = new int[0];
    public static final long[] LONG = new long[0];

    public static final Class<?>[] CLASS = new Class[0];
    public static final Object[] OBJECT = new Object[0];
    public static final String[] STRING = new String[0];
    public static final Throwable[] THROWABLE = new Throwable[0];
    public static final StackTraceElement[] STACK_TRACE_ELEMENT = new StackTraceElement[0];
    public static final java.lang.reflect.Type[] TYPE = new java.lang.reflect.Type[0];
    public static final java.lang.reflect.TypeVariable[] TYPE_VARIABLE =
        new java.lang.reflect.TypeVariable[0];
}

關(guān)于ArrayUtils.newUnpaddedObjectArray：

點我查看源碼

// 版本名稱:  Oreo API Level:  26
public static Object[] newUnpaddedObjectArray(int minLen) {
    return (Object[])VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen);
}

其中調(diào)用了VMRuntime.getRuntime().newUnpaddedArray來分配object數(shù)組內(nèi)存云石，該方法字面意思為new一個un padded的數(shù)組，即new一個不填充的數(shù)組研乒。返回一個至少為minLen長度的數(shù)組汹忠，但有可能會更大。增加的大小用于避免數(shù)組排列時填充的大小雹熬，填充量取決于組件類型和內(nèi)存分配器實現(xiàn)宽菜。因為編譯器會根據(jù)數(shù)組對齊，在申請obj內(nèi)存時竿报，往往會分配大于該obj的實際內(nèi)存而保證自然對齊使CPU讀寫更加高效铅乡，但是這往往需要填充一些沒有用到的空間，因此烈菌，為了不浪費這個空間阵幸，array變得更大了。

關(guān)于數(shù)據(jù)結(jié)構(gòu)對齊可以看wiki描述：https://en.wikipedia.org/wiki/Data_structure_alignment

put

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //二叉查找芽世，可以看后面的方法解釋

    if (i >= 0) {
        mValues[i] = value; //數(shù)組中存在該key挚赊，直接更新值
    } else {
        i = ~i;  //取到要插入的數(shù)組下標(biāo)
    
         //如果要插入的下標(biāo)小于mSize且被標(biāo)志為已刪除的話
         //重新將key賦值，value賦值
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
         
         //如果標(biāo)記為mBarbage且mSize大于或者等于key數(shù)組大小
        if (mGarbage && mSize >= mKeys.length) {
             //gc方法回收已刪除的數(shù)據(jù)
            gc();

            //重新進(jìn)行二叉搜索济瓢，因為索引可能已經(jīng)發(fā)生變化了
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        
         //插入key
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
         //插入value
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
         //mSize加1
        mSize++;
    }
}

• 首先通過二分查找是否在數(shù)組中存在該key荠割，若找到，則返回對應(yīng)的數(shù)組下標(biāo)旺矾，否則蔑鹦，返回要插入的數(shù)組下標(biāo)的負(fù)數(shù)
• 如果存在的話，直接將對應(yīng)的value數(shù)組下標(biāo)賦值
• 如果不存在的話箕宙，返回要插入的數(shù)組下標(biāo)的負(fù)數(shù)举反，因此這里重新取反，拿到要插入數(shù)組下標(biāo)的整數(shù)扒吁。再根據(jù)條件判斷key是否為已刪除數(shù)據(jù)火鼻，是否要進(jìn)行數(shù)組壓縮室囊，最后插入key和value到各自數(shù)組中。

關(guān)于ContainerHelpers.binarySearch：

//該方法要求array必須為有序數(shù)組
//array：要查找的數(shù)組
//size：數(shù)組中有效大小魁索，從下表0開始融撞，到size-1為數(shù)組的有效范圍
//value：要查找的值
static int binarySearch(int[] array, int size, int value) {
    //定義low低數(shù)組下標(biāo)，用于數(shù)組中往上查找粗蔚，最小為0
    int lo = 0; 
    
    //定義high高數(shù)組下標(biāo)尝偎，用于數(shù)組中往下查找，最大為size-1
    int hi = size - 1; 

    //如果lo <= hi鹏控，則循環(huán)
    while (lo <= hi) {
         //取數(shù)組中間下標(biāo)
         //右移1位即等同于除以2的1次方即除2致扯，無符號右移，空位都以0補齊当辐，與運算比除預(yù)算效率高
        final int mid = (lo + hi) >>> 1;  
        
         //取數(shù)組中間下標(biāo)的值
        final int midVal = array[mid];

         //若中間值小于value抖僵，則將low賦值為mid+1，繼續(xù)往上查找
        if (midVal < value) {
            lo = mid + 1;
            
         //若中間值大于value缘揪，則將high賦值為mid-1耍群，繼續(xù)往下查找
        } else if (midVal > value) {
            hi = mid - 1;
            
         //已找到，返回數(shù)組下標(biāo)
        } else {
            return mid;  // value found
        }
    }
    //否則返回一個小于0的值找筝，且該值還有另外一個含義：
    //要插入的位置下標(biāo)蹈垢，SparseArray拿到這個返回值后，便可知道要插入的下標(biāo)
    //該值還有另外一個作用就是可以保證數(shù)組的有序性
    return ~lo;  // value not present
}

關(guān)于gc

該方法為SparseArray的回收方法袖裕，用于將刪除的數(shù)據(jù)從mKeys數(shù)組和mValues數(shù)組中刪除曹抬，并將剩下的數(shù)據(jù)往前移動

private void gc() {
    // Log.e("SparseArray", "gc start with " + mSize);

    int n = mSize; //當(dāng)前數(shù)組有效大小，因為mkey大小和mValues大小相同急鳄，因此這里mSize是對兩者而言的
    int o = 0; //數(shù)組中非null的數(shù)量沐祷，即有效數(shù)據(jù)數(shù)量，起始值為0
    
    int[] keys = mKeys;
    Object[] values = mValues;

    for (int i = 0; i < n; i++) {
        Object val = values[i];

         //不是被刪除的元素
        if (val != DELETED) { 
             //若i 不等于 o的話
             //證明o為被刪除的下標(biāo)攒岛，因此這里需要將下標(biāo)為o的key數(shù)組的值
             //賦值為下標(biāo)為i的值赖临，且將下標(biāo)為o的value數(shù)組的值賦值為當(dāng)前val
             //最后將已經(jīng)移走的當(dāng)前下標(biāo)i對應(yīng)的value數(shù)組的值置為null
             //但是這里可以看到，key[i]并沒有置為0灾锯，因為不設(shè)置為0的話
             //不會影響二叉查找兢榨，因為后面mSize為非null數(shù)據(jù)數(shù)量
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }
            
             //有效數(shù)據(jù)+1
            o++;
        }
    }

    mGarbage = false; //gc后將回收標(biāo)志置為false
    mSize = o; //將mSize賦值為數(shù)組中非null的數(shù)量

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

關(guān)于GrowingArrayUtils.insert

點我查看源碼

//array: 要插入的數(shù)組
//currentSize: 數(shù)組中的元素數(shù)量，小于或等于array.length
//index: 要插入的下標(biāo)
//element: 要插入的元素
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    //如果數(shù)組中的元素數(shù)量大于數(shù)組長度的話顺饮，拋出異常
    assert currentSize <= array.length;
    
    //如果在當(dāng)前數(shù)組再插入一個元素吵聪，并且不超過數(shù)組的大小的話
    if (currentSize + 1 <= array.length) {
         //將原本數(shù)據(jù)從index開始，往后移動currentSize - index個數(shù)據(jù)
        System.arraycopy(array, index, array, index + 1, currentSize - index);
         //將index對應(yīng)的值賦值為要插入的元素
        array[index] = element;
        return array;
    }

    @SuppressWarnings("unchecked")
    //否則需要重新創(chuàng)建數(shù)組兼雄，且將原本數(shù)組的內(nèi)容賦值到新數(shù)組中
    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;
}

append

直接put一個key-value到數(shù)組中吟逝，針對key大于mKeys數(shù)組所有現(xiàn)有鍵的情況進(jìn)行優(yōu)化。

public void append(int key, E value) {
     //若當(dāng)前mSize不為0且key小于mKeys數(shù)組中的最大值
    if (mSize != 0 && key <= mKeys[mSize - 1]) {
         //直接put
        put(key, value);
        return;
    }
    
     //mGarbage回收標(biāo)志為true且mSize大于或等于mKeys數(shù)組長度
    if (mGarbage && mSize >= mKeys.length) {
         //調(diào)用gc方法
        gc();
    }
    
    
    //插入key
    mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
    //插入value
    mValues = GrowingArrayUtils.append(mValues, mSize, value);
    
    mSize++;
}

setValueAt

按照給定的index替換value

public void setValueAt(int index, E value) {
    //mGarbage回收標(biāo)志為true的話調(diào)用gc方法
    if (mGarbage) {
        gc();
    }
    
    //將對應(yīng)index下表的值賦值為value
    mValues[index] = value;
}

get

//根據(jù)key獲取value
public E get(int key) {
    return get(key, null);
}

//根據(jù)key獲取value赦肋，若該key不存在或者已刪除块攒，返回valueIfKeyNotFound
public E get(int key, E valueIfKeyNotFound) {
     //首先進(jìn)行二分查找 找到key的數(shù)組下表
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    
     //i小于0代表mKeys數(shù)組中不包含該Key励稳，或者該key-value已被刪除
    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

remove

//刪除key對應(yīng)的數(shù)據(jù)
public void remove(int key) {
    delete(key);
}

//刪除key對應(yīng)的數(shù)據(jù)
public void delete(int key) {
    //先通過二叉查找是否存在該key
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    
    //i >= 0代表存在該key且i為其在mKeys數(shù)組中的下標(biāo)
    if (i >= 0) {
         //且該key對應(yīng)的value還沒被刪除
        if (mValues[i] != DELETED) {
             //將對應(yīng)mValues數(shù)組下表的值置位DELETED已刪除
            mValues[i] = DELETED;
             //將回收標(biāo)志置為true，在調(diào)用size(), put(), append()等方法時需要
             //調(diào)用gc方法將被標(biāo)記為已刪除的數(shù)據(jù)囱井，即對應(yīng)的value值為DELETED
             //從數(shù)組移除驹尼，且將后面的沒被刪除的數(shù)據(jù)往前移動
            mGarbage = true;
        }
    }
}

//刪除對應(yīng)下表的數(shù)據(jù)
public void removeAt(int index) {
    if (mValues[index] != DELETED) {
        mValues[index] = DELETED;
         //將回收標(biāo)志置為true
        mGarbage = true;
    }
}

//刪除從對應(yīng)下表開始，大小為size的數(shù)據(jù)
public void removeAtRange(int index, int size) {
    final int end = Math.min(mSize, index + size);
    for (int i = index; i < end; i++) {
        removeAt(i);
    }
}

查詢

indexOfKey

根據(jù)key獲取其在數(shù)組中的下表

public int indexOfKey(int key) {
     //mGarbage回收標(biāo)志為true的話調(diào)用gc方法
    if (mGarbage) {
        gc();
    }
    
    //若數(shù)組中存在該key庞呕，則返回對應(yīng)下表
    //否則返回一個負(fù)數(shù)
    return ContainerHelpers.binarySearch(mKeys, mSize, key);
}

indexOfValue

根據(jù)value獲取其在數(shù)組中的下表

public int indexOfValue(E value) {
    //mGarbage回收標(biāo)志為true的話調(diào)用gc方法
    if (mGarbage) {
        gc();
    }
    
    //遍歷mValues數(shù)組新翎，判斷是否相等
    for (int i = 0; i < mSize; i++) {
        if (mValues[i] == value) { 
             //若相等，則返回i
            return i;
        }
    }
    
    //否則返回-1
    return -1;
}

keyAt

獲取下表為index的key

public int keyAt(int index) {
     //mGarbage回收標(biāo)志為true的話調(diào)用gc方法
    if (mGarbage) {
        gc();
    }

     //返回mKeys數(shù)組數(shù)據(jù)
    return mKeys[index];
}

valueAt

獲取下表為index的value

public E valueAt(int index) {
     //mGarbage回收標(biāo)志為true的話調(diào)用gc方法
    if (mGarbage) {
        gc();
    }

    //返回mValues/數(shù)組數(shù)據(jù)
    return (E) mValues[index];
}