最近在學習并發容器 ConcurrentHashMap，是以就先從 HashMap 開始了解。
前言
普及一下後面需要用到的一些知識：
- HashMap底層是由 數組+連結清單/紅黑樹 實作的；
- 這些數組就相當于哈希表；
-
哈希表簡單了解：
由對象的 hashCode 通過 hash 函數處理得到 hash 值，再處理 hash值 得到數組下标直接存儲（時間複雜度為 O(1)）；
-
HashMap hash函數的處理方式：
用對象的 hashCode 高16位 和 低16位 作異或混合運算；
-
處理 hash值得到數組下标的方式：
用 hash值對數組容量取模，得到數組下标；
- HashMap 大體資料結構示意圖
HashMap 源碼分析（JDK1.8）
1.重要屬性
/**
* The default initial capacity - MUST be a power of two.
* 預設數組容量為 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
* 最大數組容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
* 預設負載因子 0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
* 某個桶的連結清單結點個數大于等于 8 時,連結清單轉為紅黑樹
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
* 某個桶的紅黑樹結點個數小于等于 6時,紅黑樹轉為連結清單
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
* 在連結清單轉紅黑樹之前,需要滿足數組結點個數至少為 64,為了避免進行擴容、樹形化選擇的沖突
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
* 存放結點數組,數組大小必須為 2的幂
*/
transient Node<K,V>[] table;
/**
* The next size value at which to resize (capacity * load factor).
* 如果數組結點個數 size > threshold,數組就需要擴容
*/
int threshold;
/**
* 根據泊松分布得到
* 用于與數組容量相乘計算的數組門檻值
*/
final float loadFactor;
2.重要内部類
2.1 Node
Node是最核心的内部類，它封裝了 key-value 鍵值對，所有插入 HashMap 的資料都封裝在這個對象裡。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // key的hash值
final K key;
V value;
Node<K,V> next; // 相同hash值的 Node
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
2.2 TreeNode
紅黑樹結點，當連結清單長度過長的時候，會将 Node 轉換為 TreeNode。這個類大概寫了500多行代碼比較複雜，這裡就不着重分析，簡單說下類的成員變量。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links 父結點
TreeNode<K,V> left; // 左孩子結點
TreeNode<K,V> right; // 右孩子結點
TreeNode<K,V> prev; // 将原單連結清單變為雙向連結清單的前置指針
boolean red; // 判斷結點顔色 紅/黑
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
想深入學習 HashMap 紅黑樹的可以參考：史上最詳細的HashMap紅黑樹解析
這裡先貼一個 TreeNode 的繼承類圖：
大家考慮一個問題：為什麼 HashMap 的内部類 TreeNode 不繼承它的内部類 Node，卻繼承自 Node 的子類 LinkedHashMap.Entry？
LinkedHashMap.Entry 新增了兩個引用 before 、after，用于維護雙向連結清單。TreeNode 繼承自 LinkedHashMap.Entry 同樣也具有了組成連結清單的能力（連接配接 TreeNode 的插入順序）。但使用 HashMap 并不需要這種連結清單能力，這樣不就浪費了 2 個引用的空間。
因為我覺得這樣做是多餘的，是以這裡轉自别人的解釋：
仔細想想，也許是 Doug Lea 給開發者留下了 TreeNode 可以組成連結清單功能的想法，
開發者也可以繼承 HashMap 實作一個 TreeNode 具有 連結清單功能的集合架構。
這個問題可以參考：LinkedHashMap 源碼詳細分析（JDK1.8）
3.方法分析
接下來我們就從構造方法開始一步一步分析HashMap的擴容、添加元素等操作。
3.1 構造方法
HashMap 的構造方法有4個：
1. HashMap()
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
預設容量：16
預設負載因子：0.75
其他所有字段都是預設值
2. HashMap(int initialCapacity)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
調用了 3 的構造方法，初始容量：
initialCapacity
預設負載因子：0.75
3. HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException(
"Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(
"Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
三個判斷規定了
initialCapacity
的範圍，
threshold
通過調用
tableSizeFor(initialCapacity)
來設定（
threshold
：标志數組擴容的門檻值）
tableSizeFor(initialCapacity)
：傳回一個比
initialCapacity
大且最接近的2幂次方的整數。（比如給定10，傳回 2^4=16）
分析
tableSizeFor(int cap)
方法：
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;
}
注意：HashMap 的容量必須為 2的幂次方（後面會有解釋）
int n = cap - 1;
：為了防止 cap 已經是2的幂次方，那麼下面操作之後會變成2倍（比如 n=4已經符合要求，但經過下面5步之後 n 就會變為 8）
5步“n右移x再取或”
：保證最高位後面的位數全為1
圖解 tableSizeFor(int cap) 方法：
這裡将得到的 capacity 直接指派給了
threshold
，并不符合
threshold
的定義（capacity*loadFactor），在構造方法中并未初始化 table，table 的初始化被推遲到 put 方法中，put 方法在調用 resize 方法會重新計算
threshold
（後面會分析）。
4.HashMap(Map<? extends K, ? extends V> m)
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
構造一個和指定Map具有相同 mappings 的 HashMap，預設負載因子：0.75，裡面調用了
putMapEntries(m, false);
：将指定Map放入HashMap中。
分析
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
方法：
/**
* 将 m 的所有鍵值對存入到 HashMap執行個體中
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// m 中元素個數
int s = m.size();
// 如果 m 中存在元素
if (s > 0) {
// table 還未初始化,先儲存一些需要的變量
if (table == null) { // pre-size
// s相當于門檻值,括号中會計算得到一個容量 +1是為了向上取整
float ft = ((float)s / loadFactor) + 1.0F;
// 容量小于最大容量那麼就截斷
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 如果上面運算得到的容量 t 大于暫存容量
// threshold（table還未初始化，是以threshold存的是數組容量），
// 那麼就重新計算 threshold 暫存容量
if (t > threshold)
threshold = tableSizeFor(t);
}
// table 被初始化,s 元素個數超過門檻值 threshold,那麼就需要擴容
else if (s > threshold)
resize();
// 将 m 中的元素疊代插入 table 中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
看了上面代碼可能有人疑惑：為什麼要根據 s 來計算得到一個容量？
可以這樣分析，門檻值是比容量小的，分析 s 不當做門檻值來計算而是直接當做容量的情況：
假設暫存容量 threshold = 8、s = 7；那麼在疊代插入table，第一次調用 putVal 方法中
的 resize 方法會初始化 table（table.length = 8、threshold = 6(8*0.75)），可以發
現 7 大于門檻值，那麼在插入第7個元素時，會再次調用 resize 方法。這樣就會多調用一次
resize 方法，增加了記憶體消耗。而通過 7 作為門檻值算得的容量，則不會出現這種問題。
3.2 hash(Object key)
hash函數：用來計算 key 的 hash值。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
從代碼可以看出 key 的 hash值計算方法：
key的hash值高16位不變，低16位與高16位異或作為key的最終hash值。
那為什麼要這樣做？
這與HashMap中table下标的計算有關：
n = table.length;
index = （n-1） & hash;
在前言中我提到過，處理 hash值得到數組下标的方式：用 hash值對數組容量取模，得到數組下标。
這裡我需要将将兩點：
-
與運算對取模的優化
使用 % 取模有兩個缺點：不能處理負數（負數取模還是負數）、比較慢。
那如果我們使用與運算就會提高擷取數組下标的效率
一個hash值能大的數使用%需要計算較長時間，而通過與運算就可以一步計算出來。隻有n為2的幂次方時，減一才會使後面位數都為1，而不影響與運算的結果。這也是為什麼容量大小必須是2的幂次方的原因。 HashMap 源碼分析（JDK1.8） - 高低位異或，減少hash碰撞 由上圖可以知道隻有後四位參與了運算，如果隻是将對象的hashCode取後四位很容易産生碰撞，設計者考慮到現在的hashCode分布的已經很不錯了，而且當發生較大碰撞時也用樹形存儲降低了沖突。僅僅異或一下，既減少了系統的開銷，也不會造成的因為高位沒有參與下标的計算(table長度比較小時)，進而引起的碰撞。
HashMap 源碼分析（JDK1.8）
3.3 resize()
用于數組擴容的函數，其中也包括初始化數組。
final Node<K,V>[] resize() {
// 儲存目前 table
Node<K,V>[] oldTab = table;
// 儲存目前容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 儲存目前門檻值
int oldThr = threshold;
// 設定新的門檻值為0
int newCap, newThr = 0;
/**
* 1.在 size>threshold 時被調用
* oldCap>0 表示原table非空
* oldThr(threshold) = oldCap × load_factor
*/
if (oldCap > 0) {
// 若之前table容量超過最大容量，門檻值設為最大整型，之後不會擴容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍、門檻值翻倍，使用位運算效率高
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
/**
* 2.table 為空被調用,oldCap<=0 且 oldThr>0 表示：
* 使用者使用下面構造方法建立了 HashMap：
* HashMap(int initialCapacity, float loadFactor)
* HashMap(int initialCapacity)
* HashMap(Map<? extends K, ? extends V> m)
* oldTab = null，oldCap = 0，oldThr為使用者指定容量或m在putMapEntries
* 算得的容量
*/
else if (oldThr > 0) // initial capacity was placed in threshold
// 将暫存容量設為新的容量
newCap = oldThr;
/**
* 3.table 為空被調用,oldCap<=0 且 oldThr<=0 表示調用了預設構造
* HashMap(),oldCap=0、oldThr=0
*/
else { // zero initial threshold signifies using defaults
// 容量設為預設容量(16)
newCap = DEFAULT_INITIAL_CAPACITY;
// 門檻值設為預設門檻值計算(16*0.75)
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新門檻值為0
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"})
// 初始化新的 table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把 oldTab 中的結點 reHash 到 newTab 中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 置為null 利于GC回收
oldTab[j] = null;
// 如果為單個結點，直接在 newTab 中直到下标存儲
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果為 TreeNode 結點，就進行紅黑樹的 rehash
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 若是連結清單，進行連結清單的 rehash
else { // preserve order
// 用于連接配接索引位置不變的結點
Node<K,V> loHead = null, loTail = null;
// 用于連接配接索引位置改變的結點
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
/**
* 将同一桶的結點根據 (e.hash & oldCap) 是否為0進行分割
* 為0：繼續存在目前索引的桶中
* 不為0：存放在（索引+oldCap）的桶中
* 不了解的下面有圖解
*/
do {
next = e.next;
// 頭指針指向索引不變的第一個結點,尾指針依次将結點串聯起來
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 同上将索引改變的結點串聯起來
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 将索引不變的頭指針賦給新的數組相同索引處
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 将索引改變的頭指針賦給新的數組(索引+oldCap)處
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
在擴容中使用了 2次幂的擴充（長度翻倍），是以元素的索引位置要麼是在原位置，要麼是在原位置再移動2次幂的位置。
下圖所示，擴容前 n=2^4=16，擴容後 n=2^5=32，因為計算數組下标要減一是以圖中直接使用了n-1的位數來表示。
圖（a）表示擴容前 key1和key2 所确定的數組下标，圖（b）表示擴容後 key1和key2 所确定的數組下标：
因為n擴容翻倍，是以 n-1 的掩碼範圍增加 1bit，是以 key2的index就會發生變化：
是以，我們在擴容HashMap的時候，隻需要看原來hash值新增的一位bit是0還是1，是0的話索引不變，是1索引變為“原索引+oldCap”，可以看下 n從16擴充32 的示意圖：
什麼時候擴容：通過HashMap源碼可以看到是在put操作時，有兩處調用 resize 方法。一處是在剛進去判斷 table 是否為空，為空則擴容；另一處是在 size>threshold 來進行擴容。
擴容(resize)：其實就是重新計算容量；而這個擴容是計算出所需容器的大小之後重新定義一個新的容器，将原來容器中的元素放入其中。
3.4 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
向 HashMap 中添加元素，同時初始化 table。
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 方法初始化 table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 1.目前索引的桶沒有結點（并未hash碰撞），直接添加
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
/**
* 2.發生hash碰撞，存在兩種情況:
* 1.key值相同，需要判斷 onlyIfAbsent 來替換value值
* 2.key值不同：
* 1.存在桶的連結清單中
* 2.存在紅黑樹中
*/
else {
Node<K,V> e; K k;
// 第一個結點的hash值與将要添加元素的hash值相同且key也相同
// 那麼這個添加元素的key已經存在,用 e 暫存這個結點引用
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 2.2
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 2.1
else {
// 不是 TreeNode 就是連結清單,周遊連結清單
for (int binCount = 0; ; ++binCount) {
// 周遊完連結清單也沒有找到相同的hash和key，那麼就建立一個Node
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 因為第一個結點已經通路過，是以這裡 TREEIFY_THRESHOLD - 1
// 這裡判斷目前桶下連結清單的個數是否達到轉換為紅黑樹的條件
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 将連結清單轉為紅黑樹
treeifyBin(tab, hash);
break;
}
// 在連結清單周遊中，遇到hash和key相同的結點，e 記錄該結點引用
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果 e 記錄的結點引用不為空,那麼就存在相同hash和key的元素
if (e != null) { // existing mapping for key
// 記錄之前的value
V oldValue = e.value;
// 如果 onlyIfAbsent 為false 或 之前的value為空，就将新的value指派
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 傳回之前的value
return oldValue;
}
}
// 數組修改次數+1
++modCount;
// 數組大小+1 并判斷是否需要擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
注：hash 沖突發生的幾種情況：
1.兩節點key 值相同（hash值一定相同），導緻沖突；
2.兩節點key 值不同，由于 hash 函數的局限性導緻hash 值相同，沖突；
3.兩節點key 值不同，hash 值不同，但 hash 值對數組長度取模後相同，沖突；
get方法較為簡單，這裡就不在贅述。
4.JDK1.7和JDK1.8的比較
（1）JDK1.7用的是頭插法，而JDK1.8及之後使用的都是尾插法，那麼為什麼要這樣做呢？因為JDK1.7是用單連結清單進行的縱向延伸，當采用頭插法就是能夠提高插入的效率，但是也會容易出現逆序且環形連結清單死循環問題。但是在JDK1.8之後是因為加入了紅黑樹使用尾插法，能夠避免出現逆序且連結清單死循環的問題。
（2）擴容後資料存儲位置的計算方式也不一樣：
- 在JDK1.7的時候是直接用hash值和需要擴容的二進制數進行&（這裡就是為什麼擴容的時候為啥一定必須是2的多少次幂的原因所在，因為如果隻有2的n次幂的情況時減一之後，最後幾位二進制數才一定是1，這樣能最大程度減少hash碰撞）（hash值 & length-1） 。
- 在JDK1.8的時候直接用了JDK1.7的時候計算的規律，也就是擴容前的原始位置+擴容的大小值=JDK1.8的計算方式，而不再是JDK1.7的那種異或的方法。但是這種方式就相當于隻需要判斷Hash值的新增參與運算的位是0還是1就直接迅速計算出了擴容後的儲存方式。
（3）JDK1.7的時候使用的是數組+ 單連結清單的資料結構。但是在JDK1.8及之後時，使用的是數組+連結清單+紅黑樹的資料結構（當連結清單的深度達到8的時候，也就是預設門檻值，就會自動擴容把連結清單轉成紅黑樹的資料結構來把時間複雜度從O（N）變成O（logN）提高了效率）。