當我們需要存儲健->值這樣的數據類型時，腦海里想到的第一個數據類型應該是HashMap。然后開始肆無忌憚的使用它，而從不考慮它帶來的性能影響。

使用HashMap時，Android Studio會發(fā)出警告，提示你使用ArrayMap來代替，但是通常被我們忽略了。

既然Android推薦了ArrayMap，那我們應該優(yōu)先考慮使用它而不是HashMap。下面簡單對比下HashMap和ArrayMap的內部實現，以便探求在什么場景下使用它。

HashMap vs ArrayMap

HashMap 位于 java.util.HashMap包中。
ArrayMap 位于 android.util.ArrayMap和android.support.v4.util.ArrayMap包中。

HashMap

我們知道，java的HashMap的存儲結構是一個數據加單向鏈表的形式。HashMap將每隔節(jié)點信息存儲在Entry<K,V>結構中。Entry<K,V>中存儲了節(jié)點對應的key、value、hash信息，同時存儲了當前節(jié)點的下一個節(jié)點的引用。因此，Entry<K,V>是一個單向鏈表。每一個key對應的hashCode，在HashMap數組中都可以找到一個位置，而如果多個key對應了相同的hashCode，那么他們在數組中對應在相同的位置上，這是HashMap將把對應的信息放到Entry<K,V>中，并使用鏈表連接這些Entry<K,V>。
HashMap基本上是一個HashMap.Entry<K,V>的數組，Entry<K,V>中包含以下字段：

• 一個非基本數據類型的key
• 一個非基本數據類型的value
• 保存對象的hashCode
• 指向下一個Entry<K,V>的指針

當有鍵值對插入時，HashMap會發(fā)生什么呢？

• 首先，計算鍵的hashCode，然后這個值會付給Entry類中對應的hashCode。
• 然后，使用這個hashCode找到它將要被存入的數組中的位置index。
• 如果該位置已經有一個元素，那么新的元素將會被插入到這個位置上的鏈表的頭部，next指向上一個元素。
  現在，當使用key去查詢時，時間復雜度是O(1)。

雖然在時間上HashMap更快，但是它也花費了更多的內存空間。由于HashMap存儲的是非基本數據類型，因此自動裝箱的存在意味著每次插入都會有額外的對象創(chuàng)建，這會影響到內存的利用。另外，Entry對象本身是一層額外需要被創(chuàng)建以及被垃圾回收的對象。

在Android中，內存是至關重要的，因為持續(xù)的分發(fā)和釋放內存會觸發(fā)垃圾回收，導致應用出現卡頓。

ArrayMap

ArrayMap在設計上比傳統(tǒng)的HashMap更多的考慮了內存的優(yōu)化，可以理解為以時間換空間的一種優(yōu)化。它使用了兩個數組來存儲數據——一個整型數組存儲鍵的hashCode，另一個對象數組存儲鍵/值對。這樣既能避免為每個存入map中的鍵創(chuàng)建額外的對象，又能更積極的控制這些數據的長度的增加。因為增加長度只需要拷貝數組中的鍵，而不是重新構建一個哈希表。

需要注意的是，ArrayMap并不適用于可能含有大量條目的數據類型，前面說了，它是一種以時間換空間的優(yōu)化，通常比HashMap要慢，因為在查找時需要進行二分查找，增加或刪除時，需要在數組中插入或者刪除鍵，對于一個百數量級的容器來說，二者的性能差異是可以忽略的。
ArrayMap使用兩個數組，它的對象實例內部有用來存儲對象的Object[] mArray數組和用來存儲哈希值的int[] mHashes數組。

當插入一個鍵值對時：

鍵被插入到objects的下一個空閑位置。值對象唄插入到mArray的與對應鍵相鄰的位置。計算出的鍵的hashCode會被插入到mHashes數組的下一個空閑位置。

當查找一個key時：

先計算key的hashCode，在mHashes數組中二分查找此hashCode，這使得時間復雜度增加到了O(logN)。得到hashCode對應的索引index，鍵值對中的鍵就存儲在mArray[index<<1]，而值就存儲在mArray[index<<1+1]的位置。
get方法：

@Override
public V get(Object key) {
 final int index = indexOfKey(key);
 return index >= 0 ?(V)mArray[(index<<1)+1] : null;
}

查找key的位置：

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 =ContainerHelpers.binarySearch(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;
}

ArrayMap花費了更多的時間去查找，但是內存的效率提升了。通常在數百量級的情況下，這種時間差異是可以忽略的，但是內存的效率卻獲得了提升。

推薦的數據結構:
? ArrayMap<K,V> 替代 HashMap<K,V>
? ArraySet<K,V> 替代 HashSet<K,V>
? SparseArray<V> 替代 HashMap<Integer,V>
? SparseBooleanArray 替代 HashMap<Integer,Boolean>
? SparseIntArray 替代 HashMap<Integer,Integer>
? SparseLongArray 替代 HashMap<Integer,Long>
? LongSparseArray<V> 替代 HashMap<Long,V>