Java&Android集合框架須知須會(3)

NO IMAGE

公眾號:字節數組,熱衷於分享 Android 系統源碼解析,Jetpack 源碼解析、熱門開源庫源碼解析等面試必備的知識點

本系列文章會陸續對 Java 和 Android 的集合框架(JDK 1.8,Android SDK 30)中的幾個常見容器結合源碼進行介紹,瞭解不同容器在數據結構、適用場景、優勢點上的不同,希望對你有所幫助

本篇文章再來分析下 SparseArray 和 ArrayMap 這兩個 Android 系統獨有的集合框架類,這兩個容器在使用上類似於 HashMap,都是用於存儲鍵值對。由於 Android 系統對於內存比較敏感,所以 SparseArray 和 ArrayMap 在內存使用方面會比較剋制,這裡就來分析下其實現原理和優勢點

一、SparseArray

使用 Android Studio 的同學可能遇到過一個現象,就是如果在代碼中聲明瞭 Map<Integer,Object> 類型變量的話,Android Studio 會提示:Use new SparseArray<Object>(...) instead for better performance ...,即用 SparseArray< Object > 性能更優,可以用來替代 HashMap

這裡就來介紹下 SparseArray 的內部原理,看看它相比 HashMap 有什麼性能優勢

1、基本概念

SparseArray 的使用方式:

        SparseArray<String> sparseArray = new SparseArray<>();
sparseArray.put(100, "https://juejin.cn/user/923245496518439");
sparseArray.remove(100);
sparseArray.get(100);
sparseArray.removeAt(29);

SparseArray< E > 相當於 Map< Integer , E > ,key 值固定為 int 類型,在初始化時只需要聲明 value 的數據類型即可,其內部用兩個數組分別來存儲 key 和 value:int[] mKeys ; Object[] mValues

mKeys 和 mValues 按照如下規則對應起來:

  • 假設要向 SparseArray 存入 key 為 10,value 為 200 的鍵值對,則先將 10 存到 mKeys 中,假設 10 在 mKeys 中對應的索引值是 2,則將 value 存入 mValues[2] 中
  • mKeys 中的元素值按照遞增的方法進行存儲,每次存放新的鍵值對時都通過二分查找的方式將 key 插入到 mKeys 中
  • 當要從 SparseArray 取值時,則先判斷 key 在 mKeys 中對應的索引,然後根據該索引從 mValues 中取值

從以上可以看出來的一點就是:SparseArray 避免了 HashMap 每次存取值時的裝箱拆箱操作,key 值保持為基本數據類型 int,減少了性能開銷

2、類聲明

SparseArray 本身並沒有直接繼承於任何類,內部也沒有使用到 Java 原生的集合框架,所以 SparseArray 是 Android 系統自己實現的一個集合框架

	public class SparseArray<E> implements Cloneable

3、全局變量

mGarbage 是 SparseArray 的一個優化點之一,用於標記當前是否有需要垃圾回收(GC)的元素,當該值被置為 true 時,意味著當前狀態需要進行垃圾回收,但回收操作並不會馬上進行,而是在後續操作中再統一進行

    //鍵值對被移除後對應的 value 會變成此值,用來當做 GC 標記位
private static final Object DELETED = new Object();
//用於標記當前是否有待垃圾回收(GC)的元素
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
//當前集合元素的數量
//該值並不一定是時時處於正確狀態,因為有可能出現只刪除 key 和 value 兩者之一的情況
//所以 size() 方法內都會先進行 GC
private int mSize;

4、構造函數

key 數組和 value 數組的默認大小都是 10,如果在初始化時已知最終數據量的大小,則可以直接指定初始容量,這樣可以避免後續的擴容操作

    //設置數組的默認初始容量為10
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;
}

5、添加元素

添加元素的方法有幾個,主要看 put(int key, E value) 方法就可以,該方法用於存入 key 和 value 組成的鍵值對。按照前面所說的 SparseArray 存儲鍵值對的規則,put 方法會先判斷當前 mKeys 中是否已經有相同的 key 值,有的話就用 value 覆蓋 mValues 中的舊值。如果不存在相同 key 值,在將 key 插入到 mKeys 後需要在 mValues 的相同索引位置插入 value,由於 mKeys 是會按照大小對元素值進行排序存儲的,所以將 key 插入到 mKeys 可能會導致元素重新排序,從而連鎖導致 mValues 也需要重新排序

put 方法從 mKeys 查找 key 用的是 ContainerHelpers 類提供的二分查找方法:binarySearch,用於獲取 key 在 mKeys 中的當前索引(存在該 key 的話)或者是應該存放的位置的索引(不存在該 key),方法的返回值可以分為三種情況:

  1. 如果 mKeys 中存在對應的 key,則直接返回對應的索引值
  2. 如果 mKeys 中不存在對應的 key
    1. 假設 mKeys 中存在”值比 key 大且大小與 key 最接近的值的索引”為 presentIndex,則此方法的返回值為 ~presentIndex
    2. 如果 mKeys 中不存在比 key 還要大的值的話,則返回值為 ~mKeys.length
    // 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
}

可以看到,如果 mKeys 存在目標 key,那麼返回值即對應的索引位置。如果不存在目標 key,其返回值也指向了應該讓 key 存入的位置,因為當不存在目標 key 時,將計算出的索引值進行 ~ 運算後返回值一定是負數,從而與“找得到目標 key 的情況(返回值大於等於0)”的情況區分開。從這裡可以看出該方法的巧妙之處,單純的一個返回值就可以區分出多種情況,且通過這種方式來存放數據可以使得 mKeys 的內部值一直是按照值遞增的方式來排序的

再來具體看看 put 方法的邏輯

	public void put(int key, E value) {
//用二分查找法查找指定 key 在 mKeys 中的索引值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) { //對應已經存在相同 key 的情況
mValues[i] = value;
} else {
//取反,拿到真實的索引位置
i = ~i;
//如果目標位置還未賦值,則直接存入數據即可
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
//如果存在冗餘數據,那麼就先進行 GC
if (mGarbage && mSize >= mKeys.length) {
gc();
//GC 後再次進行查找,因為值可能已經發生變化了
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//索引 i 位置已經用於存儲其它數據了,此時就需要對數組元素進行遷移
//所以從索引 i 開始的所有數據都需要向後移動一位,並將 key 存到 mKeys[i]
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
//將索引 index 處的元素賦值為 value
//知道目標位置的話可以直接向 mValues 賦值
public void setValueAt(int index, E value) {
if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
// The array might be slightly bigger than mSize, in which case, indexing won't fail.
// Check if exception should be thrown outside of the critical path.
throw new ArrayIndexOutOfBoundsException(index);
}
//如果需要則先進行垃圾回收
if (mGarbage) {
gc();
}
mValues[index] = value;
}
//和 put 方法類似
//但在存入數據前先對數據大小進行了判斷,有利於減少對 mKeys 進行二分查找的次數
//所以在“存入的 key 比現有的 mKeys 值都大”的情況下會比 put 方法性能高
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++;
}

6、移除元素

上文說了,布爾變量 mGarbage 用於標記當前是否有待垃圾回收(GC)的元素,當該值被置為 true 時,即意味著當前狀態需要進行垃圾回收,但回收操作並不馬上進行,而是在後續操作中再完成

以下幾個方法在移除元素時,都只是切斷了 mValues 對 value 的引用,而 mKeys 並沒有進行回收,這個操作會留到 gc() 進行處理

	public void delete(int key) {
//用二分查找法查找指定 key 在 mKeys 中的索引值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
//標記當前需要進行垃圾回收
mGarbage = true;
}
}
}
public void remove(int key) {
delete(key);
}
//和 delete 方法基本相同,差別在於會返回 key 對應的元素值
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;
}
//刪除指定索引對應的元素值
public void removeAt(int index) {
if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
// The array might be slightly bigger than mSize, in which case, indexing won't fail.
// Check if exception should be thrown outside of the critical path.
throw new ArrayIndexOutOfBoundsException(index);
}
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
//標記當前需要進行垃圾回收
mGarbage = true;
}
}
//刪除從起始索引值 index 開始之後的 size 個元素值
public void removeAtRange(int index, int size) {
//避免發生數組越界的情況
final int end = Math.min(mSize, index + size);
for (int i = index; i < end; i++) {
removeAt(i);
}
}
//移除所有元素值
public void clear() {
int n = mSize;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
values[i] = null;
}
mSize = 0;
mGarbage = false;
}

7、查找元素

查找元素的方法較多,邏輯都挺簡單的

    //根據 key 查找相應的元素值,查找不到則返回默認值
@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
//用二分查找法查找指定 key 在 mKeys 中的索引值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//如果找不到該 key 或者該 key 尚未賦值,則返回默認值
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
//根據 key 查找相應的元素值,查找不到則返回 null
public E get(int key) {
return get(key, null);
}
//因為 mValues 中的元素值並非一定是連貫的,有可能摻雜著 DELETED 
//所以在遍歷前需要先進行 GC,這樣通過數組取出的值才是正確的
@SuppressWarnings("unchecked")
public E valueAt(int index) {
if (mGarbage) {
gc();
}
return (E) mValues[index];
}
//根據索引值 index 查找對應的 key 
public int keyAt(int index) {
if (mGarbage) {
gc();
}
return mKeys[index];
}
//根據 key 對應的索引值
public int indexOfKey(int key) {
if (mGarbage) {
gc();
}
return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//根據 value 查找對應的索引值
public int indexOfValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++) {
if (mValues[i] == value) {
return i;
}
}
return -1;
}
//與 indexOfValue 方法類似,但 indexOfValue 方法是通過比較 == 來判斷是否同個對象
//而此方法是通過 equals 方法來判斷是否同個對象
public int indexOfValueByValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++) {
if (value == null) {
if (mValues[i] == null) {
return i;
}
} else {
if (value.equals(mValues[i])) {
return i;
}
}
}
return -1;
}

8、垃圾回收

因為 SparseArray 中會出現只移除 key 和 value 兩者之一的情況,導致當前數組中的有效數據並不是全都緊挨著排列在一起的,即存在無效值,因此 gc() 方法會根據 mValues 中到底存在多少有效數據,將 mKeys 和 mValues 中的數據進行重新排列,將有意義的元素值緊挨著排序在一起

		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];
//val 非 DELETED ,說明該位置可能需要移動數據
if (val != DELETED) {
//將索引 i 處的值賦值到索引 o 處
//所以如果 i == o ,則不需要執行代碼了
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = false;
mSize = o;
}

9、優劣勢總結

從上文的介紹來看,SparseArray 的主要優勢有以下幾點:

  • 避免了基本數據類型 int 的裝箱拆箱操作
  • 和 HashMap 中每個存儲結點都是一個類對象不同,SparseArray 不需要用於包裝 key 的結構體,單個元素的存儲成本更加低廉
  • 在數據量不大的情況下,查找效率較高(二分查找法)
  • 延遲了垃圾回收的時機,只在需要的時候才一次性進行

劣勢有以下幾點:

  • 具有特定的適用範圍,key 只能是 int 類型
  • 插入鍵值對時可能需要移動大量的數組元素
  • 數據量較大時,查找效率(二分查找法)會明顯降低,需要經過多次折半查找才能定位到目標數據。而 HashMap 在沒有哈希衝突的情況下只需要進行一次哈希計算即可定位到目標元素,有哈希衝突時也只需要對比鏈表或者紅黑樹上的元素即可

10、關聯類

SparseArray 屬於泛型類,所以即使 value 是基本數據類型也會被裝箱和拆箱,如果想再省去這一部分開銷的話,可以使用 SparseBooleanArray、SparseIntArray 和 SparseLongArray 等三個容器,這三個容器的實現原理和 SparseArray 相同,但是 value 還是屬於基本數據類型

此外,系統還提供了 LongSparseArray 這個容器類,其實現原理和 SparseArray 類似,但是 key 固定為 long 類型,value 通過泛型來聲明,對於日常開發中比較有用的一點是可以用來根據 viewId 存儲 view

二、ArrayMap

ArrayMap 屬於泛型類,繼承了 Map 接口,其使用方式和 HashMap 基本一樣,但在內部邏輯上有著很大差異,所以需要了解其實現原理後才能明白 ArrayMap 到底適用於哪些場景

	public final class ArrayMap<K, V> implements Map<K, V> {
}

1、存儲機制

ArrayMap 中包含以下兩個數組。mHashes 只用於存儲鍵值對中 key 的哈希值,mArray 則用於存儲 key 和 value,即每個存入的鍵值對會被一起存入 mArray 中

    // Hashes are an implementation detail. Use public key/value API.
int[] mHashes;
// Storage is an implementation detail. Use public key/value API.
Object[] mArray;

當向 ArrayMap 插入鍵值對時,會先計算出 key 的哈希值,將 keyHash 按照大小順序存入 mHashes 中,拿到其位置索引 index。然後將 key 存入 mArray 的 index<<1 位置,將 value 存入 mArray 的 (index<<1 + 1) 位置,即 key 和 value 會存儲在相鄰的位置。從這個位置對應關係來看,mArray 的所需容量至少也需要是 mHashes 的兩倍,且每個 key-value 的排列關係也是和 keyHash 的排列保持一致

當要通過 key 對象向 ArrayMap 取值時,就先計算出 keyHash,然後通過二分查找法找到 keyHash 在 mHashes 中的位置索引 index,然後在 (index<<1 + 1)位置從 mArray 拿到 value

2、添加元素

有幾個用於添加元素的方法,當中重點看 put 方法即可,其它添加元素的方法都需要依靠該方法來實現,該方法參數就用於傳入鍵值對。前文有講到,key-value 最終是會相鄰著存入 mArray 中的,而 key-value 在 mArray 中的位置是由 keyHash 和 mHashes 來共同決定的,所以 put 方法的整體邏輯如下所訴:

  1. 根據二分查找法獲取到 keyHash 在 mHashes 中的索引位置 index,
  2. 如果 index 大於等於 0,說明在 mArray 中 key 已存在,那麼直接覆蓋舊值即可,結束流程
  3. 如果 index 小於 0,說明在 mArray 中 key 不存在,~index 此時代表的是 keyHash 按照遞增順序應該插入 mHashes 的位置
  4. 判斷是否需要擴容,需要的話則進行擴容。如果符合緩存標準的話,則會緩存擴容前的數組
  5. 對最終的數組進行數據遷移,插入 key-value 和 keyHash
	@Override
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
//第一步
if (key == null) {
hash = 0; 
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
//第二步
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
//第三步
index = ~index;
//第四步
if (osize >= mHashes.length) {
//ArrayMap 的擴容機制相比 HashMap 會比較剋制
//當數組長度已超出 BASE_SIZE*2 後,數組容量按照 1.5 倍來擴容
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, osize);
}
//第五步
if (index < osize) {
if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
+ " to " + (index+1));
System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
if (osize != mSize || index >= mHashes.length) {
throw new ConcurrentModificationException();
}
}
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}

append 方法也是用於添加元素的,帶有一點“追加”的意思,即本意是外部可以確定本次插入的 key 的 hash 值比當前所有已有值都大,那麼就可以直接向 mHashes 的尾部插入數據,從而節省了二分查找的過程。所以 append 方法會先和 mHashes 的最後一個元素值進行對比,如果 keyHash 比該值大的話就說明可以直接保存到尾部,校驗不通過的話還是會調用 put 方法

    public void append(K key, V value) {
int index = mSize;
final int hash = key == null ? 0
: (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
if (index >= mHashes.length) {
throw new IllegalStateException("Array is full");
}
//如果 mHashes 當前的最後一個值比 hash 大,hash 沒法直接插到尾部,那麼就還是需要調用 put 方法
if (index > 0 && mHashes[index-1] > hash) {
RuntimeException e = new RuntimeException("here");
e.fillInStackTrace();
Log.w(TAG, "New hash " + hash
+ " is before end of array hash " + mHashes[index-1]
+ " at index " + index + " key " + key, e);
put(key, value);
return;
}
//將 key-value 直接插入到數組尾部
mSize = index+1;
mHashes[index] = hash;
index <<= 1;
mArray[index] = key;
mArray[index+1] = value;
}

3、獲取元素

獲取元素的方法主要看 indexOf(Object key, int hash)方法即可,只要理解了該方法是如何獲取 keyIndex 的,那麼就能夠對 ArrayMap 的存儲結構有更明確的認知

indexOf 方法用於獲取和 key,hash 均能對應上的元素的哈希值在 mHashes 中的索引位置。我們知道,keyHash 是存儲在 mHashes 中的,而 key-value 又是存儲在 mArray 中的,但我們無法只根據 keyHash 就準確對應上 key-value,因為不同的 key 有可能有相同的 hash 值,即需要考慮哈希衝突的情況,所以 indexOf 方法除了需要對比 hash 值大小是否相等外還需要對比 key 的相等性。所以 indexOf 方法的具體邏輯如下所訴:

  1. 通過二分查找法獲取到 mHashes 中和 hash 相等的值的索引 index
  2. 如果 index 小於 0,說明不存在該 key,那麼就返回 index,~index 就是 hash 插入 mHashes 後的位置索引。結束流程
  3. index 大於等於 0,說明 key 有可能存在,之所以說可能,因為存在 key 不同但 hash 值相等的情況
  4. 判斷 mArray 中 index<<1 位置的元素是否和 key 相等,如果相等說明已經找到了目標位置,返回 index。結束流程
  5. 此時可以確定發生了哈希衝突,那麼就還是需要對 mArray 進行相等性對比了,而之所以要分為兩個 for 循環也是為了減少遍歷次數,因為相同 hash 值是會靠攏在一起的,所以分別向兩側進行遍歷查找。如果 key 和 keyHash 的相等性均校驗通過,那麼就返回對應的索引。結束流程
  6. 會執行到這裡,說明還是沒有找到和 key 相等的元素值,那麼就拿到 hash 應該存入 mHashes 後的索引,~ 運算後返回
	int indexOf(Object key, int hash) {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
//第一步
int index = binarySearchHashes(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
//第二步
if (index < 0) {
return index;
}
// If the key at the returned index matches, that's what we want.
//第四步
if (key.equals(mArray[index<<1])) {
return index;
}
//第五步
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}
// Key not found -- return negative value indicating where a
// new entry for this key should go.  We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
//第六步
return ~end;
}

4、緩存機制

ArrayMap 內部包含了對 mHashes 和 mArray 這兩個數組進行緩存的機制,避免由於頻繁創建數組而造成內存抖動,這一點還是比較有意義的。在 Android 系統中 Bundle 是使用得很頻繁的一個類,其內部就通過 ArrayMap 來存儲鍵值對,這可以從 Bundle 的父類 BaseBundle 看到。所以 ArrayMap 的數組緩存機制在我看來更多的是面對系統運行時的優化措施

public class BaseBundle {
@UnsupportedAppUsage
ArrayMap<String, Object> mMap = null;
public void putBoolean(@Nullable String key, boolean value) {
unparcel();
mMap.put(key, value);
}
void putByte(@Nullable String key, byte value) {
unparcel();
mMap.put(key, value);
}
void putChar(@Nullable String key, char value) {
unparcel();
mMap.put(key, value);
}
···
}

put 方法內部就使用到了數組的緩存和複用機制

	@Override
public V put(K key, V value) {
···
if (osize >= mHashes.length) {
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//嘗試通過數組複用機制來初始化 mHashes 和 mArray
allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
//嘗試回收 ohashes 和 oarray
freeArrays(ohashes, oarray, osize);
}
···
return null;
}

1、緩存數組

實現數組緩存邏輯對應的是 freeArrays 方法,該方法就用於緩存 mHashes 和 mArray。每當 ArrayMap 完成數組擴容後就會調用此方法對擴容前的數組進行緩存,但也不是所有數組都會進行緩存,而是有著數組長度和緩存總數這兩方面的限制

首先,ArrayMap 包含了多個全局的靜態變量和靜態常量用於控制及實現數組緩存。從 freeArrays 方法可以看出來,if 和 else 語句塊的邏輯是基本完全一樣的,其區別只在於觸發緩存的條件和使用的緩存池不一樣

例如,如果 hashes 的數組長度是 BASE_SIZE * 2,且當前緩存總數沒有超出 CACHE_SIZE,那麼緩存的數組就是保存在 mTwiceBaseCache 所構造的的單向鏈表中。mTwiceBaseCache 採用單向鏈表的結構來串聯多個數組,要緩存的 mArray 的第一個數組元素值會先指向 mTwiceBaseCache,第二個數組元素值會指向 mHashes,之後 mArray 會成為單向鏈表的新的頭結點,即 mArray 成為了新的 mTwiceBaseCache。在這種緩存機制下,最終 mTwiceBaseCache 指向的其實是本次緩存的 mArray,mArray 的第一個元素值指向的又是上一次緩存的 mArray,第二個元素值指向的是本次緩存的 mHashes,從而形成了一個單向鏈表結構

	//用於緩存長度為 BASE_SIZE 的數組
static Object[] mBaseCache;
//mBaseCache 已緩存的數組個數
static int mBaseCacheSize;
//用於緩存長度為 BASE_SIZE * 2 的數組
static Object[] mTwiceBaseCache;
//mTwiceBaseCache 已緩存的數組個數
static int mTwiceBaseCacheSize;
private static final int BASE_SIZE = 4;
//mBaseCacheSize 和 mTwiceBaseCacheSize 的最大緩存個數
private static final int CACHE_SIZE = 10;
//用來當做同步鎖
private static final Object sBaseCacheLock = new Object();
private static final Object sTwiceBaseCacheLock = new Object();
//緩存 hashes 和 array
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) {
synchronized (sTwiceBaseCacheLock) {
if (mTwiceBaseCacheSize < CACHE_SIZE) {
//第一個元素指向 mTwiceBaseCache
array[0] = mTwiceBaseCache;
//第二個元素指向 hashes
array[1] = hashes;
for (int i=(size<<1)-1; i>=2; i--) {
//切除多餘引用,避免內存洩漏,有利於 GC
array[i] = null;
}
//array 成為單鏈表的頭結點
mTwiceBaseCache = array;
mTwiceBaseCacheSize++;
if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
+ " now have " + mTwiceBaseCacheSize + " entries");
}
}
} else if (hashes.length == BASE_SIZE) {
synchronized (sBaseCacheLock) {
if (mBaseCacheSize < CACHE_SIZE) {
array[0] = mBaseCache;
array[1] = hashes;
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
mBaseCache = array;
mBaseCacheSize++;
if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
+ " now have " + mBaseCacheSize + " entries");
}
}
}
}

2、複用數組

緩存數組的目的自然就是為了後續複用,數組的複用邏輯對應的是 allocArrays 方法,該方法用於為 mHashes 和 mArray 申請一個更大容量的數組空間,通過複用數組或者全新初始化來獲得

在進行數組緩存的時候會判斷數組長度,只有當長度是 BASE_SIZE*2 或 BASE_SIZE 時才會進行緩存,那麼自然只有當數組的目標長度 size 是這兩個值之一才會符合複用條件了。allocArrays 的取緩存邏輯也很簡單,只需要取出單向鏈表的頭結點賦值給 mHashes 和 mArray,同時使鏈表的第二個結點成為新的頭結點即可。如果不符合複用條件,那麼就還是會進行全新初始化

	//用於緩存長度為 BASE_SIZE 的數組
static Object[] mBaseCache;
//mBaseCache 已緩存的數組個數
static int mBaseCacheSize;
//用於緩存長度為 BASE_SIZE * 2 的數組
static Object[] mTwiceBaseCache;
//mTwiceBaseCache 已緩存的數組個數
static int mTwiceBaseCacheSize;
private static final int BASE_SIZE = 4;
//mBaseCacheSize 和 mTwiceBaseCacheSize 的最大緩存個數
private static final int CACHE_SIZE = 10;
//用來當做同步鎖
private static final Object sBaseCacheLock = new Object();
private static final Object sTwiceBaseCacheLock = new Object();
private void allocArrays(final int size) {
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
if (size == (BASE_SIZE*2)) {
synchronized (sTwiceBaseCacheLock) {
if (mTwiceBaseCache != null) {
final Object[] array = mTwiceBaseCache;
mArray = array;
try {
//指向頭結點的下一個結點,即原先的第二個結點將成為鏈表新的頭結點
mTwiceBaseCache = (Object[]) array[0];
mHashes = (int[]) array[1];
if (mHashes != null) {
//符合複用條件,切除多餘引用
array[0] = array[1] = null;
mTwiceBaseCacheSize--;
if (DEBUG) {
Log.d(TAG, "Retrieving 2x cache " + mHashes
+ " now have " + mTwiceBaseCacheSize + " entries");
}
return;
}
} catch (ClassCastException e) {
}
// Whoops!  Someone trampled the array (probably due to not protecting
// their access with a lock).  Our cache is corrupt; report and give up.
Slog.wtf(TAG, "Found corrupt ArrayMap cache: [0]=" + array[0]
+ " [1]=" + array[1]);
//會執行到這裡,說明緩存機制發現問題,則棄用之前的所有緩存
mTwiceBaseCache = null;
mTwiceBaseCacheSize = 0;
}
}
} else if (size == BASE_SIZE) {
synchronized (sBaseCacheLock) {
if (mBaseCache != null) {
final Object[] array = mBaseCache;
mArray = array;
try {
mBaseCache = (Object[]) array[0];
mHashes = (int[]) array[1];
if (mHashes != null) {
array[0] = array[1] = null;
mBaseCacheSize--;
if (DEBUG) {
Log.d(TAG, "Retrieving 1x cache " + mHashes
+ " now have " + mBaseCacheSize + " entries");
}
return;
}
} catch (ClassCastException e) {
}
// Whoops!  Someone trampled the array (probably due to not protecting
// their access with a lock).  Our cache is corrupt; report and give up.
Slog.wtf(TAG, "Found corrupt ArrayMap cache: [0]=" + array[0]
+ " [1]=" + array[1]);
mBaseCache = null;
mBaseCacheSize = 0;
}
}
}
mHashes = new int[size];
mArray = new Object[size<<1];
}

3、總結

上文說了,只有長度為 BASE_SIZE 或者 BASE_SIZE*2 的數組才會被緩存複用,而 mHashes 和 mArray 的擴容操作也會盡量使得擴容後的數組長度就是這兩個值之一,這可以從 put 方法計算擴容後容量的算法看出來

	@Override
public V put(K key, V value) {
final int osize = mSize;
final int hash;
···
if (osize >= mHashes.length) {
//計算數組擴容後的大小
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
···
freeArrays(ohashes, oarray, osize);
}
···
return null;
}

所以說,雖然 ArrayMap 的構造函數中並沒有直接將 BASE_SIZE 作為數組的默認長度,但是在擴容過程中會盡量往 BASE_SIZE 和 BASE_SIZE * 2 這兩個值靠攏,這就有利於儘量實現數組複用

此外,ArrayMap 的擴容操作,即申請內存操作也顯得比較剋制,在數組長度超出 BASE_SIZE * 2 後,只是擴容到當前的 1.5 倍,且也只在 mHashes 容量不足時才會觸發擴容機制。而 HashMap 在達到負載因子設定的比例後(此時數組未滿)就會觸發擴容機制,而且也是按照擴充到兩倍容量的方式進行擴容。所以說,ArrayMap 對於內存空間的利用效率會更高一些

5、優劣勢總結

ArrayMap 的適用場景可以從它的緩存機制就看出來一些,它會緩存容量為 4 或者 8 的數組並進行後續複用,而這兩個值可以說都是比較小的。對於 Android 開發來說,系統對於內存比較敏感,需要存儲鍵值對時面對的往往是使用頻率高但數據量小的場景。例如我們在跳轉到 Activity 時往往是通過 Bundle 來存儲跳轉參數,但數據量一般都很少,所以 Bundle 內部就使用到了 ArrayMap 來存儲鍵值對。ArrayMap 在內存申請時相比 HashMap 會比較剋制,鍵值對會以更加緊密的數據結構存儲在一起,對內存利用率會更高一些

而相對的,ArrayMap 的這種存儲結構也導致了其查找效率相比 HashMap 要低很多。在數據量大時,ArrayMap 可能需要通過多次二分查找才能定位到元素,而 HashMap 在沒有哈希衝突的情況下只需要經過一次哈希計算即可定位到元素,即使有哈希衝突也只需要遍歷發生衝突的部分元素即可

所以說, ArrayMap 適用於數據量較小的場景,此時查找效率也不會受多大影響,而內存利用率能夠顯著提高。如果數據量較大,那就可以考慮使用 HashMap 來替代了

6、關聯類

系統還包含了一個用於存儲不重複元素值的集合框架類:ArraySet,從名字就可以猜到 ArraySet 實現了 Set 接口。ArraySet 內部一樣使用兩個數組來存儲 hash 和 value,即 mHashes 和 mArray,在實現邏輯上基本和 ArrayMap 一樣,只是會在存值的時候判斷 value 是否重複而已,這裡就不再贅述了

相關文章

MySQL架構演進從主從複製到分庫分表

Android中通知欄的用法

three.js實現3D動態文字

52條SQL語句性能優化策略,建議收藏