什麼是HashMap?
HashMap是基于哈希表的Map接口的非同步實作。此實作提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特别是它不保證該順序恒久不變。
HashMap的資料結構
在Java程式設計語言中，最基本的結構就是兩種，一個是數組，另外一個是模拟指針（引用），所有的資料結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個“連結清單散列”的資料結構，即數組和連結清單的結合體。
文字描述永遠要配上圖才能更好的講解資料結構，HashMap的結構圖如下。
從上圖中可以看出，HashMap底層就是一個數組結構，數組中的每一項又是一個連結清單或者紅黑樹。當建立一個HashMap的時候，就會初始化一個數組。
下面先通過大概看下HashMap的核心成員。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// 預設容量，預設為16，必須是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量，值是2^30
static final int MAXIMUM_CAPACITY = 1 << 30
// 裝載因子，預設的裝載因子是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 解決沖突的資料結構由連結清單轉換成樹的門檻值，預設為8
static final int TREEIFY_THRESHOLD = 8;
// 解決沖突的資料結構由樹轉換成連結清單的門檻值，預設為6
static final int UNTREEIFY_THRESHOLD = 6;
/* 當桶中的bin被樹化時最小的hash表容量。
* 如果沒有達到這個門檻值，即hash表容量小于MIN_TREEIFY_CAPACITY，當桶中bin的數量太多時會執行resize擴容操作。
* 這個MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
static class Node<K,V> implements Map.Entry<K,V> {
//...
}
// 存儲資料的數組
transient Node<K,V>[] table;
// 周遊的容器
transient Set<Map.Entry<K,V>> entrySet;
// Map中KEY-VALUE的數量
transient int size;
/**
* 結構性變更的次數。
* 結構性變更是指map的元素數量的變化，比如rehash操作。
* 用于HashMap快速失敗操作，比如在周遊時發生了結構性變更，就會抛出ConcurrentModificationException。
*/
transient int modCount;
// 下次resize的操作的size值。
int threshold;
// 負載因子，resize後容量的大小會增加現有size * loadFactor
final float loadFactor;
} HashMap的初始化
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 其他值都是預設值
} 通過源碼可以看出初始化時并沒有初始化數組table，那隻能在put操作時放入了，為什麼要這樣做？估計是避免初始化了HashMap之後不使用反而占用記憶體吧，哈哈哈。
HashMap的存儲操作
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} 下面我們詳細講一下HashMap是如何确定數組索引的位置、進行put操作的詳細過程以及擴容機制(resize)
hash計算，确定數組索引位置
不管增加、删除、查找鍵值對，定位到哈希桶數組的位置都是很關鍵的第一步。前面說過HashMap的資料結構是數組和連結清單的結合，是以我們當然希望這個HashMap裡面的元素位置盡量分布均勻些，盡量使得每個位置上的元素數量隻有一個，那麼當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，不用周遊連結清單，大大優化了查詢的效率。HashMap定位數組索引位置，直接決定了hash方法的離散性能。
看下源碼的實作:
static final int hash(Object key) { //jdk1.8
int h;
// h = key.hashCode() 為第一步 取hashCode值
// h ^ (h >>> 16) 為第二步 高位參與運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} 通過hashCode()的高16位異或低16位實作的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、品質來考慮的，這麼做可以在數組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。
大家都知道上面代碼里的key.hashCode()函數調用的是key鍵值類型自帶的哈希函數，傳回int型散列值。理論上散列值是一個int型，如果直接拿散列值作為下标通路HashMap主數組的話，考慮到2進制32位帶符号的int表值範圍從‑2147483648到2147483648。前後加起來大概40億的映射空間。隻要哈希函數映射得比較均勻松散，一般應用是很難出現碰撞的。但問題是一個40億長度的數組，記憶體是放不下的。你想，HashMap擴容之前的數組初始大小才16。是以這個散列值是不能直接拿來用的。用之前還要先做對數組的長度取模運算，得到的餘數才能用來通路數組下标。源碼中模運算是在這個indexFor( )函數里完成。
bucketIndex = indexFor(hash, table.length);
//indexFor的代碼也很簡單，就是把散列值和數組長度做一個"與"操作，
static int indexFor(int h, int length) {
return h & (length-1);
} 順便說一下，這也正好解釋了為什麼HashMap的數組長度要取2的整次幂。因為這樣（數組長度‑1）正好相當于一個“低位掩碼”。“與”操作的結果就是散列值的高位全部歸零，隻保留低位值，用來做數組下标通路。以初始長度16為例，16‑1=15。2進制表示是00000000 0000000000001111。和某散列值做“與”操作如下，結果就是截取了最低的四位值。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部歸零，隻保留末四位 但這時候問題就來了，這樣就算我的散列值分布再松散，要是隻取最後幾位的話，碰撞也會很嚴重。更要命的是如果散列本身做得不好，分布上成等差數列的漏洞，恰好使最後幾個低位呈現規律性重複，就無比蛋疼。這時候“擾動函數”的價值就出來了，說到這大家應該都明白了，看下圖。
hash計算過程
右位移16位，正好是32bit的一半，自己的高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的随機性。而且混合後的低位摻雜了高位的部分特征，這樣高位的資訊也被變相保留下來。
putVal方法
HashMap的put方法執行過程可以通過下圖來了解，自己有興趣可以去對比源碼更清楚地研究學習。
源碼以及解釋如下:
// 真正的put操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果table沒有初始化，或者初始化的大小為0，進行resize操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果hash值對應的桶内沒有資料，直接生成結點并且把結點放入桶中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果hash值對應的桶内有資料解決沖突，再放入桶中
else {
Node<K,V> e; K k;
//判斷put的元素和已經存在的元素是相同(hash一緻，并且equals傳回true)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// put的元素和已經存在的元素是不相同(hash一緻，并且equals傳回true)
// 如果桶内元素的類型是TreeNode，也就是解決hash解決沖突用的樹型結構，把元素放入樹種
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 桶内元素的類型不是TreeNode，而是連結清單時，把資料放傳入連結表的最後一個元素上
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果連結清單的長度大于轉換為樹的門檻值(TREEIFY_THRESHOLD)，将存儲元素的資料結構變更為樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果查已經存在key，停止周遊
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 已經存在元素時
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果K-V數量大于門檻值，進行resize操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 擴容機制
HashMap的擴容機制用的很巧妙，以最小的性能來完成擴容。擴容後的容量就變成了變成了之前容量的2倍，初始容量為16，是以經過rehash之後，元素的位置要麼是在原位置，要麼是在原位置再向高下标移動上次容量次數的位置，也就是說如果上次容量是16，下次擴容後容量變成了16+16，如果一個元素在下标為7的位置，下次擴容時，要不還在7的位置，要不在7+16的位置。
我們下面來解釋一下Java8的擴容機制是怎麼做到的？n為table的長度，圖（a）表示擴容前的key1和key2兩種key确定索引位置的示例，圖（b）表示擴容後key1和key2兩種key确定索引位置的示例，其中hash1是key1對應的哈希與高位運算結果。
元素在重新計算hash之後，因為n變為2倍，那麼n-1的mask範圍在高位多1bit(紅色)，是以新的index就會發生這樣的變化：
是以，我們在擴充HashMap的時候，不需要像JDK1.7的實作那樣重新計算hash，隻需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴充為32的resize示意圖：
而hash值的高位是否為1，隻需要和擴容後的長度做與操作就可以了，因為擴容後的長度為2的次幂，是以高位必為1，低位必為0，如10000這種形式，源碼中有
e.hash & oldCap
來做到這個邏輯。
這個設計确實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是随機的，是以resize的過程，均勻的把之前的沖突的節點分散到新的bucket了。這一塊就是JDK1.8新增的優化點。有一點注意差別，JDK1.7中rehash的時候，舊連結清單遷移新連結清單的時候，如果在新表的數組索引位置相同，則連結清單元素會倒置，但是從上圖可以看出，JDK1.8不會倒置。下面是JDK1.8的resize源碼，寫的很贊，如下:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 計算新的容量值和下一次要擴充的容量
if (oldCap > 0) {
// 超過最大值就不再擴充了，就隻好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒超過最大值，就擴充為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果位置上沒有元素，直接為null
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果隻有一個元素，新的hash計算後放入新的數組中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是樹狀結構，使用紅黑樹儲存
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果是連結清單形式
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//hash碰撞後高位為0，放入低Hash值的連結清單中
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//hash碰撞後高位為1，放入高Hash值的連結清單中
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 低hash值的連結清單放入數組的原始位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高hash值的連結清單放入數組的原始位置 + 原始容量
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} 原作者：feigeswjtu