摘要：也是我們使用非常多的，它是基于哈希表的接口的實現(xiàn)，以的形式存在。源碼分析三個構(gòu)造函數(shù)默認初始容量，默認加載因子構(gòu)造一個帶指定初始容量和默認加載因子的空。該臨界點在當中元素的數(shù)量等于數(shù)組長度加載因子。
HashMap也是我們使用非常多的Collection，它是基于哈希表的 Map 接口的實現(xiàn)，以key-value的形式存在。在HashMap中，key-value總是會當做一個整體來處理，系統(tǒng)會根據(jù)hash算法來來計算key-value的存儲位置，我們總是可以通過key快速地存、取value。
HashMap
HashMap.java源碼分析：?
三個構(gòu)造函數(shù)：?
HashMap():默認初始容量capacity（16），默認加載因子factor（0.75）?
HashMap(int initialCapacity)：構(gòu)造一個帶指定初始容量和默認加載因子 (0.75) 的空 HashMap。?
HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個帶指定初始容量和加載因子的空 HashMap。
/**
* Constructs an empty HashMap with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//構(gòu)建自定義初始容量的構(gòu)造函數(shù),默認加載因子0.75的HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//構(gòu)造一個帶指定初始容量和加載因子的空 HashMap
public HashMap(int initialCapacity, float loadFactor) {
...
...
}
HashMap內(nèi)部是使用一個默認容量為16的數(shù)組來存儲數(shù)據(jù)的，而數(shù)組中每一個元素卻又是一個鏈表的頭結(jié)點，所以，更準確的來說，HashMap內(nèi)部存儲結(jié)構(gòu)是使用哈希表的拉鏈結(jié)構(gòu)（數(shù)組+鏈表），如圖：?
這種存儲數(shù)據(jù)的方法叫做拉鏈法?
且每一個結(jié)點都是Entry類型，那么Entry是什么呢？我們來看看HashMap中Entry的屬性：
final K key; //key值
V value; //value值
HashMapEntry next;//next下一個Entry
int hash;//key的hash值
快速存取
put(key,value);
public V put(K key, V value) {
if (table == EMPTY_TABLE) {//判斷table空數(shù)組，
inflateTable(threshold);//創(chuàng)建數(shù)組容量為threshold大小的數(shù)組，threshold在HashMap構(gòu)造函數(shù)中賦值initialCapacity（指定初始容量）;
}
//當key為null，調(diào)用putForNullKey方法，保存null與table第一個位置中，這是HashMap允許key為null的原因
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key); //計算key的hash值
int i = indexFor(hash, table.length); //計算key hash 值在 table 數(shù)組中的位置
//從i出開始迭代 e,找到 key 保存的位置
for (HashMapEntry e = table[i]; e != null; e = e.next) {
Object k;
//判斷該條鏈上是否有hash值相同的(key相同)
//若存在相同，則直接覆蓋value，返回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;//舊值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue;//返回覆蓋后的舊值
}
}
//修改次數(shù)增加1
modCount++;
//將key、value添加至i位置處
addEntry(hash, key, value, i);
return null;
}
put過程分析：這篇文章http://www.cnblogs.com/chenssy/p/3521565.html總結(jié)的可以。
put過程結(jié)論：?
當我們想一個HashMap中添加一對key-value時，系統(tǒng)首先會計算key的hash值，然后根據(jù)hash值確認在table中存儲的位置。若該位置沒有元素，則直接插入。否則迭代該處元素鏈表并依此比較其key的hash值。如果兩個hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆蓋原來節(jié)點的value。如果兩個hash值相等但key值不等 ，則將該節(jié)點插入該鏈表的鏈頭。
void addEntry(int hash, K key, V value, int bucketIndex) {
//獲取bucketIndex處的Entry
Entry e = table[bucketIndex];
//將新創(chuàng)建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry
table[bucketIndex] = new Entry(hash, key, value, e);
//若HashMap中元素的個數(shù)超過極限了，則容量擴大兩倍
if (size++ >= threshold)
resize(2 * table.length);
}
這個方法中有兩點需要注意：
一是鏈的產(chǎn)生。這是一個非常優(yōu)雅的設(shè)計。系統(tǒng)總是將新的Entry對象添加到bucketIndex處。如果bucketIndex處已經(jīng)有了對象，那么新添加的Entry對象將
指向原有的Entry對象，形成一條Entry鏈，但是若bucketIndex處沒有Entry對象，也就是e==null,那么新添加的Entry對象指向null，也就不會產(chǎn)生Entry鏈了。
二、擴容問題。
隨著HashMap中元素的數(shù)量越來越多，發(fā)生碰撞的概率就越來越大，所產(chǎn)生的鏈表長度就會越來越長，這樣勢必會影響HashMap的速度，為了保證HashMap的效率，系統(tǒng)必須要在某個臨界點進行擴容處理。該臨界點在當HashMap中元素的數(shù)量等于table數(shù)組長度*加載因子。但是擴容是一個非常耗時的過程，因為它需要重新計算這些數(shù)據(jù)在新table數(shù)組中的位置并進行復(fù)制處理。所以如果我們已經(jīng)預(yù)知HashMap中元素的個數(shù)，那么預(yù)設(shè)元素的個數(shù)能夠有效的提高HashMap的性能。
讀取實現(xiàn)：get(key)?
相對于HashMap的存而言，取就顯得比較簡單了。通過key的hash值找到在table數(shù)組中的索引處的Entry，然后返回該key對應(yīng)的value即可。
public V get(Object key) {
// 若為null，調(diào)用getForNullKey方法返回相對應(yīng)的value
if (key == null)
return getForNullKey();
// 根據(jù)該 key 的 hashCode 值計算它的 hash 碼
int hash = hash(key.hashCode());
// 取出 table 數(shù)組中指定索引處的值
for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//若搜索的key與查找的key相同，則返回相對應(yīng)的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
在不斷的向HashMap里put數(shù)據(jù)時，當達到一定的容量限制時（這個容量滿足這樣的一個關(guān)系時候?qū)U容：HashMap中的數(shù)據(jù)量>容量*加載因子，而HashMap中默認的加載因子是0.75），HashMap的空間將會擴大；擴大之前容量的2倍 ：resize（newCapacity）
int newCapacity = table.length;//賦值數(shù)組長度
newCapacity <<= 1;//x2
if (newCapacity > table.length)
resize(newCapacity);//調(diào)整HashMap大小容量為之前table的2倍
這也就是重點所在，為什么在Android上需要使用SparseArray和ArrayMap代替HashMap，主要原因就是Hashmap隨著數(shù)據(jù)不斷增多，達到最大值時，需要擴容，而且擴容的大小是之前的2倍.
SparseArray
SparseArray.java 源碼?
SparseArray比HashMap更省內(nèi)存，在某些條件下性能更好，主要是因為它避免了對key的自動裝箱（int轉(zhuǎn)為Integer類型），它內(nèi)部則是通過兩個數(shù)組來進行數(shù)據(jù)存儲的，一個存儲key，另外一個存儲value，為了優(yōu)化性能，它內(nèi)部對數(shù)據(jù)還采取了壓縮的方式來表示稀疏數(shù)組的數(shù)據(jù)，從而節(jié)約內(nèi)存空間，我們從源碼中可以看到key和value分別是用數(shù)組表示：
private int[] mKeys;//int 類型key數(shù)組
private Object[] mValues;//value數(shù)組
構(gòu)造函數(shù)：?
SparseArray():默認容量10；?
SparseArray(int initialCapacity):指定特定容量的SparseArray
public SparseArray() {
this(10);
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {//判斷傳入容量值
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {//不為0初始化key value數(shù)組
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;//mSize賦值0
}
從上面創(chuàng)建的key數(shù)組：SparseArray只能存儲key為int類型的數(shù)據(jù)，同時，SparseArray在存儲和讀取數(shù)據(jù)時候，使用的是二分查找法；
/**
* 二分查找，中間位置的值與需要查找的值循環(huán)比對
* 小于：范圍從mid+1 ~ h1
* 大于：范圍從0~mid-1
* 等于：找到值返回位置mid
*/
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
}
SparseArray存取數(shù)據(jù)
SparseArray的put方法：
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//二分查找數(shù)組mKeys中key存放位置，返回值是否大于等于0來判斷查找成功
if (i >= 0) {//找到直接替換對應(yīng)值
mValues[i] = value;
} else {//沒有找到
i = ~i;//i按位取反得到非負數(shù)
if (i < mSize && mValues[i] == DELETED) {//對應(yīng)值是否已刪除，是則替換對應(yīng)鍵值
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {//當mGarbage == true 并且mSize 大于等于key數(shù)組的長度
gc(); //調(diào)用gc回收
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//最后將新鍵值插入數(shù)組，調(diào)用 GrowingArrayUtils的insert方法：
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
下面進去看看 GrowingArrayUtils的insert方法有什么擴容的；
public static T[] insert(T[] array, int currentSize, int index, T element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {//小于數(shù)組長度
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
//大于數(shù)組長度需要進行擴容
T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(),
growSize(currentSize));//擴容規(guī)則里面就一句三目運算：currentSize <= 4 ? 8 : currentSize * 2;（擴容2倍）
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
SparseArray的get（key）方法：
public E get(int key) {
return get(key, null);//調(diào)用get(key,null)方法
}
public E get(int key, E valueIfKeyNotFound) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//二分查找key
if (i < 0 || mValues[i] == DELETED) {//沒有找到，或者已經(jīng)刪除返回null
return valueIfKeyNotFound;
} else {//找到直接返回i位置的value值
return (E) mValues[i];
}
}
SparseArray在put添加數(shù)據(jù)的時候，會使用二分查找法和之前的key比較當前我們添加的元素的key的大小，然后按照從小到大的順序排列好，所以，SparseArray存儲的元素都是按元素的key值從小到大排列好的。?
而在獲取數(shù)據(jù)的時候，也是使用二分查找法判斷元素的位置，所以，在獲取數(shù)據(jù)的時候非?？欤菻ashMap快的多，因為HashMap獲取數(shù)據(jù)是通過遍歷Entry[]數(shù)組來得到對應(yīng)的元素。
SparseArray應(yīng)用場景：
雖說SparseArray性能比較好，但是由于其添加、查找、刪除數(shù)據(jù)都需要先進行一次二分查找，所以在數(shù)據(jù)量大的情況下性能并不明顯，將降低至少50%。
滿足下面兩個條件我們可以使用SparseArray代替HashMap：
數(shù)據(jù)量不大，最好在千級以內(nèi)
key必須為int類型，這中情況下的HashMap可以用SparseArray代替：
ArrayMap
ArrayMap是一個
public class ArrayMap extends SimpleArrayMap implements Map {}
構(gòu)造函數(shù)由父類實現(xiàn)：
public ArrayMap() {
super();
}
public ArrayMap(int capacity) {
super(capacity);
}
public ArrayMap(SimpleArrayMap map) {
super(map);
}
HashMap內(nèi)部有一個HashMapEntry[]對象，每一個鍵值對都存儲在這個對象里，當使用put方法添加鍵值對時，就會new一個HashMapEntry對象，而ArrayMap的存儲中沒有Entry這個東西，他是由兩個數(shù)組來維護的，mHashes數(shù)組中保存的是每一項的HashCode值，mArray中就是鍵值對，每兩個元素代表一個鍵值對，前面保存key，后面的保存value。
int[] mHashes;//key的hashcode值
Object[] mArray;//key value數(shù)組
SimpleArrayMap（）：創(chuàng)建一個空的ArrayMap，默認容量為0，它會跟隨添加的item增加容量。?
SimpleArrayMap(int capacity)：指定特定容量ArrayMap；?
SimpleArrayMap(SimpleArrayMap map)：指定特定的map；
public SimpleArrayMap() {
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
...
ArrayMap 存取
ArrayMap 的put(K key, V value)：key 不為null
/**
* Add a new value to the array map.
* @param key The key under which to store the value. Must not be null. If
* this key already exists in the array, its value will be replaced.
* @param value The value to store for the given key.
* @return Returns the old value that was stored for the given key, or null if there
* was no such key.
*/
public V put(K key, V value) {
final int hash;
int index;
//key 不能為null
if (key == null) { //key == null，hash為0
hash = 0;
index = indexOfNull();
} else {//獲取key的hash值
hash = key.hashCode();
index = indexOf(key, hash);//獲取位置
}
//返回index位置的old值
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];//old 賦值 value
mArray[index] = value;
return old;
}
//否則按位取反
index = ~index;
//擴容 System.arrayCopy數(shù)據(jù)
if (mSize >= mHashes.length) {
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= 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);//申請數(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);
}
freeArrays(ohashes, oarray, mSize);//重新收縮數(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);
}
//最后 mHashs數(shù)組存儲key的hash值
mHashes[index] = hash;
mArray[index<<1] = key;//mArray數(shù)組相鄰位置存儲key 和value值
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
從最后可以看出：ArrayMap的存儲中沒有Entry這個東西，他是由兩個數(shù)組來維護的，mHashes數(shù)組中保存的是每一項的HashCode值，mArray中就是鍵值對，每兩個元素代表一個鍵值對，前面保存key，后面的保存value。
ArrayMap 的get(Object key)：從Array數(shù)組獲得value
/**
* Retrieve a value from the array.
* @param key The key of the value to retrieve.
* @return Returns the value associated with the given key,
* or null if there is no such key.
*/
public V get(Object key) {
final int index = indexOfKey(key);//獲得key在Array的存儲位置
return index >= 0 ? (V)mArray[(index<<1)+1] : null;//如果index>=0 ?。╥ndex+1）上的value值，否則返回null（從上面put知道array存儲是key（index） value（index+1）存儲的）
}
ArrayMap 和 HashMap區(qū)別：
1.存儲方式不同
HashMap內(nèi)部有一個HashMapEntry[]對象，每一個鍵值對都存儲在這個對象里，當使用put方法添加鍵值對時，就會new一個HashMapEntry對象
ArrayMap的存儲中沒有Entry這個東西，他是由兩個數(shù)組來維護的
mHashes數(shù)組中保存的是每一項的HashCode值，
mArray中就是鍵值對，每兩個元素代表一個鍵值對，前面保存key，后面的保存value。
2.添加數(shù)據(jù)時擴容時的處理不一樣
HashMap使用New的方式申請空間，并返回一個新的對象，開銷會比較大
ArrayMap用的是System.arrayCopy數(shù)據(jù)，所以效率相對要高。
3、ArrayMap提供了數(shù)組收縮的功能，只要判斷過判斷容量尺寸，例如clear，put，remove等方法，只要通過判斷size大小觸發(fā)到freeArrays或者allocArrays方法，會重新收縮數(shù)組，釋放空間。
4、ArrayMap相比傳統(tǒng)的HashMap速度要慢，因為查找方法是二分法，并且當你刪除或者添加數(shù)據(jù)時，會對空間重新調(diào)整，在使用大量數(shù)據(jù)時，效率低于50%?？梢哉fArrayMap是犧牲了時間換區(qū)空間。但在寫手機app時，適時的使用ArrayMap，會給內(nèi)存使用帶來可觀的提升。ArrayMap內(nèi)部還是按照正序排列的，這時因為ArrayMap在檢索數(shù)據(jù)的時候使用的是二分查找，所以每次插入新數(shù)據(jù)的時候ArrayMap都需要重新排序，逆序是最差情況；
HashMap ArrayMap SparseArray性能測試對比（轉(zhuǎn)載 ）
直接看：http://www.jianshu.com/p/7b9a1b386265測試對比
1.插入性能時間對比?
數(shù)據(jù)量小的時候，差異并不大（當然了，數(shù)據(jù)量小，時間基準小，確實差異不大），當數(shù)據(jù)量大于5000左右，SparseArray，最快，HashMap最慢，乍一看，好像SparseArray是最快的，但是要注意，這是順序插入的。也就是SparseArray和Arraymap最理想的情況。
倒序插入：數(shù)據(jù)量大的時候HashMap遠超Arraymap和SparseArray，也前面分析一致。?
當然了，數(shù)據(jù)量小的時候，例如1000以下，這點時間差異也是可以忽略的。
SparseArray在內(nèi)存占用方面的確要優(yōu)于HashMap和ArrayMap不少，通過數(shù)據(jù)觀察，大致節(jié)省30%左右，而ArrayMap的表現(xiàn)正如前面說的，優(yōu)化作用有限，幾乎和HashMap相同。
2.查找性能對比
如何選擇使用
1.在數(shù)據(jù)量小的時候一般認為1000以下，當你的key為int的時候，使用SparseArray確實是一個很不錯的選擇，內(nèi)存大概能節(jié)省30%，相比用HashMap，因為它key值不需要裝箱，所以時間性能平均來看也優(yōu)于HashMap,建議使用！
2.ArrayMap相對于SparseArray，特點就是key值類型不受限，任何情況下都可以取代HashMap,但是通過研究和測試發(fā)現(xiàn)，ArrayMap的內(nèi)存節(jié)省并不明顯，也就在10%左右，但是時間性能確是最差的，當然了，1000以內(nèi)的如果key不是int 可以選擇ArrayMap。
參考：?
MVC，MVP 和 MVVM 模式如何選擇？
?一招教你讀懂JVM和Dalvik之間的區(qū)別
我的Android重構(gòu)之旅：框架篇
NDK項目實戰(zhàn)—高仿360手機助手之卸載監(jiān)聽
（Android）面試題級答案（精選版）
