什么是HashMap容器
【1】HashMap是使用頻率最高的用于映射(鍵值對)處理的資料型別，隨著JDK（Java Developmet Kit）版本的更新，JDK1.8對HashMap底層的實作進行了優化，例如引入紅黑樹的資料結構和擴容的優化等，
【2】jdk1.8 之前 HashMap 由 陣列 + 鏈表 組成，陣列是 HashMap 的主體，鏈表則是主要為了解決哈希沖突（兩個物件呼叫的 hashCode 方法計算的哈希值經哈希函式算出來的地址被別的元素占用）而存在的（“拉鏈法”解決沖突），jdk1.8 以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（或者紅黑樹的邊界值，默認為 8 ）并且當前陣列的長度大于 64 時，此時此索引位置上的所有資料改為使用紅黑樹存盤，
【3】HashMap：它根據鍵的hashCode值存盤資料，大多數情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的， HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null，HashMap非執行緒安全，即任一時刻可以有多個執行緒同時寫HashMap，可能會導致資料的不一致，如果需要滿足執行緒安全，可以用 Collections的synchronizedMap方法使HashMap具有執行緒安全的能力，或者使用ConcurrentHashMap，
HashMap的疑難問題
【1】為什么轉成樹結構的閾值是8，而由樹轉回為鏈表結構的閾值是6？
在原始碼中有這么一段注釋：
Implementation notes. 實作注意事項 This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes, each structured similarly to those in java.util.TreeMap. Most methods try to use normal bins, but relay to TreeNode methods when applicable (simply by checking instanceof a node). Bins of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. However, since the vast majority of bins in normal use are not overpopulated, checking for existence of tree bins may be delayed in the course of table methods. 這個映射通常充當一個分箱(桶)哈希表，但是當容器太大時，它們被轉換為TreeNodes的容器，每個容器的結構類似于java.util.TreeMap中的容器， 大多數方法嘗試使用普通的bin，但在適用的情況下中繼到TreeNode方法(簡單地通過檢查節點的實體)， TreeNodes的容器可以像其他容器一樣被遍歷和使用，但是在過度填充時還支持更快的查找， 然而，由于正常使用的絕大多數容器都沒有過度填充，所以在表方法的程序中可能會延遲檢查樹容器的存在， .... Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are: 因為TreeNodes大約是常規節點的兩倍大，所以我們只在容器包含足夠的節點以保證使用時才使用它們(參見TREEIFY_THRESHOLD)， 當它們變得太小(由于洗掉或調整大小)時，它們會被轉換回普通的容器， 在分布良好的用戶hashCodes的用法中，很少使用樹容器， 理想情況下，在隨機hashCodes下，容器中節點的頻率遵循泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution)， 對于默認的調整大小閾值0.75，該分布的引數平均約為0.5，盡管由于調整大小粒度的差異很大， 忽略方差，串列大小k的期望出現次數為(exp(-0.5) * pow(0.5, k) / factorial(k))，第一個值是: 0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 千萬分之6 more: less than 1 in ten million 如果是更多的話，會低于千萬分之一 ...
【2】為什么HashMap要保證陣列長度是2的倍數呢？
主要原因是在于為了擴容時候的資料遷移，因為在原始碼中，HashMap是一個一個槽位的將資料遷移， 如果限制了是2的倍數是怎么樣的呢？ 如4個槽位各有四個資料 【1】 5，9，13，17 【2】 6，10，14，18 【3】 7，11，15，19 【4】 8，12，16，20 擴容成了8個槽位，則資料必然散落在原本的槽位和與之倍數的槽位上 【1】 9，17 【2】 10，18 【3】 11，19 【4】 12，20 【5】 5，13 【6】 6，14 【7】 7，15 【8】 8，16 這也是為什么擴容的時候只用設定兩個鏈表結構的原因： Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; 反之如果是1.5倍，那么散落在的槽位就不確定了，那么我們就要面對更復雜的情況，必然要按照槽位設定多個鏈表結構 如8個槽位就要8個鏈表結構，槽位越多，對應的花銷更多，所以顯得不劃算
原始碼分析HashMap的實作（我這里是拿JDK14的原始碼展示的）
【0】繼承關系
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
【1】節點的型別分析
//明顯是單鏈表的節點 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value =https://www.cnblogs.com/chafry/archive/2022/10/26/ 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; } } //LinkedHashMap類的Entry結構，將單鏈表節點包裝之后具備雙向鏈表節點的功能 static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } //所以TreeNode其實只是在Node節點上做了包裝，所以這個樹節點其實是包含了樹和雙向鏈表節點兩者的功能 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; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } /** * Returns root of tree containing this node. */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } ... }
【2】屬性值
//默認初始容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //默認最大容量 static final int MAXIMUM_CAPACITY = 1 << 30;//即536,870,912 //默認加載因子 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; /* ---------------- Fields -------------- */ //存放資料的集合 transient Node<K,V>[] table; //用于迭代器使用的 transient Set<Map.Entry<K,V>> entrySet; //資料個數 transient int size; //修改次數記錄 transient int modCount; //擴容的閾值，默認是（容量*加載因子） int threshold; //哈希表的加載因子 final float loadFactor;
【3】構造方法
//指定容量和負載因子 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException(...); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(...); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } //這個方法保證得出來的容量是2的N次方，把不足2的N次方的向上取到2的N次方 //如3得4，5得8,10得16 //設計的巧妙點在于使用了>>>表示無符號右移，也叫邏輯右移與異或方法 //減1，是為了讓二進制盡可能多的出現1，如1000000，減一后變為0111111，當然如果是1000001，這種會變為1000000【但影響并不大】， //就以1000001為例子，減一后為1000000 //其次當右移一位之后再異或就會保證前兩位是1，即1000000|100000=1100000 //所以第二次直接右移兩位再異或，即1100000|11000=1111000 //第三次就右移四位，即1111000|111=1111111 //所以最后+1，是會變成10000000即128 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; } //指定容量，默認負載因子為0.75 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //容量使用默認值16，負載因子也為默認值0.75 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } //傳入有資料的Map public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { //初始化容器 if (table == null) { // pre-size //使得計算出來的容量不大于閾值，+1是為了向上取整，因為整除是會舍棄小數點后面的 float ft = ((float)s / loadFactor) + 1.0F; //限制不大于最大容量 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //因為有可能是上面那種設定了容量但是沒有初始化table的情況 if (t > threshold) threshold = tableSizeFor(t); } //說明table已經初始化過了；判斷傳入map的size是否大于當前map的threshold，如果是，必須要resize，預先擴大容量，再put元素 else if (s > threshold) resize(); 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); } } }
【4】核心方法分析
【4.1】添加方法put()分析
//加入元素 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //生成的hash是key的hashCode的高16位與低16位相與 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果存在陣列，利用相與的方式獲得下標【二進制中相與是不可能大于最小值的】 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //如果陣列中已經有節點了 Node<K,V> e; K k; //如果key是相等的 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果節點是樹節點，就用樹節點的方式存入 else if (p instanceof TreeNode) 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】 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //如果當前遍歷到的資料和要插入的資料的 key 是一樣,和上面之前的一樣,賦值給變數 e,下面替換內容 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //進行內容的替換 if (e != null) { // existing mapping for key V oldValue =https://www.cnblogs.com/chafry/archive/2022/10/26/ e.value; if (!onlyIfAbsent || oldValue =https://www.cnblogs.com/chafry/archive/2022/10/26/= null) e.value = value; afterNodeAccess(e); //擴展方法 return oldValue; } } ++modCount; //達到閾值便要擴容 if (++size > threshold) resize(); afterNodeInsertion(evict); //擴展方法 return null; } //這里就涉及到了Node節點的創建了 Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); }
【4.1.1】鏈表轉成樹結構treeifyBin()方法分析
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //限制了陣列最少是64的長度 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); //滿足陣列長度64，鏈表長度8，就開始轉為樹結構 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //先將單鏈表轉為雙向鏈表 do { TreeNode<K,V> 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) hd.treeify(tab); } }
【4.2】擴容方法resize()分析
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //第一階段：計算出新的newCap(擴容后的容量)和newThr(擴容后閾值) if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //新容量為舊容量的2倍 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 { //如果陣列還沒有則將默認值設定進去，默認容量16，閾值為16*0.75=12 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; //第二階段：根據newCap和newThr構造出新的newTab @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //這里其實是執行緒不安全的，因為table的參考此時指向了新陣列【而新陣列還沒有被賦值】 table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap); //如果是鏈表 else { //構建兩個鏈表結構【這就是為什么要進行兩倍擴容的原因：因為假設是4個槽位，擴容到8個槽位，那么原本在第3槽位的資料散列之后的落點必然是在3與7兩者之一】 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> 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; }
【4.2.1】分析樹節點的分割子樹流程
//本質上也是先弄成兩個鏈表 //然后判斷存入槽位的該是鏈表還是樹 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; //也是創建了兩個鏈表結構 TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; //這里的操作本質上與鏈表結構的操作沒什么不同 for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next; e.next = null; if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } //對生成的鏈表進行判斷 if (loHead != null) { //要么不滿足條件，將退化成為鏈表，即將TreeNode結構轉回為Node if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { //如果還是樹的話，針對新鏈表再次樹化一遍 tab[index] = loHead; if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } }
【4.2.1.1】分析樹節點的退化流程
final Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; for (Node<K,V> q = this; q != null; q = q.next) { //重新轉為Node節點 Node<K,V> p = map.replacementNode(q, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; } Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { return new Node<>(p.hash, p.key, p.value, next); }
【4.2.1.2】分析樹節點的再次樹化treeify()方法流程
final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; // 定義樹的根節點 for (TreeNode<K,V> x = this, next; x != null; x = next) { // 遍歷鏈表，x指向當前節點、next指向下一個節點 next = (TreeNode<K,V>)x.next; x.left = x.right = null; // 設定當前節點的左右節點為空 if (root == null) { // 如果還沒有根節點 x.parent = null; // 當前節點的父節點設為空 x.red = false; // 當前節點的紅色屬性設為false（把當前節點設為黑色） root = x; // 根節點指向到當前節點 } else { // 如果已經存在根節點了 K k = x.key; // 取得當前鏈表節點的key int h = x.hash; // 取得當前鏈表節點的hash值 Class<?> kc = null; for (TreeNode<K,V> p = root;;) { // 從根節點開始遍歷，此遍歷沒有設定邊界，只能從內部跳出 int dir, ph; K pk = p.key; // 當前樹節點的key if ((ph = p.hash) > h) // 如果當前樹節點hash值 大于 當前鏈表節點的hash值 dir = -1; // 標識當前鏈表節點會放到當前樹節點的左側 else if (ph < h) dir = 1; // 標識當前鏈表節點會放到當前樹節點的右側 //如果兩個節點的key的hash值相等，那么還要通過其他方式再進行比較， //如果當前鏈表節點的key實作了comparable介面，并且當前樹節點和鏈表節點是相同Class的實體，那么通過comparable的方式再比較兩者， //如果還是相等，最后再通過tieBreakOrder比較一次 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; //掛載之后，還需要重新把樹進行平衡，平衡之后，就可以針對下一個鏈表節點進行處理了， //為什么需要再平衡，基于紅黑樹的定義【紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹】： //性質1. 結點是紅色或黑色， //性質2. 根結點是黑色， //性質3. 所有葉子都是黑色，（葉子是NIL結點） //性質4. 每個紅色結點的兩個子結點都是黑色，（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點） //性質5. 從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點， if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); // 重新平衡 break; } } } } // 把所有的鏈表節點都遍歷完之后，最終構造出來的樹可能經歷多個平衡操作，根節點目前到底是鏈表的哪一個節點是不確定的 // 因為我們要基于樹來做查找，所以就應該把 tab[N] 得到的物件一定根節點物件，而目前只是鏈表的第一個節點物件，所以要做相應的處理， moveRootToFront(tab, root); } //將根結點放置于陣列的槽位上，便于一開始就從樹的頭結點開始遍歷 static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { int n; //紅黑樹根節點不能為空，table陣列不能為空 if (root != null && tab != null && (n = tab.length) > 0) { //獲取紅黑樹根節點的應該放入的下標位置 int index = (n - 1) & root.hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; //如果當前的下標位置放得物件與需要驗證的物件，不是同一個物件 if (root != first) { Node<K,V> rn; //設定紅黑樹根節點的值為改下標位置的值 tab[index] = root; TreeNode<K,V> rp = root.prev; //重置紅黑樹根節點的上下級關系，主要是調整root,root.prev,root.next,first;四者的關系 if ((rn = root.next) != null) ((TreeNode<K,V>)rn).prev = rp; if (rp != null) rp.next = rn; if (first != null) first.prev = root; root.next = first; root.prev = null; } assert checkInvariants(root); } }
【4.2.1.2】分析樹節點的再平衡balanceInsertion()方法流程
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { //默認是紅色節點 x.red = true; //回圈當前節點的樹結構 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //如果當前物件的父節點為空，則認為是根節點，根節點不能為紅節點，回傳該節點 if ((xp = x.parent) == null) { x.red = false; return x; } //如果父節點是紅色節點，以父節點的父節點為空，當前節點為根節點的孫子，設定該節點為紅色，并回傳 else if (!xp.red || (xpp = xp.parent) == null) return root; //如果當前節點的父節點和父節點的父節點的左節點相等 if (xp == (xppl = xpp.left)) { //如果當前節點的父節點的父節點的右節點是紅色的 if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { //如果當前節點與父節點的右節點相等，則進行左旋轉 if (x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } //父節點不為空，設定父節點的顏色，及是否右旋轉 if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } //如果當前節點的父節點和父節點的父節點的左節點不相等 else { if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { //如果當前節點與父節點的左節點相等，則進行右旋轉 if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } //父節點不為空，設定父節點的顏色，及是否左旋轉 if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } } //左旋 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> r, pp, rl; if (p != null && (r = p.right) != null) { if ((rl = p.right = r.left) != null) rl.parent = p; if ((pp = r.parent = p.parent) == null) (root = r).red = false; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root; } //右旋 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> l, pp, lr; if (p != null && (l = p.left) != null) { if ((lr = p.left = l.right) != null) lr.parent = p; if ((pp = l.parent = p.parent) == null) (root = l).red = false; else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root; }
【4.3】主體的存放邏輯已經闡述完了，下次有空再補一下JDK7的版本吧，畢竟JDK8可是修復了老版本的大BUG，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/519372.html
標籤：其他