我們知道在Java 8中對于HashMap引入了紅黑樹進而提高操作性能，由于在上一節我們已經通過圖解方式分析了紅黑樹原理，是以在接下來我們将更多精力投入到解析原理而不是算法本身，HashMap在Java中是使用比較頻繁的鍵值對資料類型，是以我們非常有必要詳細去分析背後的具體實作原理，無論是C#還是Java原了解析，從不打算一行行代碼解釋，我認為最重要的是設計思路，重要的地方可能會多啰嗦兩句。
HashMap原理分析
我們由淺入深，循序漸進，首先了解下在HashMap中定義的幾個屬性，稍後會進一步講解為何要定義這個值，難道是靠拍腦袋嗎。
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable {
//預設初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//預設負載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//連結清單轉紅黑樹門檻值
static final int TREEIFY_THRESHOLD = 8;
//取消門檻值
static final int UNTREEIFY_THRESHOLD = 6;
//最小樹容量
static final int MIN_TREEIFY_CAPACITY = 64;
}
構造函數分析
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
} 當執行個體化HashMap時，我們不指定任何參數，此時定義負載因子為0.75f
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR); 當執行個體化HashMap時，我們也可以指定初始化容量，此時預設負載因子仍為0.75f。
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);
} 當執行個體化HashMap時，我們既指定預設初始化容量，也可指定負載因子，很顯然初始化容量不能小于0，否則抛出異常，若初始化容量超過定義的最大容量，則将定義的最大容量指派與初始化容量，對于負載因子不能小于或等于0，否則抛出異常。接下來根據提供的初始化容量設定門檻值，我們接下來看看上述tableSizeFor方法實作。
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; 這個方法是在做什麼處理呢？門檻值 = 2的次幂大于初始化容量的最小值。 到學習java目前為止，我們接觸到了模運算【%】、按位左移【<<】、按位右移【>>】，這裡我們将學習到按位或運算【|】、無符号按位右移【>>>】。按位或運算就是二進制有1，結果就為1，否則為0，而無符号按位右移隻是高位無正負之分而已。不要看到上述【n | = n >>> 1】一臉懵，實際上就是【n = n | n >>> 1】，和我們正常進行四則運算一個道理，隻不過是邏輯運算和位運算符号不同而已罷了。我們通過如下例子來說明上述結論，假設初始化容量為5，接下來我們進行如上運算。
0000 0000 0000 0000 0000 0000 0000 0101 cap = 5
0000 0000 0000 0000 0000 0000 0000 0100 n = cap - 1
0000 0000 0000 0000 0000 0000 0000 0010 n >>> 1
0000 0000 0000 0000 0000 0000 0000 0110 n |= n >>> 1
0000 0000 0000 0000 0000 0000 0000 0001 n >>> 2
0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 2
0000 0000 0000 0000 0000 0000 0000 0000 n >>> 4
0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 4
0000 0000 0000 0000 0000 0000 0000 0000 n >>> 8
0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 8
0000 0000 0000 0000 0000 0000 0000 0000 n >>> 16
0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 16
如上最終算出來結果為7，然後加上最初計算時減去的1，是以對于初始化容量為5的最小2次幂為8，也就是門檻值為8，要是初始化容量為8，那麼門檻值也為8。接下來到了我們的重點插入操作。
插入原理分析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true); 上述插入操作簡短一行代碼，隻不過是調用了putVal方法，但是我們注意到首先計算了鍵的哈希值，我們看看該方法實作。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 直接了解方法大意是：若傳入的鍵為空，則哈希值為0，否則直接調用鍵的本地hashCode方法擷取哈希值，然後對其按位向右移16位，最後進行按位異或（隻要不同結果就為1）操作。好像還是不懂，我們暫且擱置一下，我們繼續看看插入方法具體實作。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// 步驟【1】：tab為空擴容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步驟【2】：計算index，并對null做處理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
// 步驟【3】：鍵存在，直接覆寫值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步驟【4】：若為紅黑樹
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// 步驟【5】：若為連結清單
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//若連結清單長度大于8則轉換為紅黑樹進行處理
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步驟【6】：超過最大容量進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 我們首先來看來步驟【2】，我們待會再來看步驟【1】實作，我們首先摘抄上述擷取鍵的索引邏輯
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); 上述通過計算出鍵的哈希值并與數組的長度按位與運算，雜湊演算法直接決定鍵的存儲是否分布均勻，否則會發生沖突或碰撞，嚴重影響性能，是以上述【 (n - 1) & hash 】是發生碰撞的關鍵所在，難道我們直接調用鍵的本地hashCode方法擷取哈希值不就可以了嗎，肯定是不可以的，我們來看一個例子。假設我們通過調用本地的hashCode方法，擷取幾個鍵的哈希值為31、63、95，同時預設初始化容量為16。然後調用（n-1 & hash），計算如下：
0000 0000 0000 0000 0000 0000 0001 1111 hash = 31
0000 0000 0000 0000 0000 0000 0000 1111 n - 1
0000 0000 0000 0000 0000 0000 0000 1111 => 15
0000 0000 0000 0000 0000 0000 0011 1111 hash = 63
0000 0000 0000 0000 0000 0000 0111 1111 hash = 95
因為（2 ^ n-1）的低位始終都是1，再按照按位運算（0-1始終為0）所有最終結果都有1111，這就是為什麼傳回相同索引的原因，是以，盡管我們具有不同的哈希值，但結果卻是存儲到哈希桶數組相同索引位置。是以為了解決低位根本就沒有參與到運算中的問題：通過調用上述hash方法，按位右移16位并異或，解決因低位沒有參與運算導緻沖突，提高性能。我們繼續回到上述步驟【1】，當數組為空，内部是如何進行擴容的呢？我們來看看resize方法實作。
final Node[] resize() {
Node[] 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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
......
} 由上可知：當執行個體化HashMap并無參時，此時預設初始化容量為16，預設門檻值為12，負載因子為0.75f，當指定參數（初始化容量比如為5），此時初始化容量為8，門檻值為8，負載因子為0.75f。否則也指定了負載因子，則以指定負載因子為準。同時當超過容量時，擴容後的容量為原容量的2倍。到這裡我們發現一個問題：hashTable中的容量可為奇或偶數，而HashMap中的容量永遠都為2的次幂即偶數，為何要這樣設計呢？
int index = (n - 1) & hash;
如上為HashMap計算在哈希桶數組中的索引位置，若HashMap中的容量不為2的次幂，此時通過按與運算，索引隻能為16或0，這也就意味着将發生更多沖突，也将導緻性能很差，本可通過O(1)進行檢索，現在需要O(log n)，因為發生沖突時，給定存儲桶中的所有節點都将存儲在紅黑樹中，若容量為2的次幂，此時按與運算符将和hashTable中計算索引存儲位置的方式等同，如下：
int index = (hash & 0x7FFFFFFF) % tab.length;
按照HashMap計算索引的方式，當我們從2的次幂中減去1時，得到的是一個二進制末位全為1的數字，例如預設初始化容量為16，如果從中減去1，則得到15，其二進制表示形式是1111，此時如果對1111進行任意數字的按位與運算，我們将得到整數的最後4位，換句話說，等價于對16取模，但是除法運算通常是昂貴的運算，也就是說按位運算比取模運算效率更高。到此我們知道HashMap中容量為2的次幂的原因在于：哈希桶數組索引存儲采取按位運算而非取模運算，因其效率比取模運算更高。進行完上述擴容後容量、門檻值重新計算後，接下來則需要對哈希桶數組重新哈希(rehash)，請繼續往下看。
影響HashMap性能因素分析
在講解上述重新哈希之前，我們需要重頭開始進行叙述，直到這裡，我們知道HashMap預設初始化容量為16，假如我們有16個元素放入到HashMap中，如果實作了很好的雜湊演算法，那麼在哈希桶數組中将在每個存儲桶中放入1個元素，在此種情況下，查找元素僅需要1次，如果是HashMap中有256元素，如果實作了很好的雜湊演算法，那麼在哈希桶數組中将在每個存儲桶中放入16個元素，同理，在此種情況下，查找任何一個元素，最多也隻需要16次，到這裡我們可以知道，如果HashMap中的哈希桶數組存儲的元素增加一倍或幾倍，那麼在每個存儲桶中查找元素的最大時間成本并不會很大，但是，如果持續維持預設容量即16不變，如果每個存儲桶中有大量元素，此時，HashMap的映射性能将開始下降。比如現在HashMap中有一千六百萬條資料，如果實作了很好的雜湊演算法，将在每個存儲桶中配置設定一百萬個元素，也就是說，查找任意元素，最多需要查找一百萬次。很顯然，我們将存儲的元素放大後，将嚴重影響HashMap性能，那麼對此我們有何解決方案呢？讓我們回到最初的話題，因為預設存儲桶大小為16且當存儲的元素條目少時，HashMap性能并未有什麼改變，但是當存儲桶的數量持續增加時，将影響HashMap性能，這是由于什麼原因導緻的呢？主要是我們一直在維持容量固定不變，我們卻一直增加HashMap中哈希桶數組中存儲元素的大小，這完全影響到了時間複雜度。如果我們增加存儲桶大小，則當每個存儲桶中的總項開始增加時，我們将能夠使得每個存儲桶中的元素個數保持恒定，并對于查詢和插入操作保持O(1)的時間複雜度。那麼增加存儲桶大小也就是容量的時機是什麼時候呢？存儲桶的大小（容量）由負載因子決定，負載因子是一種度量，它決定着何時增加存儲桶的大小（容量），以便針對查詢和插入操作保持O(1)的時間複雜度，是以，何時增加容量的大小取決于乘積（初始化容量 負載因子），是以容量和負載因子是影響HashMap性能的根本因素。我們知道預設負載因子是0.75，也就是百分之75，是以增加容量大小的值為（16 0.75）= 12，這個值我們稱之為門檻值，也就意味着，在HashMap中存儲直到第12個鍵值對時，都将保持容量為16，等到第13個鍵值對插入到HashMap中時，其容量大小将由預設的16變為（ 16 * 2）= 32。通過上述計算增加容量大小即門檻值的公式，我們從反向角度思考：負載因子比率 = 哈希桶數組中元素個數 / 哈希桶數組桶大小，舉個栗子，若預設桶大小為16，當插入第一個元素時，其負載因子比率 = 1 / 16 = 0.0625 > 0.75 嗎？若為否無需增加容量，當插入第13個元素時，其負載因子比率 = 13 / 16 = 0.81 > 0.75嗎？若為是則需增加容量。講完這裡，我們再來看看重哈希，在講解為什麼要進行重哈希之前，我們需要了解重哈希的概念：重新計算已存儲在哈希桶數組中元素的哈希碼的過程，當達到門檻值時，将其移動到另外一個更大的哈希桶數組中。當存儲到哈希桶數組中的元素超過了負載因子的限制時，此時将容量增加一倍并進行重哈希。那麼為何要進行重哈希呢？因為容量增加一倍後，如若不處理已存在于哈希桶數組中鍵值對，那麼将容量增加一倍則沒有任何意義，同時呢，也是為了保持每一個存儲桶中元素保持均勻分布，因為隻有将元素均勻的分布到每一個存儲桶中才能實作O(1)時間複雜度。接下來我們繼續進行重哈希源碼分析
重哈希源碼分析
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
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;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} 從整體上分析擴容後進行重哈希分為三種情況： ① 哈希桶數組元素為非連結清單即數組中隻存在一個元素 ②哈希桶數組元素為紅黑樹進行轉換 ③哈希桶數組元素為連結清單。關于①②情況就不用我再叙述，我們接下來重點看看對連結清單的優化處理。也就是如下這一段代碼：
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
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;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
} 看到上述代碼我們不禁疑惑為貌似聲明了兩個連結清單，一個低位連結清單（lower），一個高位連結清單（high），我們暫且不是很了解哈，接下來我們進入 do {} while () 循環，然後重點來了這麼一句 e.hash & oldCap == 0 ，這是幹啥玩意，根據此行代碼來分别進入到低位連結清單和高位連結清單。好了，我們通過一例子就很好了解了：假設按照預設初始化容量為16，然後我們插入一個為21的元素，根據我們上面的叙述，首先計算出哈希值，然後計算出索引位置，為了便于很直覺的了解，我們還是一步步來計算下。
static final int hash(21) {
int h;
return (21 == null) ? 0 : (h = 21.hashCode()) ^ (h >>> 16); 調用如上hash方法計算出鍵21的值仍為21，接下來通過如下按與運算計算出存儲到哈希桶數組中的索引位置。
i = (16 - 1) & 21
最終我們計算其索引位置即i等于5，因為初始化容量為16，此時門檻值為12，當插入第13個元素開始進行擴容，容量變為32，此時若再次按照上述方式計算索引存儲位置為 i = (32 - 1) & 21 ，結果為21。從這裡我們得出結論：當容量為16時，插入元素21的索引位置為5，而擴容後容量為32，此時插入元素21的索引位置為21，也就是說【擴容後的新的索引 = 原有索引 + 原有容量】。同理，若插入元素為5，容量為16，那麼索引位置為5，若擴容後容量為32，索引位置同樣也為5，也就是說【擴容後的索引 = 原有索引】。因為容量始終為原有容量的2倍（比如16到32即從0000 0000 0000 0000 0000 0000 0001 0000 =》0000 0000 0000 0000 0000 0000 0010 0000）從按位考慮則是高位由0變為1，也就是說我們通過計算出元素的哈希值與原有容量按位與運算，若結果等于0，則擴容後索引等于原索引，否則等于原有索引加上原有容量，也就是通過哈希值與原容量按位與運算即 e.hash & oldCap == 0 來判斷新索引位置是否發生了改變，說的更加通俗易懂一點，比如（5 & 16 = 0），那麼元素5擴容後的索引位置為【新索引 = 原索引 + 0】，同理比如（21 & 16 = 16），那麼元素21的擴容後的索引位置為【新索引 = 原索引 + 16】。由于容量始終為2次幂，如此而節省了之前版本而重新計算哈希的時間進而達到優化。到這裡，我們可以進一步總結出容量始終為2次幂的意義：①哈希桶數組索引存儲采取按位運算而非取模運算，因其效率比取模運算更高 ②優化重新計算哈希而節省時間。最終将索引不變連結清單即低位連結清單和索引改變連結清單即高位連結清單分别放入擴容後新的哈希桶數組中，最終重新哈希過程到此結束。接下來我們分析将元素如何放入到紅黑樹中的呢？
将值插入紅黑樹保持樹平衡
// 步驟【4】：若為紅黑樹
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); 然後我們看看上述将值放入到紅黑樹中具體方法實作，如下：
final TreeNode putTreeVal(HashMap map, Node[] tab,
int h, K k, V v) {
Class kc = null;
boolean searched = false;
TreeNode root = (parent != null) ? root() : this;
for (TreeNode p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node xpn = xp.next;
TreeNode x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
} 我們需要思考的是：（1）待插入元素在紅黑樹中的具體位置是在哪裡呢？（2）找到插入具體位置後，然後需要知道的到底是左邊還是右邊呢？。我們按照正常思路了解的話還是非常容易想明白，我們從根節點開始周遊樹，通過每一個節點的哈希值與待插入節點哈希值比較，若待插入元素位于其父節點的左邊，則看父節點的左邊是否已存在元素，如果不存在則将其父節點的左邊節點留給待插入節點，同理對于父節點的右邊也是如此，但是如果父節點的左邊和右邊都有其引用，那麼就繼續周遊，直到找到待插入節點的具體位置。這就是我們在寫代碼或進行代碼測試時的一般思路，但是我們還要考慮邊界問題，否則說明考慮不完全，針對待插入元素插入到紅黑樹中的邊界問題是什麼呢？當周遊的節點和待插入節點的哈希值相等，那麼此時我們應該确定元素的順序來保持樹的平衡呢？也就是上述中的如下代碼：
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
} 為了解決将元素插入到紅黑樹中，如何确定元素順序的問題。通過兩種方案來解決：①實作Comprable接口 ②突破僵局機制。接下來我們來看實作Comprable例子，如下：
public class PersonComparable implements Comparable {
int age;
public PersonComparable(int age) {
this.age = age;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj instanceof PersonComparable) {
PersonComparable p = (PersonComparable) obj;
return (this.age == p.age);
}
return false;
}
@Override
public int hashCode() {
return 42;
}
@Override
public int compareTo(PersonComparable o) {
return this.age - o.age;
} 然後我們在控制台中，調用如下代碼進行測試：
HashMap hashMap = new HashMap();
Person p1 = new Person(1);
Person p2 = new Person(2);
Person p3 = new Person(3);
Person p4 = new Person(4);
Person p5 = new Person(5);
Person p6 = new Person(6);
Person p7 = new Person(7);
Person p8 = new Person(8);
Person p9 = new Person(9);
Person p10 = new Person(10);
Person p11 = new Person(11);
Person p12 = new Person(12);
Person p13 = new Person(13);
hashMap.put(p1, "1");
hashMap.put(p2, "2");
hashMap.put(p3, "3");
hashMap.put(p4, "4");
hashMap.put(p5, "5");
hashMap.put(p6, "6");
hashMap.put(p7, "7");
hashMap.put(p8, "8");
hashMap.put(p9, "9");
hashMap.put(p10, "10");
hashMap.put(p11, "11");
hashMap.put(p12, "12");
hashMap.put(p13, "13"); 反觀上述代碼，我們實作了Comprable接口并且直接重寫了hashcode為常量值，此時将産生沖突，插入到HashMap中每一個元素的哈希值都相等即索引位置一樣，也就是最終将由連結清單轉換為紅黑樹，既然哈希值一樣，那麼我們如何确定其順序呢？，此時我們回到上述 comparableClassFor 方法和 compareComparables 方法（二者具體實作就不一一解釋了）
// 若實作Comparable接口傳回其具體實作類型，否則傳回空
static Class comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
} //調用自定義實作Comprable接口比較器，進而确定順序
static int compareComparables(Class kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
} 但是要是上述我們實作的Person類沒有實作Comprable接口，此時将使用突破僵局機制（我猜測作者對此方法的命名是否是來自于維基百科《
https://en.wikipedia.org/wiki/Tiebreaker》，比較貼切【突破僵局制（英語：tiebreaker），是一種延長賽的制度，主要用于棒球與壘球運動，特别是采淘汰制的季後賽及國際賽，以避免比賽時間過久仍無法分出勝負。】），也就是對應如下代碼：
dir = tieBreakOrder(k, pk);
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
} 因為哈希值相等，同時也沒有實作Comparable接口，但是我們又不得不解決這樣實際存在的問題，可以說是最終采取“迫不得已“的解決方案，通過調用上述 System.identityHashCode 來擷取對象唯一且恒定的哈希值進而确定順序。好了，那麼問題來了對于實作Comparable接口的鍵插入到樹中和未實作接口的鍵插入到樹中，二者有何差別呢？如果鍵實作Comparable接口，查找指定元素将會使用樹特性快速查找，如果鍵未實作Comparable接口，查找到指定元素将會使用周遊樹方式查找。問題又來了，既然通過實作Comparable接口的比較器來确定順序，那為何不直接使用突破僵局機制來作為比較器？我們來看看那如下例子：
Person person1 = new Person(1);
Person person2 = new Person(1);
System.out.println(System.identityHashCode(person1) == System.identityHashCode(person2));
到這裡我們知道，即使是兩個相同的對象執行個體其identityHashCode都是不同的，是以不能使用identityHashCode作為比較器。問題又來了，既然使用identityHashCode确定元素順序，當查找元素時是采用周遊樹的方式，完全沒有利用到樹的特性，那麼為何還要構造樹呢？因為HashMap能夠包含不同對象執行個體的鍵，有些可能實作了Comparable接口，有些可能未實作。我們來看如下混合不同類例子：
public class Person {
int age;
public Person(int age) {
this.age = age;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj instanceof Person) {
Person p = (Person) obj;
return (this.age == p.age);
}
return false;
}
@Override
public int hashCode() {
return 42;
} HashMap hashMap = new HashMap();
PersonComparable p1 = new PersonComparable (1);
PersonComparable p2 = new PersonComparable (2);
PersonComparable p3 = new PersonComparable (3);
PersonComparable p4 = new PersonComparable (4);
PersonComparable p5 = new PersonComparable (5);
PersonComparable p6 = new PersonComparable (6);
Person p7 = new Person(7);
Person p8 = new Person(8);
Person p9 = new Person(9);
Person p10 = new Person(10);
Person p11 = new Person(11);
Person p12 = new Person(12);
Person p13 = new Person(13);
hashMap.put(p1, "1");
hashMap.put(p2, "2");
hashMap.put(p3, "3");
hashMap.put(p4, "4");
hashMap.put(p5, "5");
hashMap.put(p6, "6");
hashMap.put(p7, "7");
hashMap.put(p8, "8");
hashMap.put(p9, "9");
hashMap.put(p10, "10");
hashMap.put(p11, "11");
hashMap.put(p12, "12");
hashMap.put(p13, "13");
當使用混合模式時即實作了Comparable接口和未實作Comparable接口的對象執行個體可以基于類名來比較鍵。
總結
本節我們詳細講解了HashMap實作原理細節，一些比較簡單的地方就沒有再一一分析，文中若有叙述不當或了解錯誤之處，還望指正，感謝您的閱讀
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)