目錄
- 一.Collection集合體系
-
- ①.List集合
-
- 1.1 ArrayList底層原理
-
- 1.1.1 單個存儲
- 1.1.2 多個存儲
- 1.2 LinkedList底層原理
- ②.Collection周遊方式
-
- 2.1 疊代器周遊
- 2.2 增強for周遊
- 2.3 Lambda表達式周遊
- 2.4 疊代器源碼分析
- ③.Set集合
-
- 3.1 HashSet
-
- 3.1.1 HashSet底層結構
- 3.1.2 HashSet存儲原理
- 3.1.3 HashSet三個疑惑
- 3.2 LinkedHashSet
- 3.3 TreeSet
-
- 3.3.1 排序規則
- 3.3.2 預設排序/自然排序
- 3.3.3 比較器排序/定制排序
- ④.集合工具類Collections
- ⑤.Collection集合總結
- 二.Map集合體系
-
- 1. HashMap
- 2. HashMap底層源碼解析
- 3. TreeMap
- 4. TreeMap底層源碼解析
- 5. Map結合總結與思考
前言：這些底層原理的圖畫的可能不太清晰，但整體流程是完善出來了，多多琢磨，定會霍然開朗。因為個人能力有限，不足之處望諸位多多包涵，也歡迎您的補充與指正，最後感謝您的閱覽，也希望您能有所收獲
一.Collection集合體系
Collection是單列集合的祖宗接口，它的功能是全部單列集合都可以繼承使用的。
Collection常用方法如下
注意
因為contains方法在底層依賴equals方法判斷對象是否一緻的。
如果存的是自定義對象（如student），沒有重寫equals方法，那麼預設使用object類中的equals方法進行判斷，而object類中equals方法，依賴位址值進行判斷.需求:如果同姓名和同年齡，就認為是同一個學生。
是以，需要在自定義的Javabean類中，重寫equals方法就可以了。
①.List集合
List系列集合：添加元素是有序（存和取順序一緻），可重複，有索引的
由于List集合有索引，是以出來Collection的共性方法外，還有多了一些索引操作的方法
下面是根據索引的增，删，改，查四個方法
細節注意
使用指定索引插入方法，原來索引上的元素依次向後移
使用指定索引删除方法，會将被删除元素作為傳回
使用指定索引修改方法，會将被修改元素作為傳回
1.1 ArrayList底層原理
JDK7：初始化時，底層建立長度為10的數組
JDK8：初始化建立一個空數組，沒有長度，隻有調用add時才建立長度為10的數組
1.1.1 單個存儲
elementData是它底層數組的名稱
當存滿後，自動擴容為原數組的1.5倍，再将原數組的内容拷貝到新數組中
起始建立時，數組容量為0，添加第一個元素，數組初始化容量為10，源碼調用邏輯如下圖，注：這是JDK11的底層源碼和JDK8不一樣
下面是添加第一個元素，數組初始化容量為10的，調用過程
1.1.2 多個存儲
如果一次添加多個資料，數組放不下，則新建立數組以實際長度為準，比如新添加100個元素，新數組的長度就是100
數組擴容的兩種情況
一. 單個單個元素增加時擴容為之前的1.5倍（數組右移一位就是除以2，新增的容量為之前的一半，那合起來就是1.5倍）
二. 多個元素一起添加，addAll的情況，數組擴容為實際要存放的元素的總數量，例如之前初始化容量為10，添加100個元素，這時數組長度為110
以下是數組容量為10，添加第11個元素源碼調用及一次添加100個元素詳細過程解析
1.2 LinkedList底層原理
與ArrayList底層為數組不同，LinkedList底層是一個雙向清單結構，秉承清單特點，查詢慢，增删快
底層源碼調用
最終雙向連結清單形成的結果圖
②.Collection周遊方式
由于Colllectino集合下的set集合沒有索引，是以不能再用以前的for循環周遊了，下面是提供的三種周遊方式
2.1 疊代器周遊
疊代器不依賴索引，疊代器是集合專用的周遊方式
細節注意點:
1，如果疊代器指針已周遊到最後，再次調用next()方法擷取元素，會報錯NoSuchElementException
2，疊代器周遊完畢，指針不會複位；如果要把該集合再次周遊一遍，隻能重新擷取一個新的疊代器對象
3，循環中隻能用一次next方法；next方法執行的是擷取元素，移動指針，如果循環體内再來一個it.next()，一次循環中指針會後移兩次，最後會報NoSuchElementException（沒有這個元素異常）
4，疊代器周遊時，不能用集合的方法進行增加或者删除；如果使用了集合的方法，會報并發修改異常，詳細見下面疊代器源碼分析位置
便于周遊過程中删除元素，用疊代器的删除方法
2.2 增強for周遊
增強for的底層就是疊代器，為了簡化疊代器代碼書寫的
所有的單列集合和數組才能用增強for進行周遊
注意細節：
修改增強for中的變量，不會改變集合中原本的資料。
2.3 Lambda表達式周遊
得益于JDK8開始的新技術Lambda表達式，提供了一種更簡單、更直接的周遊集合的方式。
例如下
2.4 疊代器源碼分析
疊代器回顧
疊代器源碼調用分析
調用解析
并發修改異常原理
結論
在以後如何避免并發修改異常
在使用疊代器或者是增強for周遊集合的過程中，不要使用集合的方法去添加或者删除元素即可。
③.Set集合
Set系列集合：添加的元素是無序（存和取的順序不一緻），不重複（常用來去重），無索引（不能根據索引擷取元素）
set集合下的所有實作類底層，都是new了一個map對象
3.1 HashSet
使用格式如下（泛型不是一定的），它的api方法就是Collection的共性方法
3.1.1 HashSet底層結構
- HashSet集合底層采取哈希表存儲資料
- 哈希表是一種對于增删改查資料性能都較好的結構
而哈希表的組成
JDK8之前: 數組 + 連結清單
JDK8開始 :數組 + 連結清單 + 紅黑樹
哈希值，哈希表靈魂所在
哈希值就是對象的整數表現形式
哈希表底層是以數組存在的，它并不是從0索引開始的，依次往後存儲的，而是依據下面的公式，算出得到存儲的索引
int index =（數組長度-1）&哈希值;
哈希值概念
- 根據hashcode方法算出來的int類型的整數
- 該方法定義在Object類中，所有對象都可以調用，預設使用位址值進行計算
- 一般情況下，會重寫hashCode方法，利用對象内部的屬性值計算哈希值
對象的哈希值特點
- 如果沒有重寫hashCode方法，不同對象計算出的哈希值是不同的（因為對象位址值不可能一樣）
- 如果已經重寫hashcode方法，不同的對象隻要屬性值相同，計算出的哈希值就是一樣的
- 在小部分情況下，不同的屬性值或者不同的位址值計算出來的哈希值也有可能一樣。(哈希碰撞)
3.1.2 HashSet存儲原理
int index =（數組長度-1）&哈希值;
擴容方式
①當存入了16*0.75（預設加載因子）=12個元素後，數組就會擴容為原來的兩倍，比如上面例子就是擴容到32
②當連結清單長度大于8而且數組長度大于等于64時，目前連結清單就會自動轉為紅黑樹，提高查找效率
注意
如果集合中存儲的是自定義對象，必須要重寫hashCode和equals方法（和重寫getset方法方式一樣），不重寫比較的就是位址值，這樣導緻即使建立兩個屬性相同的對象，也可以存入set集合中。
而String，Integer這些不需要重寫，因為這些類java底層已經重寫好了
3.1.3 HashSet三個疑惑
1.為什麼HashSet存和取的順序不一樣
HashSet周遊是從數組0下标開始的，但是HashSet存入是按數組長度和哈希值的計算公式得到存儲的位置，可以說是存入即無序，那麼按順序周遊，自然不會有序。
2.為什麼HashSet沒有索引
因為HashSet底層結構就是數組+連結清單+紅黑樹，使用索引顯然不太合适，不能說一個索引下還挂着一串連結清單，這怎麼用索引表示
3.HashSet利用什麼機制保證資料去重
這裡依靠兩個方法，一個是HashCode方法，一個是equals方法
通過HashCode方法計算出哈希值，通過equals方法判斷屬性是否相同，上面底層存儲原理已經說明過了，若相同則不存儲
3.2 LinkedHashSet
LinkedHashSet：有序，不重複，無索引
原理∶底層資料結構是依然哈希表，隻是每個元素又額外的多了一個雙連結清單的機制記錄存儲的順序。
有序原因如下
周遊的時候就不會從數組的0索引開始，而是根據第一個存入元素的雙向連結清單來周遊
3.3 TreeSet
- 不重複、無索引、可排序
- 可排序:按照元素的預設規則(有小到大)排序。
- TreeSet集合底層是基于紅黑樹的資料結構實作排序的，增删改查性能都較好。
3.3.1 排序規則
- 對于數值類型:Integer , Double，預設按照從小到大的順序進行排序。
- 對于字元、字元串類型:按照字元在ASCII碼表中的數字升序進行排序。比較過程中隻要有一個字元能确定大小關系，後面字母就不會再看了（不是和起來比大小）
注意添加自定義對象時，需要自己指定比較規則
3.3.2 預設排序/自然排序
javabean類實作Comparable接口，重寫裡面的抽象方法，再指定比較規則
如下
傳回值:
負數:認為要添加的元素是小的，存左邊
正數:認為要添加的元素是大的，存右邊
0:認為要添加的元素已經存在，舍棄
注意這個o不是固定的，代指目前元素需要對比的元素，比如存入一個23，o開始是代表25，比完後放左邊，左邊有了24，又要和24比，這是o代表24。插入元素的同時也要注意紅黑規則，不滿足紅黑規則就需要按照添加規則表來操作旋轉。
這裡添加元素，如果違背了紅黑樹的紅黑規則，就需要對照紅黑樹添加規則表來操作，不然很迷糊
位址：
紅黑樹添加規則表
3.3.3 比較器排序/定制排序
比較器排序:建立TreeSet對象時候，傳遞比較器Comparator指定規則
使用原則:預設使用第一種，如果第一種不能滿足目前需求，就使用第二種
下面是指定先按長度排序，一樣再按首字母排序範例
TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
//按照長度排序
int i = o1.length() - o2.length();
//如果一樣長則按照首字母排序
i = i == 0 ? o1.compareTo(o2) : i;
return i;
}
});
i = i == 0 ? o1.compareTo(o2) : i;
這裡用了三位運算和鍊式程式設計，把最後的結果指派給i
④.集合工具類Collections
常用api如下
使用格式如下
⑤.Collection集合總結
二.Map集合體系
map集合是一種雙列集合
雙列集合的特點
①雙列集合一次需要存一對資料，分别為鍵和值
②鍵不能重複，值可以重複
③鍵和值是一 一對應的，每一個鍵隻能找到自己對應的值
④鍵＋值這個整體我們稱之為“鍵值對”或者“鍵值對對象”，在Java中叫做“Entry對象”
Map集合常見的API（共性方法）
put方法細節處
- 在添加資料的時候，如果鍵不存在，那麼直接把鍵值對對象添加到map集合當中,方法傳回null
- 在添加資料的時候，如果鍵是存在的，那麼會把原有的鍵值對對象覆寫，會把被覆寫的值進行傳回。
①map集合周遊鍵值方式之一（鍵找值），for循環周遊（疊代器也可以下面隻是示例）
周遊方式，把key放入單列集合，根據周遊的key，利用map集合中的鍵擷取對應值得規則，周遊key，value
Set<String> set = map.keySet();
for (String key : set) {
String value = map.get(key);
System.out.println(key+"="+value);
}
②map集合周遊鍵值方式之二（鍵值對），通過一個方法擷取所有的鍵值對對象，傳回一個set集合，周遊entrySet 這個集合，去得到裡面的每一個鍵值對對象
Set<Map.Entry<String, String>> entrySet = map.entrySet();
for (Map.Entry<String, String> entry : entrySet) {
String key = entry.getKey();
String value = entry.getValue();
System.out.println(key+"="+value);
}
③map集合周遊鍵值方式之三（Lambda表達式）
底層:|
forEach其實就是利用第二種方式進行周遊，依次得到每一個鍵和值再調用accept方法
下面分别是匿名對象和lambda方式來周遊
map.forEach(new BiConsumer<String, String>() {
public void accept(String key, String value) {
System.out.println(key+"="+value);
}
});
map.forEach((String key, String value)->{
System.out.println(key+"="+value);
});
1. HashMap
特點都是由鍵決定的:無序、不重複、無索引
HashMap跟HashSet底層原理是一模一樣的，都是哈希表結構（數組+連結清單+紅黑樹）
但是有一個差別，HashSet添加元素，一樣的不存，而HashMap添加元素，相同的覆寫，這就是為什麼map的put方法存入key相同時，覆寫之前的value
其餘的和HashSet差不多，存儲位置相同時，JDK7新元素存數組，老元素挂新元素下面，JDK8以後，新元素直接挂老元素下面就完了。當連結清單長度超過8且數組長度大于等于64時，連結清單自動轉化成紅黑樹
總結
- HashMap底層是哈希表結構的
- 依賴hashcode方法和equals方法保證鍵的唯一
- 如果鍵存儲的是自定義對象，需要重寫hashCode和equals方法；如果值存儲自定義對象，不需要重寫hashCode和equals方法
2. HashMap底層源碼解析
由于檢視源碼，需要不斷跟進，轉換頁面很多，也不連貫，文字描述想要讓人看懂是很難的，我自認為我沒有用文字全面解析底層源碼的能力，文字描述還能讓人意會邏輯我也不知道如何去寫
不如看看視訊解析，視訊連貫且清晰，邏輯更容易明悟。位址：阿玮老師講的超贊的
屬性，方法解釋分析
1.看源碼之前需要了解的一些内容
Node<K,V>[] table 哈希表結構中數組的名字 HashMap底層結構是哈希表， 而哈希表在JDK8以後是有數組+連結清單+紅黑樹構成
DEFAULT_INITIAL_CAPACITY： 數組預設長度16
DEFAULT_LOAD_FACTOR： 預設加載因子0.75
HashMap裡面每一個對象包含以下内容：
1.1 連結清單中的鍵值對對象 ——entry對象
包含：
int hash; //鍵的哈希值
final K key; //鍵
V value; //值
Node<K,V> next; //下一個節點的位址值 這個是存儲位置相同，下挂連結清單的情況
1.2 紅黑樹中的鍵值對對象
包含：
int hash; //鍵的哈希值
final K key; //鍵
V value; //值
TreeNode<K,V> parent; //父節點的位址值
TreeNode<K,V> left; //左子節點的位址值
TreeNode<K,V> right; //右子節點的位址值
boolean red; //節點的顔色
2.添加元素
HashMap<String,Integer> hm = new HashMap<>(); 建立map集合時，數組是null，還未給數組長度指派
hm.put("aaa" , 111); 添加時才給數組初始化長度
hm.put("bbb" , 222);
hm.put("ccc" , 333);
hm.put("ddd" , 444);
hm.put("eee" , 555);
添加元素的時候至少考慮三種情況：
2.1數組位置為null 就是該索引位置上沒有元素
2.2數組位置不為null，鍵不重複，挂在下面形成連結清單或者紅黑樹
2.3數組位置不為null，鍵重複，元素覆寫
//參數一：鍵
//參數二：值
//傳回值：被覆寫元素的值，如果沒有覆寫，傳回null
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//利用鍵計算出對應的哈希值，再把哈希值進行一些額外的處理
//簡單了解：傳回值就是傳回鍵的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//參數一：鍵的哈希值
//參數二：鍵
//參數三：值
//參數四：如果鍵重複了是否保留
// true，表示老元素的值保留，不會覆寫
// false，表示老元素的值不保留，會進行覆寫
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
//定義一個局部變量，用來記錄哈希表中數組的位址值。
Node<K,V>[] tab;
下面是把涉及到的源碼都拆分，寫在一起，便于檢視
//臨時的第三方變量，用來記錄鍵值對對象的位址值
Node<K,V> p;
//表示目前數組的長度
int n;
//表示索引
int i;
//把哈希表中數組的位址值，指派給局部變量tab
tab = table;
if (tab == null || (n = tab.length) == 0){
//1.如果目前是第一次添加資料，底層會建立一個預設長度為16，加載因子為0.75的數組
//2.如果不是第一次添加資料，會看數組中的元素是否達到了擴容的條件
//如果沒有達到擴容條件，底層不會做任何操作
//如果達到了擴容條件，底層會把數組擴容為原先的兩倍，并把資料全部轉移到新的哈希表中
//擴容條件為數組元素數量達到了（加載因子*數組長度），擴容操作也時這個resize()方法做的
tab = resize();
//表示把目前數組的長度指派給n
n = tab.length;
}
//拿着數組的長度跟鍵的哈希值進行計算，計算出目前鍵值對對象，在數組中應存入的位置
i = (n - 1) & hash;//index
//擷取數組中對應元素的資料
p = tab[i];
if (p == null){ //①數組對應索引上沒有元素直接存入的情況
//底層會建立一個鍵值對對象，直接放到數組當中
tab[i] = newNode(hash, key, value, null);
}else {
Node<K,V> e;
K k;
//等号的左邊：數組中鍵值對的哈希值
//等号的右邊：目前要添加鍵值對的哈希值
//如果鍵不一樣，此時傳回false
//如果鍵一樣，傳回true
boolean b1 = p.hash == hash;
if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){
e = p;
} else if (p instanceof TreeNode){ //②從這開始就是存儲位置有元素，但鍵不同的情況
//判斷數組中擷取出來的鍵值對是不是紅黑樹中的節點
//如果是，則調用方法putTreeVal，把目前的節點按照紅黑樹的規則添加到樹當中。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
} else {
//如果從數組中擷取出來的鍵值對不是紅黑樹中的節點
//表示此時下面挂的是連結清單
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//此時就會建立一個新的節點，挂在下面形成連結清單
p.next = newNode(hash, key, value, null);
//判斷目前連結清單長度是否超過8，如果超過8，就會調用方法treeifyBin
//treeifyBin方法的底層還會繼續判斷
//判斷數組的長度是否大于等于64
//如果同時滿足這兩個條件，就會把這個連結清單轉成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//e： 0x0044 ddd 444
//要添加的元素： 0x0055 ddd 555
//如果哈希值一樣，就會調用equals方法比較内部的屬性值是否相同
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
p = e;
}
}
//如果e為null，表示目前不需要覆寫任何元素
//如果e不為null，表示目前的鍵是一樣的，值會被覆寫
//e:0x0044 ddd 555
//要添加的元素： 0x0055 ddd 555
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null){
//等号的右邊：目前要添加的值
//等号的左邊：0x0044的值
e.value = value; //就是把新的value覆寫給了原來的value，其實整個entry并沒有覆寫還是以前的，隻是value被覆寫了
}
afterNodeAccess(e);
return oldValue;
}
}
//threshold：記錄的就是數組的長度 * 0.75，哈希表的擴容時機 16 * 0.75 = 12
if (++size > threshold){
resize();
}
//表示目前沒有覆寫任何元素，傳回null
return null;
}
LinkedHashMap和LinkedHashSet，底層原理基本一緻，有序，唯一，無索引
3. TreeMap
- TreeMap跟TreeSet底層原理一樣，都是紅黑樹結構的。
- 由鍵決定特性:不重複、無索引、可排序
- 可排序:對鍵進行排序。
- 注意:預設按照鍵的從小到大進行排序，也可以自己規定鍵的排序規則
排序規則也是和TreeSet一樣有兩種
- 實作Comparable接口，指定比較規則。
- 建立集合時傳遞Comparator比較器對象，指定比較規則。
不指定排序規則，預設按照鍵的升序來排序，這個預設的排序規則和TreeMap的一樣
對于數值類型:Integer , Double，預設按照從小到大的順序進行排序。
對于字元、字元串類型:按照字元在ASCII碼表中的數字升序進行排序。比較過程中隻要有一個字元能确定大小關系，後面字母就不會再看了（不是和起來比大小）
4. TreeMap底層源碼解析
看源碼之前需要了解的一些内容，屬性，方法解釋分析
1.TreeMap中每一個節點的内部屬性
K key; //鍵
V value; //值
Entry<K,V> left; //左子節點
Entry<K,V> right; //右子節點
Entry<K,V> parent; //父節點
boolean color; //節點的顔色
2.TreeMap類中中要知道的一些成員變量
public class TreeMap<K,V>{
//比較器對象
private final Comparator<? super K> comparator;
//根節點
private transient Entry<K,V> root;
//集合的長度
private transient int size = 0;
3.空參構造
//空參構造就是沒有傳遞比較器對象
public TreeMap() {
comparator = null;
}
4.帶參構造
//帶參構造就是傳遞了比較器對象。
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
5.添加元素
public V put(K key, V value) {
return put(key, value, true);
}
參數一：鍵
參數二：值
參數三：當鍵重複的時候，是否需要覆寫值
true：覆寫
false：不覆寫
下面是把涉及到的源碼都拆分，寫在一起，便于檢視
private V put(K key, V value, boolean replaceOld) {
//擷取根節點的位址值，指派給局部變量t
Entry<K,V> t = root;
//判斷根節點是否為null
//如果為null，表示目前是第一次添加，會把目前要添加的元素，當做根節點
//如果不為null，表示目前不是第一次添加，跳過這個判斷繼續執行下面的代碼
if (t == null) {
//方法的底層，會建立一個Entry對象，把他當做根節點
addEntryToEmptyMap(key, value);
//表示此時沒有覆寫任何的元素
return null;
}
//表示兩個元素的鍵比較之後的結果
int cmp;
//表示目前要添加節點的父節點
Entry<K,V> parent;
//表示目前的比較規則
//如果我們是采取預設的自然排序，那麼此時comparator記錄的是null，cpr記錄的也是null
//如果我們是采取比較去排序方式，那麼此時comparator記錄的是就是比較器
Comparator<? super K> cpr = comparator;
//表示判斷目前是否有比較器對象
//如果傳遞了比較器對象，就執行if裡面的代碼，此時以比較器的規則為準
//如果沒有傳遞比較器對象，就執行else裡面的代碼，此時以自然排序的規則為準
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
} else {
//把鍵進行強轉，強轉成Comparable類型的
//要求：鍵必須要實作Comparable接口，如果沒有實作這個接口
//此時在強轉的時候，就會報錯。
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//把根節點當做目前節點的父節點
parent = t;
//調用compareTo方法，比較根節點和目前要添加節點的大小關系
cmp = k.compareTo(t.key);
if (cmp < 0)
//如果比較的結果為負數
//那麼繼續到根節點的左邊去找
t = t.left;
else if (cmp > 0)
//如果比較的結果為正數
//那麼繼續到根節點的右邊去找
t = t.right;
else {
//如果比較的結果為0，會覆寫
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
}
//就會把目前節點按照指定的規則進行添加
addEntry(key, value, parent, cmp < 0);
return null;
}
private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
Entry<K,V> e = new Entry<>(key, value, parent);
if (addToLeft)
parent.left = e;
else
parent.right = e;
//添加完畢之後，需要按照紅黑樹的規則進行調整
fixAfterInsertion(e);
size++;
modCount++;
}
private void fixAfterInsertion(Entry<K,V> x) {
//因為紅黑樹的節點預設就是紅色的
x.color = RED;
//按照紅黑規則進行調整
//parentOf:擷取x的父節點
//parentOf(parentOf(x)):擷取x的爺爺節點
//leftOf:擷取左子節點
while (x != null && x != root && x.parent.color == RED) {
//判斷目前節點的父節點是爺爺節點的左子節點還是右子節點
//目的：為了擷取目前節點的叔叔節點
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//表示目前節點的父節點是爺爺節點的左子節點
//那麼下面就可以用rightOf擷取到目前節點的叔叔節點
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
//叔叔節點為紅色的處理方案
//把父節點設定為黑色
setColor(parentOf(x), BLACK);
//把叔叔節點設定為黑色
setColor(y, BLACK);
//把爺爺節點設定為紅色
setColor(parentOf(parentOf(x)), RED);
//把爺爺節點設定為目前節點
x = parentOf(parentOf(x));
} else {
//叔叔節點為黑色的處理方案
//表示判斷目前節點是否為父節點的右子節點
if (x == rightOf(parentOf(x))) {
//表示目前節點是父節點的右子節點
x = parentOf(x);
//左旋
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
//表示目前節點的父節點是爺爺節點的右子節點
//那麼下面就可以用leftOf擷取到目前節點的叔叔節點
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//把根節點設定為黑色
root.color = BLACK;
}
代碼都給了詳細的注解，每段代碼的意思應該都很明确，看懂應該不難，這就是一個整體初始化及添加元素時，代碼的調用過程
5. Map結合總結與思考
1.TreeMap添加元素的時候，鍵是否需要重寫hashCode和equals方法？
此時是不需要重寫的。
2.HashMap是哈希表結構的，JDK8開始由數組，連結清單，紅黑樹組成的。
既然有紅黑樹，HashMap的鍵是否需要實作Compareable接口或者傳遞比較器對象呢？
不需要的。
因為在HashMap的底層，預設是利用哈希值的大小關系來建立紅黑樹的
3.TreeMap和HashMap誰的效率更高？
如果是最壞情況，添加了8個元素，這8個元素形成了連結清單，此時TreeMap的效率要更高
但是這種情況出現的幾率非常的少。
一般而言，還是HashMap的效率要更高。因為HashMap底層數組對于通路查詢元素操作效率更高
4.你覺得在Map集合中，java會提供一個如果鍵重複了，不會覆寫的put方法呢？
此時 p u t I f A b s e n t 本身不重要。（就是不會覆寫鍵值的方法） \color{blue} {此時putIfAbsent本身不重要。（就是不會覆寫鍵值的方法）} 此時putIfAbsent本身不重要。（就是不會覆寫鍵值的方法）
傳遞一個思想：
代碼中的邏輯都有兩面性，如果我們隻知道了其中的A面，而且代碼中還發現了有變量可以控制面性的發生。
那麼該邏輯一定會有B面。
習慣：
boolean類型的變量控制，一般隻有AB兩面，因為boolean隻有兩個值
int類型的變量控制，一般至少有三面，因為int可以取多個值。
5.三種雙列集合，以後如何選擇？
HashMap LinkedHashMap TreeMap
預設： HashMap（效率最高） 如果要保證存取有序：LinkedHashMap 如果要進行排序：TreeMap