摘要：不過在鏈表過長時會將其重構為紅黑樹，這樣，其最壞的時間復雜度就會降低為，這樣使得表的適應場景更廣。該節點代表一棵紅黑樹。調用紅黑樹的相關方法完成操作。同樣，和鏈表的一樣，也是將紅黑樹拆分成兩條子樹。
接上一篇博文，來吧剩下的部分寫完。
總體來說，HashMap的實現內部有兩個關鍵點，第一是當表內元素和hash桶數組的比例達到某個閾值時會觸發擴容機制，否則表中的元素會越來越擠影響性能；
第二是保存hash沖突的鏈表如果過長，就重構為紅黑樹提升性能。
關于第二點，對于HashMap來說，達到O(1)的查詢性能只是平均時間復雜度，這需要key的hash值對應的位置分布的足夠均勻。
來設想一種極端情況，假設某個黑客故意構造一組特定的數據，這些數據的hash值正好一樣。當插入hash表中時，它們的位置也一樣。
那么，這些數據會全部被組織到該位置的鏈表中，hash表退化為鏈表，這時的查詢的時間復雜度為O(N)，也是hash表查詢時間復雜度的最壞情況。
不過HashMap在鏈表過長時會將其重構為紅黑樹，這樣，其最壞的時間復雜度就會降低為O(logN)，這樣使得hash表的適應場景更廣。
resize擴容
擴容分兩個步驟：
計算擴容之后的大小。
進行具體的擴容操作。
計算擴容后大小
以下是第一個步驟的代碼：
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 已經初始化過的情況
// 對邊界情況的處理：如果hash桶數組的大小已經達到了最大值MAXINUM_CAPACITY 這里是2的30次方
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
}
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);
}
if (newThr == 0) { // =_= 邏輯好繞
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 到此，newCap是新的hash桶數組大小，newThr是新的擴容閾值
threshold = newThr;
// 分配一個新的hash桶數組，然后把舊的數據遷移過來
/* ... */
}
邏輯是這樣的，首先有三種情況，代碼寫的看起來很復雜：
hash桶數組已經初始化過。
擴容后是會溢出，也即達到了2的30次方。
擴容后不會溢出，這種情況擴容兩倍。擴容后hash桶數組的大小依然是2的冪。
hash桶數組沒有初始化過，但是指定了初始化大小。
hash桶數組沒有初始化過，也沒有指定初始化大小。
雖然邏輯很明確，但是代碼寫的看起來卻很復雜。
其原因是HashMap內部記錄的字段能表達的狀態太多，每種情況都需要考慮周全。
第一階段執行完畢后，HashMap內部的部分狀態字段被更新。
最重要的是，newCap這個變量記錄了擴容之后的大小。
執行擴容操作
final Node[] resize() {
/* ... */
// 分配一個新的hash桶數組，然后把舊的數據遷移過來
@SuppressWarnings({"rawtypes","unchecked"})
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) {
// 如果注意到hash桶數組擴容是從2^N 到 2^(N +１) 這一事實，從二進制的角度分析取余運算，就不難發現優化思路。
// 總之，這個迭代的代碼是把這條鏈表拆分成兩條，然而不同的處理邏輯。
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;
}
從思路上，總結如下：
分配一個新的hash桶數組，這是擴容后的數組。之后需要把之前的節點遷移過來。
遍歷舊的hash桶數組，在其中保存有節點時，分不同情況處理：
只有一個節點的情況，直接將這個節點rehash到新的數組中。
該節點代表一棵紅黑樹。調用紅黑樹的相關方法完成操作。
該節點代表一個鏈表。將鏈表節點rehash到新的數組中。
先來看下紅黑樹的split函數：
final void split(HashMap map, Node[] tab, int index, int bit) {
/* ... */
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
// 只是這里面有一個邏輯，即如果拆分出的樹太小，就重新轉換回鏈表
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
/* ... */
}
紅黑樹的各種操作代碼我是無心看，各種旋轉太復雜了。這里面主要有一個關鍵點，在于rehash的時候，會將紅黑樹節點也rehash。
同樣，和鏈表的rehash一樣，也是將紅黑樹拆分成兩條子樹。至于為什么是拆分為兩條后面會說。
但是，如果拆分出來的子樹太小了，就會重新將其重構回鏈表。
順便說一句，由于刪除操作的邏輯沒有什么新東西之前就沒有分析。我也沒有在其中找到刪除節點時，如果紅黑樹太小會將其重構回鏈表的操作。
rehash優化
對于鏈表的rehash操作，乍一看，這個邏輯還有些看不懂，從代碼上來看是這樣的邏輯，對于hash桶數組中第j個位置上的一個鏈表，進行遍歷，根據條件分成兩條：
(e.hash & oldCap) == 0
滿足上述條件的串成一條鏈表loHead，不滿足上述條件的串成一條鏈表hiHead。之后：
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
實際上，由于HashMap的hash桶數組的大小一定為2的冪這一性質，取余操作能夠被優化。前面也說過這一點，這里以大小為8，也即0001000為例子：
設一個2的冪次方數N，如00001000，二進制寫法中一定只有一個1.
任意一個數B余N，反映到二進制上，就是高于等于1的對應位置0，低于的保留。如00111110 % 00001000 = 00000110，前5位置0，后4位保留。
假如讓這個數余2N，不難發現，反映到二進制上，變成了前4位置0，后4為保留。
嚴謹的數學表達我實在懶得寫了，總之通過分析不難得到這個結論：
如果數B的第3位（從低位從0開始數）為0，那么B % N = B % 2N。
如果數B的第3位（從低位從0開始數）為1，那么B % N結果的第3位給置1等于B % 2N，也即B % N + N = B % 2N
有了以上結論，對照上面的代碼，也就不難理解這段rehash代碼的思路了：
(e.hash & oldCap) == 0
這句話是判斷hash值的對應位是否為0，并分成兩條不同的鏈表。
如果為0，則rehash后的位置不變。
如果不為0，則為以前的位置加上舊表的大小。
最后，我比較疑惑的一點是，花了這么大力氣去優化，為什么能得到性能或內存上的提升？
我們分析下優化前后的時間復雜度：
如果不優化，則是遍歷舊的hash桶數組，然后遍歷每一個鏈表，并且把鏈表的每個節點rehash到新的hash桶數組上去。將鏈表插入到新的數組只需O(1)的時間，也即整個操作的時間復雜度為O(N)，N為hash表中元素的個數。
如果優化，則是遍歷舊的hash桶數組，然后同樣需要遍歷每一個鏈表，把每一個節點分開到兩條不同的子鏈表上去。。。時間復雜度仍然是O(N)...
看起來兩種方案都需要遍歷所有的鏈表節點，難道僅僅是減小一點時間復雜度的常數嗎？
treeifyBin操作
之前說過當鏈表長度過大時會將其重構為紅黑樹，下面來看具體的代碼。
// 8. 把鏈表轉換成二叉樹
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
// 如果hash桶數組的大小太小還得擴容。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 所需要的hash參數是為了定位是hash桶數組中的那個鏈表，可為啥不直接傳index...
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode hd = null, tl = null;
// 遍歷單鏈表，然后把給它們一個個的分配TreeNode節點
// 看下面這代碼，這個TreeNode，記得擁有next和prev字段，看下面的代碼是把它們串成雙鏈表
do {
TreeNode p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 調用TreeNod.treeify()函數將這個已經組成雙鏈表的TreeNode節點重構成紅黑樹
hd.treeify(tab);
}
}
之前提到過TreeNode擁有next和prev字段，因此它不僅能夠用來組織紅黑樹，還能夠組織雙向鏈表。
這里看到了，這里首先將單鏈表的元素復制到TreeNode節點構成的雙向鏈表中，然后通過TreeNode的treeify方法將其組織成紅黑樹。至于這個方法。。。各種旋轉，紅黑樹的操作算法本身是很復雜的，就略過不看了。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71637.html
