前言

今天我們來了解一下與HashMap類似的數據結構SparseArray，并分析下它的源碼實現。在分析源碼的過程中，我們帶著以下幾個問題來看。

• SparseArray底層數據結構是什么？
• SparseArray如何通過key獲得對應數組下標
• SparseArray的擴容機制是什么？
• SparseArray與HashMap有什么區別？

核心字段

private static final Object DELETED = new Object();private boolean mGarbage = false;private int[] mKeys;private Object[] mValues;private int mSize; 復制代碼

首先我們先來了解一下SparseArray類中聲明的變量都是做什么的，如下

• DELETED 表示刪除狀態(后面詳細說明)
• mGarbage 表示是否GC
• mKeys 表示Key數組，SparseArray中專門存取Key的數組
• mValues 表示Values數組，SparseArray中專門存取Value的數組
• mSize 表示數組實際存儲的元素大小

小結

通過了解以上幾個變量，我們可以大概知道SparseArray底層是通過兩個數組來實現的，一個int數組來存取Key，一個Object數組來存取Value。

構造方法

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;} 復制代碼

可以看出SparseArray默認容量為10，然后我們來看一下put()方法。

put()

public void put(int key, E value) {//通過key獲取對應的數組位置int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//若i>=0，說明key存在，直接賦值if (i >= 0) {mValues[i] = value;} else {//此時i<0，然后對i取反i = ~i;//如果i<mSize并且i對應的Value已經是標記位刪除狀態，那么就復用這個位置if (i < mSize && mValues[i] == DELETED) {mKeys[i] = key;mValues[i] = value;return;}//如果需要GC并且mSize大于等于mKeys數組的長度，那么進行GC，并且重新查找iif (mGarbage && mSize >= mKeys.length) {gc();i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);}//最后分別插入key和value，并且判斷是否需要擴容mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);mSize++;}} 復制代碼

通過分析put()方法源碼，我們可以知道SparseArray添加元素可以分為以下幾步。

• 獲取key對應的數組位置i
• 判斷i是否大于0
  • 如果i>0,說明key存在，直接賦值
  • 如果i<0，說明key不存在
    • 如果i<mSize并且i對應的Value已經是標記位刪除狀態，那么就復用這個位置
    • 如果需要GC并且mSize大于等于mKeys數組的長度，那么進行GC，并且重新查找i
    • 最后分別插入key和value，并且判斷是否需要擴容

查找key對應的數組下標

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; }}return ~lo; } 復制代碼

可以看出通過二分查找的方式來獲得key在數組中對應的下標，最后如果沒找到，會對lo取反并返回。

GC相關方法

private void gc() { //表示實際大小int n = mSize;int o = 0;int[] keys = mKeys;Object[] values = mValues;//遍歷所有元素，如果某個元素標記為DELETED，那么就刪除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++;}}//設為false，表示不需要GCmGarbage = false;mSize = o;} 復制代碼

擴容機制

在插入key和value時調用了GrowingArrayUtils的insert()方法，然后我們來看一下SparseArray里如何進行擴容的，源碼如下。

public static int[] insert(int[] array, int currentSize, int index, int element) {assert currentSize <= array.length;//不需要擴容if (currentSize + 1 <= array.length) {//從index以后的元素向后移一位System.arraycopy(array, index, array, index + 1, currentSize - index);//在index對應的位置賦值array[index] = element;return array;}//需要擴容，創建一個新數組int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));//將array數組中從0到index之間的元素(不包括index對應的元素)復制到新數組中System.arraycopy(array, 0, newArray, 0, index);newArray[index] = element;//再將index之后的元素復制到新數組中System.arraycopy(array, index, newArray, index + 1, array.length - index);return newArray;}public static int growSize(int currentSize) {//如果currentSize小于等于4，就為8，否則乘以2return currentSize <= 4 ? 8 : currentSize * 2;} 復制代碼

通過分析以上方法的源碼，我們知道了SparseArray的擴容機制，主要步驟如下。

• 創建一個新數組，數組容量根據currentSize來判斷
• 將舊數組中，index之前的數組元素復制到新數組中
• 對新數組中的index對應的元素進行賦值
• 將舊數組中，index之后的數組元素復制到新數組中

刪除操作

我們再來看一下SparseArray的刪除方法，通過查看源碼可以發現有多個刪除方法，我們一個個的來看一下。

remove(int key)

public void remove(int key) {delete(key);} public void delete(int key) {//通過key獲得對應的數組下標iint i = ContainerHelpers.binarySearch(mKeys, mSize, key);if (i >= 0) {//如果mValues[i]沒有被標記為DELETED，那么就進行標記，并設置mGarbage為true，表示需要GCif (mValues[i] != DELETED) {mValues[i] = DELETED;mGarbage = true;}}} 復制代碼

可以看出該方法是通過key來進行刪除，主要分為以下幾步。

• 獲得key對應的數組下標
• 如果i>=0，判斷mValues[i]是否被標記為DELETED
  • 如果沒有被標記為DELETED，那么就進行標記，并設置mGarbage為true，表示需要GC

removeAt(int index)

public void removeAt(int index) {if (mValues[index] != DELETED) {mValues[index] = DELETED;mGarbage = true;}} 復制代碼

通過index找到對應的位置進行刪除操作。

查找

get(int key)

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];}}復制代碼

從以上源碼可以看出SparseArray通過key來查找對應的元素，主要有以下幾步。

• 獲取key對應的數組下標
• 如果i小于0或者mValues[i]已經標記為DELETED，返回valueIfKeyNotFound，也就是null
• 否則就返回mValues[i]

SparseArray與HashMap區別

性能

在性能方面，SparseArray適合存儲少量的數據。如果存儲大量的數據，在進行擴容時，會有比較大的性能開銷。

底層數據結構

SparseArray是由兩個數組組成，一個數組負責存儲key(int類型)，一個數組負責存儲value，類似于key為int類型的HashMap。

刪除

SparseArray的刪除操作先將要刪除的數組元素標記為DELETED，然后當存儲相同key對應的value時，可以進行復用。

總結

SparseArray在內存方面上比HashMap消耗更少，所以對于數據不大的情況下，優先使用SparseArray，畢竟在Android中內存是比較重要的。

轉載于:https://juejin.im/post/5ca31d4bf265da30bf15ccdb

總結

以上是生活随笔為你收集整理的Java填坑系列之SparseArray的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。