1、簡述

• 我們都知道 HashMap，它屬于 java.util 包下，但是很多人可能對 ArrayMap 并不是很熟悉，通俗來說 ArrayMap 屬于 android.util 包下，是用于 Android 平臺某些情況替換 HashMap 的數據結構。
• 使用限定：minSdkVersion 必須大于等于 19（Android 4.4）。

2、歸納

• 實現了 Map 接口。
• 底層采用兩個一維數組，第一個數組是整型數組，且有序，存儲 key 對應的 hash 值，第二個數組存儲 key 和 value，其中 key 在 index*2 位置，value 在 index*2+1 位置。
• 每次插入時，根據 key 的哈希值，利用二分查找，去尋找 key 在整型數組中的下標位置，如果出現了 hash 沖突，則從需要從目標點向兩頭遍歷，找到正確的 index。
• 擴容機制，如果容量小于4，則擴容到4，如果容量大于等于4小于8，則擴容到8，如果容量大于等于8，則擴容到當前容量加當前容量的一半。
• 縮容機制，如果存儲 hash 值的數組長度大于等于8，且集合長度少于當前空間的1/3，則進行收縮操作，避免浪費空間。
• ArrayMap 的操作單線安全，多線程不安全。
• 1000 以內元素性能 ArrayMap 相對 HashMap 更高。

3、分析

3.1、成員變量

public final class ArrayMap<K, V> implements Map<K, V> {// 是否是 DEBUG 模式private static final boolean DEBUG = false;// 設置 TAGprivate static final String TAG = "ArrayMap";private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;// 擴容默認的 size， 4是相對效率較高的大小private static final int BASE_SIZE = 4;// 數組緩存中的最大條目數@UnsupportedAppUsage(maxTargetSdk = 28)private static final int CACHE_SIZE = 10;// 指示容器不可變的特殊哈希數組值@UnsupportedAppUsage(maxTargetSdk = 28)static final int[] EMPTY_IMMUTABLE_INTS = new int[0];@UnsupportedAppUsage(maxTargetSdk = 28)public static final android.util.ArrayMap EMPTY = new android.util.ArrayMap<>(-1);@UnsupportedAppUsage(maxTargetSdk = 28)static Object[] mBaseCache;@UnsupportedAppUsage(maxTargetSdk = 28)static int mBaseCacheSize;@UnsupportedAppUsage(maxTargetSdk = 28)static Object[] mTwiceBaseCache;@UnsupportedAppUsage(maxTargetSdk = 28)static int mTwiceBaseCacheSize;private static final Object sBaseCacheLock = new Object();private static final Object sTwiceBaseCacheLock = new Object();// 是否利用 System.identityHashCode(key) 獲取唯一 hashCodeprivate final boolean mIdentityHashCode;// 保存每個元素的 hash，長度為容量大小// mHashes 是有序的，按照元素的 hash 值由小到大排序，hash 值相同的元素，先插入的排在前面// 由于 mHashes 是有序的，所以使用二分法查找元素的位置，時間復雜度為 O(logn)@UnsupportedAppUsage(maxTargetSdk = 28)int[] mHashes;// 保存鍵值對，長度為容量的兩倍// 根據 key 的 hash 在 mHashes 的存放位置 index，可以確定鍵值對在 mArray 的存放位置// key 存放在 index << 1 處，value 存放在 (index << 1) + 1 處@UnsupportedAppUsage(maxTargetSdk = 28)Object[] mArray;// 當前鍵值對數量@UnsupportedAppUsage(maxTargetSdk = 28)int mSize;private MapCollections<K, V> mCollections;... }

3.2、構造函數

public final class ArrayMap<K, V> implements Map<K, V> {.../*** 無參構造函數*/public ArrayMap() {this(0, false);}/*** 有參構造函數** @param capacity 容量*/public ArrayMap(int capacity) {this(capacity, false);}/*** 有參構造函數** @param capacity 容量* @param identityHashCode 是否使用 System.identityHashCode(key) 獲取 hashcode 值*/public ArrayMap(int capacity, boolean identityHashCode) {mIdentityHashCode = identityHashCode;if (capacity < 0) {// 容量小于 0，創建一個不可變的 ArrayMapmHashes = EMPTY_IMMUTABLE_INTS;mArray = EmptyArray.OBJECT;} else if (capacity == 0) {// 容量等于 0，創建一個空 ArrayMapmHashes = EmptyArray.INT;mArray = EmptyArray.OBJECT;} else {// 容量大于 0，根據指定容量初始化 mHashes 和 mArray 數組// 如果容量是 4 或 8 的話，會查看之前是否有緩存的數組，有就使用緩存allocArrays(capacity);}mSize = 0;}/*** 有參構造函數** @param map ArrayMap 集合*/public ArrayMap(android.util.ArrayMap<K, V> map) {this();if (map != null) {putAll(map);}}... }

3.3、增操作

public final class ArrayMap<K, V> implements Map<K, V> {.../*** 添加元素** @param key 鍵* @param value 值* @return 如果 key 存在，則返回 oldValue*/public V put(K key, V value) {// key 的 hash 值final int hash;// 下標int index;// 如果 key 為 null，則 hash 值為0if (key == null) {hash = 0;// 尋找 null 的下標index = indexOfNull();} else {// 根據 mIdentityHashCode 取到 hash 值hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();// 根據 hash 值和 key 找到合適的 indexindex = indexOf(key, hash);}// 如果 index>=0，說明是替換（改）操作if (index >= 0) {// 只需要更新 value 不需要更新 key，因為 key 已經存在index = (index << 1) + 1;// 返回舊值final V old = (V) mArray[index];mArray[index] = value;return old;}// index<0，說明是插入操作。對其取反，得到應該插入的下標index = ~index;// 如果需要擴容if (mSize >= mHashes.length) {// 如果容量大于8，則擴容一半// 否則容量大于4，則擴容到8// 否則擴容到4final int n = mSize >= (BASE_SIZE * 2) ? (mSize + (mSize >> 1)): (mSize >= BASE_SIZE ? (BASE_SIZE * 2) : BASE_SIZE);// 臨時數組final int[] ohashes = mHashes;final Object[] oarray = mArray;// 分配空間完成擴容allocArrays(n);// 復制臨時數組中的數組進新數組if (mHashes.length > 0) {if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);System.arraycopy(oarray, 0, mArray, 0, oarray.length);}// 釋放臨時數組空間freeArrays(ohashes, oarray, mSize);}// 如果 index 在中間，則需要移動數組，騰出中間的位置if (index < mSize) {if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize - index)+ " to " + (index + 1));System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);}// hash 數組，就按照下標存哈希值mHashes[index] = hash;// array 數組，根據下標，乘以2存 key，乘以2+1存 valuemArray[index << 1] = key;mArray[(index << 1) + 1] = value;mSize++;// 修改 sizereturn null;}/*** 將一個 ArrayMap 集合添加進來** @param array ArrayMap 集合*/public void putAll(ArrayMap<? extends K, ? extends V> array) {final int N = array.mSize;// 確?？臻g足夠存放ensureCapacity(mSize + N);// 如果當前是空集合if (mSize == 0) {if (N > 0) {// 則直接復制覆蓋數組內容即可。System.arraycopy(array.mHashes, 0, mHashes, 0, N);System.arraycopy(array.mArray, 0, mArray, 0, N << 1);mSize = N;}} else {// 否則需要一個一個執行插入 put 操作for (int i = 0; i < N; i++) {put(array.keyAt(i), array.valueAt(i));}}}/*** 將一個 Map 集合添加進來** @param map Map 集合*/@Overridepublic void putAll(Map<? extends K, ? extends V> map) {// 確?？臻g容量足夠ensureCapacity(mSize + map.size());for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {// 分別調用單個增方法 addput(entry.getKey(), entry.getValue());}}/*** 擴容操作** @param size 容量大小*/private void allocArrays(final int size) {// 數量<0，構建一個不可變的 ArrayMapif (mHashes == EMPTY_IMMUTABLE_INTS) {throw new UnsupportedOperationException("ArrayMap is immutable");}// 擴容數量是8if (size == (BASE_SIZE * 2)) {synchronized (ArrayMap.class) {// 查看之前是否有緩存的容量為8的 int[] 數組和容量為16的 object[] 數組// 如果有，復用給 mArray mHashesif (mTwiceBaseCache != null) {final Object[] array = mTwiceBaseCache;mArray = array;mTwiceBaseCache = (Object[]) array[0];mHashes = (int[]) array[1];array[0] = array[1] = null;mTwiceBaseCacheSize--;if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes+ " now have " + mTwiceBaseCacheSize + " entries");return;}}} else if (size == BASE_SIZE) {// 擴容數量是4synchronized (ArrayMap.class) {// 查看之前是否有緩存的 容量為4的 int[] 數組和容量為8的 object[] 數組//如果有，復用給 mArray mHashesif (mBaseCache != null) {final Object[] array = mBaseCache;mArray = array;mBaseCache = (Object[]) array[0];mHashes = (int[]) array[1];array[0] = array[1] = null;mBaseCacheSize--;if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes+ " now have " + mBaseCacheSize + " entries");return;}}}// 構建 mHashes 和 mArray，mArray 是 mHashes 的兩倍。因為它既要存 key 還要存 valuemHashes = new int[size];mArray = new Object[size << 1];}/*** 確?？臻g足夠存放 minimumCapacity 個數據** @param minimumCapacity 最小容量*/public void ensureCapacity(int minimumCapacity) {// 如果不夠擴容if (mHashes.length < minimumCapacity) {// 暫存當前的hash array，后面復制需要final int[] ohashes = mHashes;final Object[] oarray = mArray;// 擴容空間（開頭講過這個函數）allocArrays(minimumCapacity);if (mSize > 0) {// 如果原集合不為空，復制原數據到新數組中System.arraycopy(ohashes, 0, mHashes, 0, mSize);System.arraycopy(oarray, 0, mArray, 0, mSize << 1);}// 釋放回收臨時暫存數組空間freeArrays(ohashes, oarray, mSize);}}/*** 釋放回收臨時暫存數組空間** @param hashes 數組* @param array 數組* @param size 長度*/private static void freeArrays(final int[] hashes, final Object[] array, final int size) {// 如果容量是8， 則將 hashes 和array 緩存起來，以便下次使用if (hashes.length == (BASE_SIZE * 2)) {synchronized (ArrayMap.class) {if (mTwiceBaseCacheSize < CACHE_SIZE) {// 0存，前一個緩存的 cachearray[0] = mTwiceBaseCache;// 1存 int[] 數組array[1] = hashes;//2+元素置空，以便 GCfor (int i = (size << 1) - 1; i >= 2; i--) {array[i] = null;}// 更新緩存引用為 arraymTwiceBaseCache = array;// 增加緩存過的 Array 的數量mTwiceBaseCacheSize++;if (DEBUG) Log.d(TAG, "Storing 2x cache " + array+ " now have " + mTwiceBaseCacheSize + " entries");}}// 相同邏輯，只不過緩存的是 int[] 容量為4的數組} else if (hashes.length == BASE_SIZE) {synchronized (ArrayMap.class) {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");}}}}/*** 返回 key 為 null 的下標 index** @return 返回 key 為 null 的下標 index*/int indexOfNull() {// N 為當前集合 size final int N = mSize;// 如果當前集合是空的，返回~0if (N == 0) {//return ~0;}// 根據 hash 值=0，通過二分查找，查找到目標 indexint index = ContainerHelpers.binarySearch(mHashes, N, 0);// 如果 index<0，則 hash 值=0之前沒有存儲過數據if (index < 0) {return index;}// 如果 index>=0，說明該 hash 值，之前存儲過數據，找到對應的 key，比對 key 是否等于 null。相等的話，返回 index。說明要替換// 關于 array 中對應數據的位置，是 index*2=key，index*2+1=valueif (null == mArray[index << 1]) {return index;}// 以下兩個 for 循環是在出現 hash 沖突的情況下，找到正確的 index 的過程：// 從 index+1，遍歷到數組末尾，找到 hash 值相等，且 key 相等的位置，返回int end;for (end = index + 1; end < N && mHashes[end] == 0; end++) {if (null == mArray[end << 1]) return end;}// 從 index-1，遍歷到數組頭，找到 hash 值相等，且 key 相等的位置，返回for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {if (null == mArray[i << 1]) return i;}// key 沒有找到，返回一個負數。代表應該插入的位置return ~end;}/*** 根據 key 和 key 的 hash 值，返回 index** @param key 鍵* @param hash hash 值* @return 返回數組下標*/int indexOf(Object key, int hash) {// N 為當前集合 size final int N = mSize;// 如果當前集合是空的，返回~0if (N == 0) {return ~0;}// 根據 hash 值，通過二分查找，查找到目標 indexint index = ContainerHelpers.binarySearch(mHashes, N, hash);// 如果 index<0，說明該 hash 值之前沒有存儲過數據if (index < 0) {return index;}// 如果 index>=0，說明該 hash 值，之前存儲過數據，找到對應的 key，比對 key 是否相等。相等的話，返回 index。說明要替換。if (key.equals(mArray[index << 1])) {return index;}// 以下兩個 for 循環是在出現 hash 沖突的情況下，找到正確的 index 的過程：// 從 index+1，遍歷到數組末尾，找到 hash 值相等，且 key 相等的位置，返回int end;for (end = index + 1; end < N && mHashes[end] == hash; end++) {if (key.equals(mArray[end << 1])) return end;}// 從 index-1，遍歷到數組頭，找到 hash 值相等，且 key 相等的位置，返回for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {if (key.equals(mArray[i << 1])) return i;}// key 沒有找到，返回一個負數。代表應該插入的位置return ~end;}... }

3.4、刪操作

public final class ArrayMap<K, V> implements Map<K, V> {.../*** 根據 key 刪除元素** @param key 鍵* @return 返回刪除的元素，如若不存在則返回 null*/public V remove(Object key) {// 根據 key，找到下標final int index = indexOfKey(key);if (index >= 0) {// 如果 index>=0，說明 key 有對應的元素存在，則去根據下標刪除return removeAt(index);}// 否則返回 nullreturn null;}/*** 根據下標刪除元素** @param index 數組下標* @return 返回刪除后的元素*/public V removeAt(int index) {// 根據 index，得到 valuefinal Object old = mArray[(index << 1) + 1];// 如果之前的集合長度小于等于1，則執行過刪除操作后，集合現在就是空的了if (mSize <= 1) {// Now empty.if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");// 釋放回收空間freeArrays(mHashes, mArray, mSize);// 置空mHashes = EmptyArray.INT;mArray = EmptyArray.OBJECT;mSize = 0;} else {// 根據元素數量和集合占用的空間情況，判斷是否要執行收縮操作// 如果 mHashes 長度大于8，且 集合長度小于當前空間的1/3，則執行一個 shrunk，收縮操作，避免空間的浪費if (mHashes.length > (BASE_SIZE * 2) && mSize < mHashes.length / 3) {// 如果當前集合長度大于8，則n為當前集合長度的1.5倍，否則n為8// n 為收縮后的 mHashes 長度final int n = mSize > (BASE_SIZE * 2) ? (mSize + (mSize >> 1)) : (BASE_SIZE * 2);if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);// 分配新的更小的空間（收縮操作）final int[] ohashes = mHashes;final Object[] oarray = mArray;allocArrays(n);// 刪掉一個元素，所以修改集合元素數量mSize--;// 因為執行了收縮操作，所以要將老數據復制到新數組中if (index > 0) {if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");System.arraycopy(ohashes, 0, mHashes, 0, index);System.arraycopy(oarray, 0, mArray, 0, index << 1);}// 在復制的過程中，排除不復制當前要刪除的元素即可if (index < mSize) {if (DEBUG) Log.d(TAG, "remove: copy from " + (index + 1) + "-" + mSize+ " to " + index);System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,(mSize - index) << 1);}} else {// 不需要收縮// 修改集合長度mSize--;// 類似 ArrayList，用復制操作去覆蓋元素達到刪除的目的if (index < mSize) {if (DEBUG) Log.d(TAG, "remove: move " + (index + 1) + "-" + mSize+ " to " + index);System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,(mSize - index) << 1);}// 記得置空，以防內存泄漏mArray[mSize << 1] = null;mArray[(mSize << 1) + 1] = null;}}// 返回刪除的值return (V) old;}/*** 刪除 Collection 集合中，所有出現的 key** @param collection Collection 集合* @return true 代表刪除成功，false 代表刪除失敗*/public boolean removeAll(Collection<?> collection) {return MapCollections.removeAllHelper(this, collection);}... }

• MapCollections.removeAllHelper() 方法

abstract class MapCollections<K, V> {.../*** 遍歷 Collection，調用 Map.remove(key) 去刪除元素** @param map* @param collection* @param <K>* @param <V>* @return true 刪除成功，false 刪除失敗*/public static <K, V> boolean removeAllHelper(Map<K, V> map, Collection<?> collection) {int oldSize = map.size();Iterator<?> it = collection.iterator();while (it.hasNext()) {map.remove(it.next());}// 如果元素不等，說明成功刪除元素return oldSize != map.size();}... }

3.5、查操作

public final class ArrayMap<K, V> implements Map<K, V> {.../*** 根據 key 獲取 值** @param key 鍵* @return 返回值*/public V get(Object key) {// 根據 key 去得到 indexfinal int index = indexOfKey(key);// 根據 index*2+1 得到 valuereturn index >= 0 ? (V) mArray[(index << 1) + 1] : null;}/*** 根據 key 獲取數組下標** @param key 鍵* @return 返回數組下標*/public int indexOfKey(Object key) {// 判斷 key 是否是 null，并去查詢 key 對應的 indexreturn key == null ? indexOfNull(): indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());}... }

總結

以上是生活随笔為你收集整理的ArrayMap 源码解析的全部內容，希望文章能夠幫你解決所遇到的問題。

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