HashMap實現原理 HashMap的底層使用數組+鏈表/紅黑樹實現。 這表示HashMap是Node數組構成，其中Node類的實現如下，可以看出這其實就是個鏈表，鏈表的每個結點是一個映射。 HashMap的每個下標都存放了一條鏈表。 常量/變數定義 關於modCount的作用見 "這篇blog" ...
HashMap實現原理
HashMap的底層使用數組+鏈表/紅黑樹實現。
transient Node<K,V>[] table;這表示HashMap是Node數組構成，其中Node類的實現如下，可以看出這其實就是個鏈表，鏈表的每個結點是一個<K,V>映射。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}HashMap的每個下標都存放了一條鏈表。
常量/變數定義
/* 常量定義 */
// 初始容量為16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 負載因數，當鍵值對個數達到DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR會觸發resize擴容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 當鏈表長度大於8，且數組長度大於MIN_TREEIFY_CAPACITY，就會轉為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 當resize時候發現鏈表長度小於6時，從紅黑樹退化為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 在要將鏈表轉為紅黑樹之前，再進行一次判斷，若數組容量小於該值，則用resize擴容，放棄轉為紅黑樹
// 主要是為了在建立Map的初期，放置過多鍵值對進入同一個數組下標中，而導致不必要的鏈表->紅黑樹的轉化，此時擴容即可，可有效減少衝突
static final int MIN_TREEIFY_CAPACITY = 64;
/* 變數定義 */
// 鍵值對的個數
transient int size;
// 鍵值對的個數大於該值時候，會觸發擴容
int threshold;
// 非線程安全的集合類中幾乎都有這個變數的影子，每次結構被修改都會更新該值，表示被修改的次數
transient int modCount;關於modCount的作用見這篇blog
在一個迭代器初始的時候會賦予它調用這個迭代器的對象的modCount，如何在迭代器遍歷的過程中，一旦發現這個對象的modCount和迭代器中存儲的modCount不一樣那就拋異常。
Fail-Fast機制：java.util.HashMap不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了map，那麼將拋出ConcurrentModificationException，這就是所謂fail-fast策略。這一策略在源碼中的實現是通過modCount域，modCount顧名思義就是修改次數，對HashMap內容的修改都將增加這個值，那麼在迭代器初始化過程中會將這個值賦給迭代器的expectedModCount。在迭代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經有其他線程修改了Map。
註意初始容量和擴容後的容量都必須是2的次冪，為什麼呢?
hash方法
先看散列方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}HashMap的散列方法如上，其實就是將hash值的高16位和低16位異或，我們將馬上看到hash在與n - 1相與的時候，高位的信息也被考慮了，能使碰撞的概率減小，散列得更均勻。
在JDK 8中，HashMap的putVal方法中有這麼一句
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);關鍵就是這句(n - 1) & hash，這行代碼是把待插入的結點散列到數組中某個下標中，其中hash就是通過上面的方法的得到的，為待插入Node的key的hash值，n是table的容量即table.length，2的次冪用二進位表示的話，只有最高位為1，其餘為都是0。減去1，剛好就反了過來。比如16的二進位表示為10000，減去1後的二進位表示為01111，除了最高位其餘各位都是1，保證了在相與時，可以使得散列值分佈得更均勻（因為如果某位為0比如1011，那麼結點永遠不會被散列到1111這個位置），且當n為2的次冪時候有(n - 1) & hash == hash % n, 舉個例子，比如hash等於6時候，01111和00110相與就是00110，hash等於16時，相與就等於0了，多舉幾個例子便可以驗證這一結論。最後來回答為什麼HashMap的容量要始終保持2的次冪
- 使散列值分佈均勻
- 位運算的效率比取餘的效率高
註意table.length是數組的容量，而transient int size表示存入Map中的鍵值對數。
int threshold表示臨界值，當鍵值對的個數大於臨界值，就會擴容。threshold的更新是由下麵的方法完成的。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
該方法返回大於等於cap的最小的二次冪數值。比如cap為16，就返回16，cap為17就返回32。
put方法
put方法主要由putVal方法實現：
- 如果沒有產生hash衝突，直接在數組
tab[i = (n - 1) & hash]處新建一個結點； - 否則，發生了hash衝突，此時key如果和頭結點的key相同，找到要更新的結點，直接跳到最後去更新值
- 否則，如果數組下標中的類型是TreeNode，就插入到紅黑樹中
- 如果只是普通的鏈表，就在鏈表中查找，找到key相同的結點就跳出，到最後去更新值；到鏈表尾也沒有找到就在尾部插入一個新結點。接著判斷此時鏈表長度若大於8的話，還需要將鏈表轉為紅黑樹（註意在要將鏈表轉為紅黑樹之前，再進行一次判斷，若數組容量小於該值，則用resize擴容，放棄轉為紅黑樹）
get方法
get方法由getNode方法實現：
- 如果在數組下標的鏈表頭就找到key相同的，那麼返回鏈表頭的值
- 否則如果數組下標處的類型是TreeNode，就在紅黑樹中查找
- 否則就是在普通鏈表中查找了
- 都找不到就返回null
remove方法的流程大致和get方法類似。
by @sunhaiyu
2018.7.26
