概述
HashMap是基于哈希表的 Map 接口的實(shí)現(xiàn)。數(shù)據(jù)以鍵值對(duì)的形式存儲(chǔ)救欧，和HashTab的差別在于HashMap可以以null作為鍵值，但是HashMap是線程不安全的。如果要實(shí)現(xiàn)線程同步可以使用：
- Map map = Collections.synchronizedMap(new HashMap());
- ConcurrentHashMap
HashMap的數(shù)據(jù)結(jié)構(gòu)
HashMap是通過(guò)數(shù)組和鏈表（散列鏈表）來(lái)實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)的难衰。之所以HashMap查詢速度很快，是因?yàn)樗峭ㄟ^(guò)散列碼來(lái)決定存儲(chǔ)位置逗栽。通過(guò)獲取key的hashcode和數(shù)組的長(zhǎng)度的&值來(lái)確定存儲(chǔ)的位置盖袭，如果有相同的key的hashcode，那么就是所謂的hash沖突，就添加到對(duì)應(yīng)的鏈表結(jié)構(gòu)的數(shù)據(jù)中苍凛。
紫色代表數(shù)組代表哈希表趣席，也稱為哈希數(shù)組，綠色代表鏈表醇蝴。數(shù)組存儲(chǔ)具有相同key值hashcode的鏈表的表頭宣肚。數(shù)組的元素和鏈表的節(jié)點(diǎn)都是Entry對(duì)象。
HashMap源碼分析（Android中的源碼）
- HashMapEntry對(duì)象：
/** HashMapEntry是單向鏈表悠栓。
* 它是 “HashMap鏈?zhǔn)酱鎯?chǔ)法”對(duì)應(yīng)的鏈表霉涨。
* 它實(shí)現(xiàn)了Map.Entry 接口，即實(shí)現(xiàn)getKey(), getValue(), setValue(V value), equals(Object o), hashCode()這些函數(shù)
**/
static class HashMapEntry<K, V> implements Entry<K, V> {
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;
HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
@Override public final boolean equals(Object o) {
if (!(o instanceof Entry)) {
return false;
}
Entry<?, ?> e = (Entry<?, ?>) o;
return Objects.equal(e.getKey(), key)
&& Objects.equal(e.getValue(), value);
}
@Override public final int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
@Override public final String toString() {
return key + "=" + value;
}
}
HashMapEntry就是一個(gè)單向鏈表惭适，每個(gè)節(jié)點(diǎn)包含了key笙瑟、value、hash值癞志、和下一個(gè)節(jié)點(diǎn)往枷。
- 重要屬性：
private static final int MINIMUM_CAPACITY = 4;//最小的容量，也是默認(rèn)的初始容量
static final float DEFAULT_LOAD_FACTOR = .75F;//默認(rèn)的加載因子
transient HashMapEntry<K, V>[] table;//哈希表
transient int modCount;//被修改的次數(shù)
transient int size;//存放元素的個(gè)數(shù)
private transient int threshold;//閾值凄杯，當(dāng)前的元素個(gè)數(shù)查過(guò)閾值進(jìn)行擴(kuò)容错洁，閾值 = 加載因子*總?cè)萘?加載因子在Android 的源碼中被閹割了，固定為0.75戒突，這是和在jdk中不同的地方
public HashMap(int capacity, float loadFactor) {
this(capacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor: " + loadFactor);
}
/* 加載因子固定為3/4
* Note that this implementation ignores loadFactor; it always uses
* a load factor of 3/4. This simplifies the code and generally
* improves performance.
*/
}
加載因子表示HashMap填充的程度屯碴，加載因子越大，HashMap填充的越滿才進(jìn)行擴(kuò)容膊存，空間利用率越高导而，造成的問(wèn)題是存放的數(shù)據(jù)越多，hash沖突的可能性越大隔崎，查找的效率越低今艺。反之亦反。這是一個(gè)空間和效率的之間的取舍爵卒。一般用默認(rèn)的就行了洼滚。
- put方法：
public V put(K key, V value) {
if (key == null) {
//存放null的key值，則將該鍵值對(duì)添加到table[0]中技潘。
return putValueForNullKey(value);
}
//對(duì)key的hashcode值進(jìn)行再次計(jì)算得到hash遥巴。
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
//通過(guò)hash值和數(shù)組長(zhǎng)度來(lái)確定數(shù)組的下標(biāo)，這里的值不是隨便取的
int index = hash & (tab.length - 1);
//遍歷對(duì)應(yīng)的數(shù)組下標(biāo)的鏈表享幽，如果存在相同的key值就替換原來(lái)的value
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
//否則加載列表的頭部（也就是數(shù)組對(duì)應(yīng)的位置）
//在添加新的數(shù)據(jù)之前檢查是否需要擴(kuò)容铲掐。如果數(shù)據(jù)的大小超過(guò)閾值，數(shù)組的容量就擴(kuò)大到原來(lái)的2倍
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
//把數(shù)據(jù)添加到表頭
addNewEntry(key, value, hash, index);
return null;
}
hash & (tab.length - 1)的算法來(lái)取到數(shù)組的下標(biāo)值值桩，這個(gè)方式即可實(shí)現(xiàn)均勻的散列摆霉，還可以使數(shù)組不越界。那為什么擴(kuò)容需要2的次冪呢，因?yàn)閔ash & (tab.length - 1)中携栋，如果括號(hào)中的結(jié)果數(shù)奇數(shù)的話最后一位為1搭盾，hash&xx最后的接口有可能是奇數(shù)也有可能是偶數(shù)；如果括號(hào)中的值是偶數(shù)的話婉支，那最后的結(jié)果也只能是偶數(shù)鸯隅，那么數(shù)組存放的值只能存放在偶數(shù)下標(biāo)中，浪費(fèi)了一般的資源向挖，如果是2的倍數(shù)減一蝌以，剛好能夠控制能過(guò)取到所有的下標(biāo)值。因此何之，length取2的整數(shù)次冪跟畅，是為了使不同hash值發(fā)生碰撞的概率較小，這樣就能使元素在哈希表中均勻地散列溶推。
擴(kuò)容：
private HashMapEntry<K, V>[] doubleCapacity() {
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable;
}
int newCapacity = oldCapacity * 2;
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
if (size == 0) {
return newTable;
}
for (int j = 0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry<K, V> e = oldTable[j];
if (e == null) {
continue;
}
int highBit = e.hash & oldCapacity;
HashMapEntry<K, V> broken = null;
newTable[j | highBit] = e;
for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
int nextHighBit = n.hash & oldCapacity;
if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken != null)
broken.next = null;
}
return newTable;
}
新建了一個(gè)數(shù)組徊件，是原來(lái)數(shù)組容量的兩倍，然后重新計(jì)算hashcode在數(shù)組中的位置蒜危，并且存放在數(shù)組中虱痕。
那為什么擴(kuò)容呢？隨著HashMap存放的數(shù)據(jù)越來(lái)越多舰褪，hash沖入產(chǎn)生的概率就越來(lái)越大，造成查找效率越來(lái)越低疏橄，所以進(jìn)行擴(kuò)容占拍，但是擴(kuò)容需要把所有的元素遍歷重新賦值，還要新建一個(gè)數(shù)組捎迫，這是HashMap很消耗資源的地方晃酒。
在達(dá)到閾值的時(shí)候開(kāi)始擴(kuò)容，如：現(xiàn)在的容量大小為8,8*0.75 = 6窄绒，當(dāng)HashMap中的元素個(gè)數(shù)達(dá)到6的時(shí)候就開(kāi)始擴(kuò)容贝次。
