ArrayMap是如何提高記憶體的使用效率的？
ArraySet使用陣列儲存資料，提高了記憶體的使用效率，在資料量不超過1000時，相較於 HashSet ，效率最多不會降低50%，本節來分析下 ofollow,noindex">ArraySet 新增和刪除元素分析 ，谷歌指出 ArrayMap 的設計也是為了更加高效地使用記憶體，在資料量不超過1000時，效率最多不會降低50%。閱讀原碼可以發現， ArrayMap 和 ArraySet 在實現上保持了統一，主要的不同是元素的儲存方式。
繼承結構
可以看到，```ArrayMap```的繼承結構比較簡單，只是實現了Map介面。
儲存結構
可以回憶一下 ArraySet 的儲存結構：一個int型別的陣列mHashes儲存hash值，一個object型別的陣列mArray儲存內容，這兩個陣列的下標一一對應。
ArrayMap 的儲存結構猜想應該和 ArraySet 不一樣，因為 ArrayMap 不僅僅需要儲存value，還需要儲存key，Google的大神們是怎樣解決這個問題的呢？
Google的大神們還是使用了和 ArraySet 一樣的資料結構，在儲存key和value時設計了一個非常巧妙的方法。
如上圖所示，```mHashes```中儲存了```key```的hash值，```key```在```mHashes```的下標為```index```，在```mArray```中，```mArray[index<<1]```儲存```key```，```mArray[index<<1 + 1]```儲存```value```。故```mArray```的長度是```mHashes```的2倍。這樣的設計使的```ArraySet```和```ArrayMap```在儲存結構上保持了統一。
新增和刪除
ArraySet 和 ArrayMap 在實現上保持了統一，閱讀原碼可以發現，他們擁有同樣的快取結構，刪除和新增元素時會有相同的邏輯流程。大致看下 HashMap 的儲存結構
HashMap 的儲存結構，每個連結串列後面的元素的數量沒有達到將連結串列樹化的數目。
HashMap 在儲存k-v鍵值對的時候，首先根據k的hash值找到k-v儲存的連結串列陣列的下標，然後將k-v鍵值對儲存在連結串列的最後。
ArrayMap 使用兩個一維陣列分別儲存k的hash值和k-v鍵值對。新增元素時根據k查詢元素以確認元素是否已經存在，如果已經存在則直接更新，否則新增；刪除元素時查詢元素以確定元素是否存在，如果不存在則直接返回，否則刪除元素。
ArrayMap 在新增刪除元素的過程中，也會涉及到元素的移動，快取的新增和刪除。整個流程和
ArraySet 相同。但是需要注意的是，
ArrayMap 在新增和刪除元素的過程中，儲存k-v鍵值對
mArray
陣列需要同時修改k和v兩個元素。
元素查詢
經過上面的分析，可能發現了一個問題， ArrayMap 和 ArraySet 太相似了。確實是，他們在底層儲存結構，快取結構都是一樣的。新增和刪除元素的時候，需要查詢元素，新增元素時根據k查詢元素以確認元素是否已經存在，如果已經存在則直接更新，否則新增；刪除元素時查詢元素以確定元素是否存在，如果不存在則直接返回，否則刪除元素。 ArrayMap 是否和 ArraySet 具有相同的查詢過程呢。直接上原始碼：
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;
}
private static int binarySearchHashes(int[] hashes, int N, int hash) {
try {
return ContainerHelpers.binarySearch(hashes, N, hash);
} catch (ArrayIndexOutOfBoundsException e) {
if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
throw new ConcurrentModificationException();
} else {
throw e; // the cache is poisoned at this point, there's not much we can do
}
}
}
複製程式碼
以上為 indexOf 函式和 binarySearchHashes 函式的實現。通過對比原始碼，可以發現， ArrayMap 和 ArraySet 使用了相同的二分查詢邏輯，可以肯定的，和 ArraySet 一樣， ArrayMap 在儲存hash值時是有序的。具體的查詢過程的分析可以參考 ArraySet 新增和刪除元素分析
不同點
上面的分析容易讓人產生一種感覺 ArraySet 和 ArrayMap 的實現完全相同。這是一種誤解， ArraySet 和 ArrayMap 在實現的邏輯流程是相同的，但在細節處理上還是有不同。新增刪除元素的過程中，不同點主要體現在在新增和刪除元素的過程中，如果有其他操作改變了 ArrayMap 儲存的內容的數量，則會丟擲 ConcurrentModificationException ， ArrayMap 中能改變儲存容量的是以下三個方法： put 、 remove 、 clear
可以做一個小實驗 首先，兩個執行緒同時修改 ArrayMap 同一個key下的value
ArrayMap<String, String> aMap = new ArrayMap<>();
aMap.put("key", "value");
new Thread(new Runnable() {
@Override
public void run() {
// TODO Auto-generated method stub
for (int i = 0 ; ; i++) {
aMap.put("key", "value" + i);
}
}
}).start();
new Thread(new Runnable() {
@Override
public void run() {
// TODO Auto-generated method stub
for (int i = 0 ; ; i++) {
aMap.put("key", "value" + i);
}
}
}).start();
複製程式碼
執行後可以發現，程式會一直執行，也不會報錯。
接下來看下兩個執行緒同時向 ArrayMap 中新增元素
ArrayMap<String, String> aMap = new ArrayMap<>();
new Thread(new Runnable() {
@Override
public void run() {
// TODO Auto-generated method stub
for (int i = 0 ; ; i++) {
aMap.put("key" + i, "value" + i);
}
}
}).start();
new Thread(new Runnable() {
@Override
public void run() {
// TODO Auto-generated method stub
for (int i = 0 ; ; i++) {
aMap.put("key" + i, "value" + i);
}
}
}).start();
複製程式碼
執行程式後，會報如下異常
Exception in thread "Thread-1" java.util.ConcurrentModificationException at com.rock.collections.array.ArrayMap.put(ArrayMap.java:527) at com.rock.collections.Client$2.run(Client.java:50) at java.lang.Thread.run(Thread.java:748) 複製程式碼
（我將 ArrayMap 抽出來進行測試，故顯示的包名是我自定義的） 可以發現由於兩個執行緒同時向 aMap 中添加了元素，修改了元素的數量，系統丟擲了 ConcurrentModificationException 。
跟蹤下新增元素的過程
@Override
public V put(K key, V value) {
final int osize = mSize;
......
index = ~index;
if (osize >= mHashes.length) {
// 陣列擴容
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
......
allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
......
}
......
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;
}
複製程式碼
原始碼已經很清晰了， CONCURRENT_MODIFICATION_EXCEPTIONS = true ，在新增元素之前，使用 osize 記錄 mSize ，在擴容之後和最後新增元素之前會對當前元素的數量進行判斷，如果發生了變化則丟擲異常。
再跟蹤下刪除元素的過程
public V removeAt(int index) {
final int osize = mSize;
......
if (osize <= 1) {
......
} else {
nsize = osize - 1;
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
......
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
......
} else {
......
}
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
mSize = nsize;
return (V)old;
}
複製程式碼
在縮容或者記錄最終元素的數量之前，如果發現元素的數量被修改過，則丟擲異常。這個地方還有一個要注意的，由於是刪除元素， mSize 最終是要發生變化的，但是原始碼中對比的 mSize 發生變化之前的值。
小結
ArrayMap 的設計是為了更加高效地利用記憶體，高效體現在以下幾點
-
ArrayMap使用更少的儲存單元儲存元素ArrayMap使用int型別的陣列儲存hash，使用Object型別陣列儲存k-v鍵值對，相較於HashMap使用Node儲存節點，ArrayMap儲存一個元素佔用的記憶體更小。 -
ArrayMap在擴容時容量變化更小HashMap在擴容的時候，通常會將容量擴大一倍，而ArrayMap在擴容的時候，如果元素個數超過8，最多擴大自己的1/2。
雖然有以上有點，但是和 ArraySet 一樣， ArrayMap 也存在以下劣勢：
- 儲存大量（超過1000）元素時比較耗時
- 在對元素進行查詢或者確定待插入元素的位置時使用二分查詢，當元素較多時，耗時較長
- 頻繁擴容和縮容，可能會產生大量複製操作
-
ArrayMap在擴容和縮容時需要移動元素，且擴容時容量變化比HashMap小，擴容和縮容的頻率可能更高，元素數量過多時，元素的移動可能會對效能產生影響。
基於以上優缺點，google給出的建議是當元素數量小於1000時，建議使用 Array 代替 HashMap ，效率降低最多不會超過50%