想看我更多文章:【張旭童的博客】http://blog.csdn.net/zxt0601
想來gayhub和我gaygayup:【mcxtzhang的Github主頁】https://github.com/mcxtzhang

1 概述

在上文中，我們已經(jīng)聊過了HashMap和LinkedHashMap.所以如果沒看過上文，請(qǐng)先閱讀面試必備：HashMap源碼解析（JDK8） ,面試必備：LinkedHashMap源碼解析（JDK8
那么今天換點(diǎn)口味，不看JDK了，我們看看android sdk的源碼。

本文將從幾個(gè)常用方法下手，來閱讀ArrayMap的源碼。
按照從構(gòu)造方法->常用API（增、刪、改、查）的順序來閱讀源碼，并會(huì)講解閱讀方法中涉及的一些變量的意義。了解ArrayMap的特點(diǎn)、適用場景。

如果本文中有不正確的結(jié)論、說法，請(qǐng)大家提出和我討論，共同進(jìn)步，謝謝。

2 概要

概括的說，ArrayMap 實(shí)現(xiàn)了implements Map<K, V>接口，所以它也是一個(gè)關(guān)聯(lián)數(shù)組、哈希表。存儲(chǔ)以key->value 結(jié)構(gòu)形式的數(shù)據(jù)。它也是線程不安全的，允許key為null,value為null。

它相比HashMap，空間效率更高。

它的內(nèi)部實(shí)現(xiàn)是基于兩個(gè)數(shù)組。
一個(gè)int[]數(shù)組，用于保存每個(gè)item的hashCode.
一個(gè)Object[]數(shù)組，保存key/value鍵值對(duì)。容量是上一個(gè)數(shù)組的兩倍。
它可以避免在將數(shù)據(jù)插入Map中時(shí)額外的空間消耗（對(duì)比HashMap）。

而且它擴(kuò)容的更合適，擴(kuò)容時(shí)只需要數(shù)組拷貝工作，不需要重建哈希表。

和HashMap相比，它不僅有擴(kuò)容功能，在刪除時(shí)，如果集合剩余元素少于一定閾值，還有收縮（shrunk）功能。減少空間占用。

對(duì)于哈希沖突的解決，查看源碼可以得知采用的是開放地址法。

但是它不適合大容量的數(shù)據(jù)存儲(chǔ)。存儲(chǔ)大量數(shù)據(jù)時(shí)，它的性能將退化至少50%。
比傳統(tǒng)的HashMap時(shí)間效率低。
因?yàn)槠鋾?huì)對(duì)key從小到大排序，使用二分法查詢key對(duì)應(yīng)在數(shù)組中的下標(biāo)。
在添加、刪除、查找數(shù)據(jù)的時(shí)候都是先使用二分查找法得到相應(yīng)的index，然后通過index來進(jìn)行添加、查找、刪除等操作。

所以其是按照key的大小排序存儲(chǔ)的。

適用場景：

• 數(shù)據(jù)量不大
• 空間比時(shí)間重要
• 需要使用Map
• 在Android平臺(tái)，相對(duì)來說，內(nèi)存容量更寶貴。而且數(shù)據(jù)量不大。所以當(dāng)需要使用key是Object類型的Map時(shí)，可以考慮使用ArrayMap來替換HashMap

示例代碼：

Map<String, String> map = new ArrayMap<>();map.put("1","1");map.put(null,"2");map.put("3",null);map.put("6",null);map.put("5",null);map.put("4",null);Log.d("TAG", "onCreate() called with: map = [" + map + "]");

輸出：

onCreate() called with: map = [{null=2, 1=1, 3=null, 4=null, 5=null, 6=null}]

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

//擴(kuò)容默認(rèn)的size， 4是相對(duì)效率較高的大小private static final int BASE_SIZE = 4;//表示集合是不可變的static final int[] EMPTY_IMMUTABLE_INTS = new int[0];//是否利用System.identityHashCode(key) 獲取唯一HashCode模式。 final boolean mIdentityHashCode;//保存hash值的數(shù)組int[] mHashes;//保存key/value的數(shù)組。Object[] mArray;//容量int mSize;//創(chuàng)建一個(gè)空的ArrayMap，默認(rèn)容量是0.當(dāng)有Item被添加進(jìn)來，會(huì)自動(dòng)擴(kuò)容public ArrayMap() {this(0, false);}//創(chuàng)建一個(gè)指定容量的ArrayMappublic ArrayMap(int capacity) {this(capacity, false);}//指定容量和identityHashCodepublic ArrayMap(int capacity, boolean identityHashCode) {mIdentityHashCode = identityHashCode;//數(shù)量< 0，構(gòu)建一個(gè)不可變的ArrayMapif (capacity < 0) {mHashes = EMPTY_IMMUTABLE_INTS;mArray = EmptyArray.OBJECT;//數(shù)量= 0，構(gòu)建空的mHashes mArray} else if (capacity == 0) {mHashes = EmptyArray.INT;mArray = EmptyArray.OBJECT;} else {//數(shù)量>0,分配空間初始化數(shù)組allocArrays(capacity);}mSize = 0;}//擴(kuò)容private void allocArrays(final int size) {//數(shù)量< 0，構(gòu)建一個(gè)不可變的ArrayMapif (mHashes == EMPTY_IMMUTABLE_INTS) {throw new UnsupportedOperationException("ArrayMap is immutable");}//擴(kuò)容數(shù)量是 8if (size == (BASE_SIZE*2)) {synchronized (ArrayMap.class) {//查看之前是否有緩存的 容量為8的int[]數(shù)組和容量為16的object[]數(shù)組 //如果有，復(fù)用給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) {//擴(kuò)容數(shù)量是4synchronized (ArrayMap.class) {//查看之前是否有緩存的 容量為4的int[]數(shù)組和容量為8的object[]數(shù)組 //如果有，復(fù)用給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;}}}//構(gòu)建mHashes和mArray，mArray是mHashes的兩倍。因?yàn)樗纫鎘ey還要存value。mHashes = new int[size];mArray = new Object[size<<1];}//利用另一個(gè)map構(gòu)建ArrayMappublic ArrayMap(ArrayMap<K, V> map) {this();if (map != null) {putAll(map);}}//批量put方法：public void putAll(ArrayMap<? extends K, ? extends V> array) {final int N = array.mSize;//確?？臻g足夠存放ensureCapacity(mSize + N);//如果當(dāng)前是空集合，if (mSize == 0) {if (N > 0) {//則直接復(fù)制覆蓋數(shù)組內(nèi)容即可。System.arraycopy(array.mHashes, 0, mHashes, 0, N);System.arraycopy(array.mArray, 0, mArray, 0, N<<1);mSize = N;}} else {//否則需要一個(gè)一個(gè)執(zhí)行插入put操作for (int i=0; i<N; i++) {put(array.keyAt(i), array.valueAt(i));}}}//確?？臻g足夠存放 minimumCapacity 個(gè)數(shù)據(jù)public void ensureCapacity(int minimumCapacity) {//如果不夠擴(kuò)容if (mHashes.length < minimumCapacity) {//暫存當(dāng)前的hash array。后面復(fù)制需要final int[] ohashes = mHashes;final Object[] oarray = mArray;//擴(kuò)容空間（開頭講過這個(gè)函數(shù)）allocArrays(minimumCapacity);if (mSize > 0) {//如果原集合不為空，復(fù)制原數(shù)據(jù)到新數(shù)組中System.arraycopy(ohashes, 0, mHashes, 0, mSize);System.arraycopy(oarray, 0, mArray, 0, mSize<<1);}//釋放回收臨時(shí)暫存數(shù)組空間freeArrays(ohashes, oarray, mSize);}}//釋放回收臨時(shí)暫存數(shù)組空間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存，前一個(gè)緩存的cachearray[0] = mTwiceBaseCache;//1 存 int[]數(shù)組array[1] = hashes;//2+ 元素置空 以便GCfor (int i=(size<<1)-1; i>=2; i--) {array[i] = null;}//更新緩存引用為arraymTwiceBaseCache = array;//增加緩存過的Array的數(shù)量mTwiceBaseCacheSize++;if (DEBUG) Log.d(TAG, "Storing 2x cache " + array+ " now have " + mTwiceBaseCacheSize + " entries");}}//相同邏輯，只不過緩存的是int[] 容量為4的數(shù)組 } 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");}}}}

小結(jié)：
* 擴(kuò)容時(shí)，會(huì)查看之前是否有緩存的 int[]數(shù)組和object[]數(shù)組
* 如果有，復(fù)用給mArray mHashes

4 增 、改

4.1 單個(gè)增改 put(K key, V value)

//如果key存在，則返回oldValuepublic V put(K key, V value) {//key的hash值final int hash;//下標(biāo)int index;// 如果key為null，則hash值為0.if (key == null) {hash = 0;//尋找null的下標(biāo)index = indexOfNull();} else {//根據(jù)mIdentityHashCode 取到 hash值hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();//根據(jù)hash值和key 找到合適的indexindex = indexOf(key, hash);}//如果index>=0,說明是替換（改）操作if (index >= 0) {//只需要更新value 不需要更新key。因?yàn)閗ey已經(jīng)存在index = (index<<1) + 1;//返回舊值final V old = (V)mArray[index];mArray[index] = value;return old;}//index<0,說明是插入操作。 對(duì)其取反，得到應(yīng)該插入的下標(biāo)index = ~index;//如果需要擴(kuò)容if (mSize >= mHashes.length) {//如果容量大于8，則擴(kuò)容一半。//否則容量大于4，則擴(kuò)容到8.//否則擴(kuò)容到4final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)): (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);//臨時(shí)數(shù)組final int[] ohashes = mHashes;final Object[] oarray = mArray;//分配空間完成擴(kuò)容allocArrays(n);//復(fù)制臨時(shí)數(shù)組中的數(shù)組進(jìn)新數(shù)組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);}//釋放臨時(shí)數(shù)組空間freeArrays(ohashes, oarray, mSize);}//如果index在中間，則需要移動(dòng)數(shù)組，騰出中間的位置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數(shù)組，就按照下標(biāo)存哈希值mHashes[index] = hash;//array數(shù)組，根據(jù)下標(biāo)，乘以2存key，乘以2+1 存valuemArray[index<<1] = key;mArray[(index<<1)+1] = value;mSize++;//修改sizereturn null;}//返回key為null的 下標(biāo)indexint indexOfNull() {//N為當(dāng)前集合size final int N = mSize;//如果當(dāng)前集合是空的，返回~0if (N == 0) {//return ~0;}//根據(jù)hash值=0，通過二分查找，查找到目標(biāo)indexint index = ContainerHelpers.binarySearch(mHashes, N, 0);//如果index《0，則hash值=0之前沒有存儲(chǔ)過數(shù)據(jù)if (index < 0) {return index;}//如果index>=0,說明該hash值，之前存儲(chǔ)過數(shù)據(jù)，找到對(duì)應(yīng)的key，比對(duì)key是否等于null。相等的話，返回index。說明要替換。 //關(guān)于array中對(duì)應(yīng)數(shù)據(jù)的位置，是index*2 = key ,index*2+1 = value.if (null == mArray[index<<1]) {return index;}//以下兩個(gè)for循環(huán)是在出現(xiàn)hash沖突的情況下，找到正確的index的過程：//從index+1,遍歷到數(shù)組末尾，找到hash值相等，且key相等的位置，返回int end;for (end = index + 1; end < N && mHashes[end] == 0; end++) {if (null == mArray[end << 1]) return end;}//從index-1,遍歷到數(shù)組頭，找到hash值相等，且key相等的位置，返回for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {if (null == mArray[i << 1]) return i;}// key沒有找到，返回一個(gè)負(fù)數(shù)。代表應(yīng)該插入的位置return ~end;}//根據(jù)key和key的hash值，返回indexint indexOf(Object key, int hash) {//N為當(dāng)前集合size final int N = mSize;//如果當(dāng)前集合是空的，返回~0if (N == 0) {return ~0;}//根據(jù)hash值，通過二分查找，查找到目標(biāo)indexint index = ContainerHelpers.binarySearch(mHashes, N, hash);//如果index《0，說明該hash值之前沒有存儲(chǔ)過數(shù)據(jù)if (index < 0) {return index;}//如果index>=0,說明該hash值，之前存儲(chǔ)過數(shù)據(jù)，找到對(duì)應(yīng)的key，比對(duì)key是否相等。相等的話，返回index。說明要替換。if (key.equals(mArray[index<<1])) {return index;}//以下兩個(gè)for循環(huán)是在出現(xiàn)hash沖突的情況下，找到正確的index的過程：//從index+1,遍歷到數(shù)組末尾，找到hash值相等，且key相等的位置，返回int end;for (end = index + 1; end < N && mHashes[end] == hash; end++) {if (key.equals(mArray[end << 1])) return end;}//從index-1,遍歷到數(shù)組頭，找到hash值相等，且key相等的位置，返回for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {if (key.equals(mArray[i << 1])) return i;}// key沒有找到，返回一個(gè)負(fù)數(shù)。代表應(yīng)該插入的位置return ~end;}

4.2 批量增 putAll(Map

//批量增，接受更為廣泛的Map參數(shù)public void putAll(Map<? extends K, ? extends V> map) {//確?？臻g容量足夠ensureCapacity(mSize + map.size());for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {//分別調(diào)用單個(gè)增方法 addput(entry.getKey(), entry.getValue());}}

小結(jié)：
* 增的流程：1 先根據(jù)key得到hash值，2 根據(jù)hash值得到index 3 根據(jù)index正負(fù)，得知是插入還是替換 4 如果是替換直接替換值即可 5 如果是插入，則先判斷是否需要擴(kuò)容，并進(jìn)行擴(kuò)容 6 挪動(dòng)數(shù)組位置，插入元素（類似ArrayList）

• 插入允許key為null，value為null。
• 每次插入時(shí)，根據(jù)key的哈希值，利用二分查找，去尋找key在int[] mHashes數(shù)組中的下標(biāo)位置。
• 如果出現(xiàn)了hash沖突，則從需要從目標(biāo)點(diǎn)向兩頭遍歷，找到正確的index。
• 如果index>=0,說明之前已經(jīng)存在該key，需要替換（改）。
• 如果index<0,說明沒有找到。（也是二分法特性）對(duì)index去反，可以得到這個(gè)index應(yīng)該插入的位置。
• 根據(jù)key的hash值在mHashs中的index，如何得到key、value在mArray中的下標(biāo)位置呢？key的位置是index*2，value的位置是index*2+1,也就是說mArray是利用連續(xù)的兩位空間去存放key、value。
• 根據(jù)hash值的index計(jì)算，key、value的index也利用了位運(yùn)算。index<<1 和 (index<<1)+1

5 刪

5.1 單個(gè)刪

//如果對(duì)應(yīng)key有元素存在，返回value。否則返回nullpublic V remove(Object key) {//根據(jù)key，找到下標(biāo)final int index = indexOfKey(key);if (index >= 0) {//如果index>=0,說明key有對(duì)應(yīng)的元素存在，則去根據(jù)下標(biāo)刪除return removeAt(index);}//否則返回nullreturn null;} //根據(jù)下標(biāo)刪除元素public V removeAt(int index) {//根據(jù)index，得到valuefinal Object old = mArray[(index << 1) + 1];//如果之前的集合長度小于等于1，則執(zhí)行過刪除操作后，集合現(xiàn)在就是空的了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 {//根據(jù)元素?cái)?shù)量和集合占用的空間情況，判斷是否要執(zhí)行收縮操作//如果 mHashes長度大于8，且 集合長度 小于當(dāng)前空間的 1/3,則執(zhí)行一個(gè) shrunk，收縮操作，避免空間的浪費(fèi)if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {// Shrunk enough to reduce size of arrays. We dont allow it to// shrink smaller than (BASE_SIZE*2) to avoid flapping between// that and BASE_SIZE.//如果當(dāng)前集合長度大于8，則n為當(dāng)前集合長度的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);//刪掉一個(gè)元素，所以修改集合元素?cái)?shù)量mSize--;//因?yàn)閳?zhí)行了收縮操作，所以要將老數(shù)據(jù)復(fù)制到新數(shù)組中。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);}//在復(fù)制的過程中，排除不復(fù)制當(dāng)前要?jiǎng)h除的元素即可。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，用復(fù)制操作去覆蓋元素達(dá)到刪除的目的。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);}//記得置空，以防內(nèi)存泄漏mArray[mSize << 1] = null;mArray[(mSize << 1) + 1] = null;}}//返回刪除的值return (V)old;}

5.2 批量刪除

//從ArrayMap中，刪除Collection集合中，所有出現(xiàn)的key。//返回值代表是否成功刪除元素public boolean removeAll(Collection<?> collection) {return MapCollections.removeAllHelper(this, collection);}//MapCollections.removeAllHelper(this, collection);//遍歷Collection，調(diào)用Map.remove(key)去刪除元素;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();}

• 根據(jù)元素?cái)?shù)量和集合占用的空間情況，判斷是否要執(zhí)行收縮操作
• 類似ArrayList，用復(fù)制操作去覆蓋元素達(dá)到刪除的目的。

6 查

當(dāng)你想獲取某個(gè)value的時(shí)候，ArrayMap會(huì)計(jì)算輸入key轉(zhuǎn)換過后的hash值，然后對(duì)hash數(shù)組使用二分查找法尋找到對(duì)應(yīng)的index，然后我們可以通過這個(gè)index在另外一個(gè)數(shù)組中直接訪問到需要的鍵值對(duì)。如果在第二個(gè)數(shù)組鍵值對(duì)中的key和前面輸入的查詢key不一致，那么就認(rèn)為是發(fā)生了碰撞沖突。為了解決這個(gè)問題，我們會(huì)以該key為中心點(diǎn)，分別上下展開，逐個(gè)去對(duì)比查找，直到找到匹配的值。如下圖所示：

隨著數(shù)組中的對(duì)象越來越多，查找訪問單個(gè)對(duì)象的花費(fèi)也會(huì)跟著增長，這是在內(nèi)存占用與訪問時(shí)間之間做權(quán)衡交換。

6.1 單個(gè)查

public V get(Object key) {//根據(jù)key去得到indexfinal int index = indexOfKey(key);//根據(jù) index*2+1 得到valuereturn index >= 0 ? (V)mArray[(index<<1)+1] : null;}public int indexOfKey(Object key) {//判斷key是否是null，并去查詢key對(duì)應(yīng)的indexreturn key == null ? indexOfNull(): indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());}

總結(jié)

ArrayMap的實(shí)現(xiàn)細(xì)節(jié)很多地方和ArrayList很像，由于我們之前分析過面試必備：ArrayList源碼解析（JDK8）。所以對(duì)于用數(shù)組復(fù)制覆蓋去完成刪除等操作的細(xì)節(jié)，就比較容易理解了。

• 每次插入時(shí)，根據(jù)key的哈希值，利用二分查找，去尋找key在int[] mHashes數(shù)組中的下標(biāo)位置。
• 如果出現(xiàn)了hash沖突，則從需要從目標(biāo)點(diǎn)向兩頭遍歷，找到正確的index。
• 擴(kuò)容時(shí)，會(huì)查看之前是否有緩存的 int[]數(shù)組和object[]數(shù)組
• 如果有，復(fù)用給mArray mHashes
• 擴(kuò)容規(guī)則：如果容量大于8，則擴(kuò)容一半。（類似ArrayList）
• 根據(jù)key的hash值在mHashs中的index，如何得到key、value在mArray中的下標(biāo)位置呢？key的位置是index*2，value的位置是index*2+1,也就是說mArray是利用連續(xù)的兩位空間去存放key、value。
• 根據(jù)元素?cái)?shù)量和集合占用的空間情況，判斷是否要執(zhí)行收縮操作
• 如果 mHashes長度大于8，且 集合長度 小于當(dāng)前空間的 1/3,則執(zhí)行一個(gè) shrunk，收縮操作，避免空間的浪費(fèi)
• 類似ArrayList，用復(fù)制操作去覆蓋元素達(dá)到刪除的目的。

總結(jié)

以上是生活随笔為你收集整理的面试必备：ArrayMap源码解析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。