HashMap中紅黑樹的定義和它內部的方法

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; //父親節點 red-black tree linksTreeNode<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);}final TreeNode<K,V> root(){//返回節點的根節點...}static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root){... //把給定節點設為桶中的第一個元素}final TreeNode<K,V> find(int h, Object k, Class<?> kc){... //從當前結點this開始通過給定的hash和key查找結點}final TreeNode<K,V> getTreeNode(int h, Object k) {... // 從根節點開始尋找節點}static int tieBreakOrder(Object a, Object b) {...//用來排序}final void treeify(Node<K,V>[] tab){...//鏈表樹化}final Node<K,V> untreeify(HashMap<K,V> map){...//轉化回鏈表}final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v){...//放入樹節點}final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable) {...//刪除節點}final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit){...//Resize()調用}static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p){...//左旋 }static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p){...//右旋}static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {...//插入后保持平衡}static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) {...//刪除后保持平衡}static <K,V> boolean checkInvariants(TreeNode<K,V> t) {}

轉化為紅黑樹–treeifyBin 方法

在HashMap中put方法時候，但數組中某個位置的鏈表長度大于8時，會調用treeifyBin方法將鏈表轉化為紅黑樹。

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 如果桶數組table為空，或者桶數組table的長度小于MIN_TREEIFY_CAPACITY，不符合轉化為紅黑樹的條件if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)// 數組大小小于64的，調用resize將數組大小擴容至2倍大小resize();// 如果符合轉化為紅黑樹的條件，而且hash對應的桶不為null， 則重新計算 hash段位，及table的索引位，第一個節點else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {// 遍歷鏈表，將鏈表元素轉化成TreeNode鏈TreeNode<K,V> p = replacementTreeNode(e, null);// 確定樹頭節點if (tl == null)// TreeNode鏈為空，將元素設置為hd的首個節點hd = p;else {// TreeNode鏈不為空，向TreeNode鏈后面添加元素p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);// 前面僅僅轉換為雙向鏈表，treeify才是轉換紅黑樹的處理方法入口　// 讓桶的第一個元素指向新建的紅黑樹頭結點，以后這個桶里的元素就是紅黑樹而不是鏈表了if ((tab[index] = hd) != null)// TreeNode鏈表轉化為紅黑樹hd.treeify(tab);}}

構成紅黑樹–treeify 方法

將Treenode鏈轉化成紅黑樹

final void treeify(Node<K,V>[] tab) {// root節點TreeNode<K,V> root = null;// 遍歷TreeNode鏈for (TreeNode<K,V> x = this, next; x != null; x = next) {// next　下一個節點next = (TreeNode<K,V>)x.next;// 設置左右節點為空x.left = x.right = null;// 第一次進入循環　root　== null，確定頭結點，為黑色if (root == null) {// 將根節點的父節點設置位空x.parent = null;// 將根節點設置為黑色x.red = false;//將x 設置為根節點root = x;}// 后面進入循環走的邏輯，x 指向樹中的某個節點。 此處為非根節點else {//　獲取當前循環節點keyK k = x.key;// 獲取當前節點 hashint h = x.hash;Class<?> kc = null;// 從根節點開始驗證，遍歷所有節點跟當前節點 x 比較，調整位置，有點像冒泡排序for (TreeNode<K,V> p = root;;) {// 循環查找當前節點插入的位置并添加節點int dir, ph;// 每個節點的 keyK pk = p.key;// hashMap元素的hash值用來表示紅黑樹中節點數值大小if ((ph = p.hash) > h)// 當前節點值小于根節點，dir = -1 沿左路徑查找dir = -1;else if (ph < h)// 當前節點值大于根節點, dir = 1 沿右路徑查找dir = 1;// 如果存在比較對象，則根據比較對象定義的comparable進行比較// 比較之后返回查詢節點路徑（左或右）else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0)// 當前節點的值等于根節點值。// 如果當前節點實現Comparable接口，調用compareTo比較大小并賦值dir// 如果當前節點沒有實現Comparable接口，compareTo結果等于0，則調用tieBreakOrder繼續比較大小// tieBreakOrder本質是通過比較k與pk的hashcodedir = tieBreakOrder(k, pk);// 當前“根節點”賦值給xpTreeNode<K,V> xp = p;if ((p = (dir <= 0) ? p.left : p.right) == null) {// 如果當前節點小于根節點且左子節點為空 或者 當前節點大于根節點且右子節點為空，直接添加子節點// 將px設置為ｘ的父節點x.parent = xp;if (dir <= 0)xp.left = x;elsexp.right = x;// 平衡紅黑樹，將二叉樹轉換位紅黑樹－正式轉換紅黑樹root = balanceInsertion(root, x);// 跳出循環，繼續向紅黑樹添加下一個元素break;}}}}// 確保紅黑樹根節點是數組中該index的第一個節點moveRootToFront(tab, root);}

新增元素后平衡紅黑樹–balanceInsertion方法

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {// 新增節點默認是紅色x.red = true;// xp父節點 xpp祖父節點 xppl祖父左節點 xppr 祖父右節點for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {// xp = x.parent// 如果x存在父節點，則說明目前只有一個節點,即root.根據紅黑樹的五大特征，根節點只能為黑色節點if ((xp = x.parent) == null) {// x的父節點為空，x應為根節點，應為黑色x.red = false;return x;}// xpp = xp.parent, 直接查詢的是根節點else if (!xp.red || (xpp = xp.parent) == null)// 父節點是黑色，祖父節點為空，直接返回return root;// xppl = xpp.left. x的父節點是左節點時if (xp == (xppl = xpp.left)) {// 驗證是否需要旋轉// xppr = xpp.right 存在右節點　且　右節點為紅色if ((xppr = xpp.right) != null && xppr.red) {// 叔父節點設為黑色xppr.red = false;// 父節點設為黑色xp.red = false;// 祖父節點設置為紅色xpp.red = true;// 將祖父節點設置為當前節點，并繼續循環操作x = xpp;}else {// 叔父節點為黑色或者空if (x == xp.right) {// x為父節點右節點，則要進行左旋操作root = rotateLeft(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}// 經過左旋x為左節點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;}// x為右節點if (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;// 以祖父節點為支點左旋root = rotateLeft(root, xpp);}}}}}}

向紅黑樹添加元素 – putTreeVal 方法

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {Class<?> kc = null;boolean searched = false;// 獲取根節點TreeNode<K,V> root = (parent != null) ? root() : this;for (TreeNode<K,V> p = root;;) { // 從root節點開始遍歷int dir, ph; K pk;// 通過比較hash大小確定添加元素的位置if ((ph = p.hash) > h)dir = -1;else if (ph < h)dir = 1;else if ((pk = p.key) == k || (k != null && k.equals(pk)))// key相同直接返回return p;else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0) {if (!searched) {TreeNode<K,V> 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<K,V> xp = p;// 根據dir大小添加元素if ((p = (dir <= 0) ? p.left : p.right) == null) {Node<K,V> xpn = xp.next;// 構建新的treeNode節點TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);if (dir <= 0)xp.left = x;elsexp.right = x;xp.next = x;x.parent = x.prev = xp;if (xpn != null)((TreeNode<K,V>)xpn).prev = x;// 平衡紅黑樹并保證root是index處首節點moveRootToFront(tab, balanceInsertion(root, x));return null;}}}

獲取方法–getTreeNode

// 獲取紅黑樹的指定節點final TreeNode<K,V> getTreeNode(int h, Object k) {return ((parent != null) ? root() : this).find(h, k, null);// 從根節點開始查詢}// 獲取紅黑樹指定節點final TreeNode<K,V> find(int h, Object k, Class<?> kc) {// 此節點p就是根節點,進入循環后p代表當前節點TreeNode<K,V> p = this;do {// 定義當前節點p的hash值ph、相對位置dir、keyint ph, dir; K pk;// 獲取當前節點的左子節點、右子節點TreeNode<K,V> pl = p.left, pr = p.right, q// 表明目標節點在當前節點的左子節點if ((ph = p.hash) > h)p = pl;// 表明目標節點在當前節點的右子節點else if (ph < h)p = pr;// 當前節點的hash值與目標節點hash值相等,且當前節點的key與目標key相等(equals)else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;// 當前節點的hash值與目標節點hash值相等,且當前節點的key與目標key不相等(equals)else if (pl == null)p = pr;else if (pr == null)p = pl;// 當前節點的hash值與目標節點hash值相等,// 且當前節點的key與目標key不相等(equals),// 且左子節點與右子節點均不為null,目標key實現Comparable接口,且與當前節點比較不為0else if ((kc != null ||(kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;// 當前節點的hash值與目標節點hash值相等,// 且當前節點的key與目標key不相等(equals),// 且左子節點與右子節點均不為null,目標key沒有實現Comparable接口,// 則直接在右子樹中查詢,這個方法并沒有在左子樹中循環,因為這是一個遞歸方法,// 先遍歷右子樹并判斷是否查找到,若無則將左子樹根節點作為當前節點,不用遍歷左子樹依然可以覆蓋全部情況else if ((q = pr.find(h, k, kc)) != null)return q;elsep = pl;} while (p != null);return null;// 未找到,返回null}

紅黑樹節點的刪除–removeTreeNode方法

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable) {int n;// 判斷是否為空，是，直接返回if (tab == null || (n = tab.length) == 0)return;// 計算下標int index = (n - 1) & hash;TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;// succ指向刪除節點的下一個，pred指向前一個TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;if (pred == null)// 前一個為空，tab[index] 和 first 指向后一個節點tab[index] = first = succ;else// 前一個節點不為空，則前一個節點的后一個節點指向后一個，就是刪除當前節點pred.next = succ;if (succ != null)// 如果后一個節點不為空，將他的前一個節點，指向當前節點的前一個succ.prev = pred;if (first == null) // 為空直接返回return;// 根節點存在父節點，說明不是根節點，調用root()獲取，確保root時根節點if (root.parent != null)root = root.root();// 根據節點及其左右孩子，判斷當前紅黑樹節點的數量，進而轉換為鏈表if (root == null|| (movable&& (root.right == null|| (rl = root.left) == null|| rl.left == null))) {tab[index] = first.untreeify(map); // too smallreturn;}// p 要刪除的節點，replacement刪除后替代他的節點// 刪除一個中級節點，但是他還有子節點，肯定連接到樹上的，此時需要一個節點來頂替他的位置TreeNode<K,V> p = this, pl = left, pr = right, replacement;// 刪除節點，左右孩子都不為空時，遍歷if (pl != null && pr != null) {TreeNode<K,V> s = pr, sl;// s = pr,是當前節點的右節點開始遍歷，找到最后一個左子節點// s是大于當前節點的最小值while ((sl = s.left) != null) // find successors = sl;// 顏色交換，要刪除的節點，替換他的節點boolean c = s.red; s.red = p.red; p.red = c; // swap colorsTreeNode<K,V> sr = s.right;TreeNode<K,V> pp = p.parent;// 位置交換// s == pr 意思是大于要刪除節點的最小節點，就是他的右節點// 在節點右邊都是比它大的，在節點左邊都是比它小的// 在當前節點的右邊，其右邊節點的左邊，說明大于當前節點，小于當前節點的右節點，最左邊的也就是最靠近當前節點if (s == pr) { // p was s's direct parentp.parent = s;s.right = p;}else {// 當前節點的父節點指向，替換節點的父節點TreeNode<K,V> sp = s.parent;if ((p.parent = sp) != null) {// 判斷替換的節點是其父的左右節點，將替換節點的父節點的左或者右節點指向當前節點if (s == sp.left)sp.left = p;elsesp.right = p;}// 替換節點的右節點指向刪除節點的右節點，刪除節點的右節點的父節點，指向替換節點if ((s.right = pr) != null)pr.parent = s;}// 刪除節點的左節點置空// 替換節點肯定不存在左節點，不然就不會成為替換節點p.left = null;// 但不一定沒有右節點，進行右節點賦值if ((p.right = sr) != null)sr.parent = p;// 將替換節點的左節點指向刪除節點的左節點if ((s.left = pl) != null)pl.parent = s;// 替換節點的父節點，指向刪除節點的父節點，如果父節點為空，則替換節點作為根節點if ((s.parent = pp) == null)root = s;// 刪除節點有父節點，且為父節點的左節點，父節點的左節點指向替換節點，反之亦然else if (p == pp.left)pp.left = s;elsepp.right = s;// 替換節點存在右節點，左節點是肯定不存在的// replacement 為替換節點右節點，反之為刪除節點if (sr != null)replacement = sr;elsereplacement = p;}// 刪除節點存在左節點，replacement為左節點else if (pl != null)replacement = pl;// 刪除節點存在右節點，replacement為右節點else if (pr != null)replacement = pr;// 左右節點都不存在，replacement為刪除節點elsereplacement = p;// replacement不為刪除節點（他有子節點，或者s節點有右節點）// 看replacement的賦值p的情況// p節點不存在子節點// p節點存在左右節點，且s節點無右節點if (replacement != p) {// 替換節點的父節點指向當前節點的父節點TreeNode<K,V> pp = replacement.parent = p.parent;// replacement 替換 p// 存在左右節點是，此時的p為替換之后的節點，replacement為sr（替換p的節點的右節點）// 存在左節點，或者右節點，那他的子節點替換p節點if (pp == null)// 如果父節點為null，替換節點為root節點root = replacement;else if (p == pp.left)pp.left = replacement;elsepp.right = replacement;// 孤立p節點p.left = p.right = p.parent = null;}// p節點為紅色，刪除后無影響，不為紅色需要進行平衡TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);// p 沒有兒子或者s沒有兒子，直接移除pif (replacement == p) { // detachTreeNode<K,V> pp = p.parent;p.parent = null;if (pp != null) {if (p == pp.left)pp.left = null;else if (p == pp.right)pp.right = null;}}// 處理根節點if (movable)moveRootToFront(tab, r);}

刪除元素后的平衡紅黑樹–balanceDeletion

static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) {for (TreeNode<K,V> xp, xpl, xpr;;) {// 要刪除的節點是根節點，或者為null，返回根節點if (x == null || x == root)return root;// x為根節點，設為黑色，返回else if ((xp = x.parent) == null) {x.red = false;return x;}// 刪除的節點是紅色，無需調整else if (x.red) {x.red = false;return root;}// 移除的節點是其父的左節點else if ((xpl = xp.left) == x) {// 兄弟為紅色if ((xpr = xp.right) != null && xpr.red) {// 兄弟設為黑色xpr.red = false;// 父節點為紅色xp.red = true;// 左旋root = rotateLeft(root, xp);// 重新將xp指向x的父節點，xpr指向xp新的右孩子xpr = (xp = x.parent) == null ? null : xp.right;}// 沒有兄弟節點，將x指向父節點，向上調整if (xpr == null)x = xp;else {// 存在兄弟節點，進一步調整// xpr是兄弟節點兄弟TreeNode<K,V> sl = xpr.left, sr = xpr.right;// 侄子為空或者侄子為黑（沒有就算黑）if ((sr == null || !sr.red) &&(sl == null || !sl.red)) {// 兄弟節點設為紅色，將x指向父節點xpr.red = true;x = xp;}// 侄子節點存在紅色節點else {// 兄弟右節點為空或者黑子，說明兄弟左節點為紅色if (sr == null || !sr.red) {// 兄弟左節點設置黑色if (sl != null)sl.red = false;// 兄弟節點設為紅色xpr.red = true;// 基于兄弟節點右旋root = rotateRight(root, xpr);// 兄弟節點重新指向xpr = (xp = x.parent) == null ?null : xp.right;}// 如果兄弟節點不為空if (xpr != null) {// 讓兄弟節點跟父節點同時xpr.red = (xp == null) ? false : xp.red;// 兄弟右節點不為空，設置黑色if ((sr = xpr.right) != null)sr.red = false;}// 存在父節點if (xp != null) {xp.red = false;// 設置黑色root = rotateLeft(root, xp);// 基于父節點左旋}x = root;}}}// x為右節點，與上面類似判斷節點顏色，顏色變化與旋轉else { // symmetricif (xpl != null && xpl.red) {xpl.red = false;xp.red = true;root = rotateRight(root, xp);xpl = (xp = x.parent) == null ? null : xp.left;}if (xpl == null)x = xp;else {TreeNode<K,V> sl = xpl.left, sr = xpl.right;if ((sl == null || !sl.red) &&(sr == null || !sr.red)) {xpl.red = true;x = xp;}else {if (sl == null || !sl.red) {if (sr != null)sr.red = false;xpl.red = true;root = rotateLeft(root, xpl);xpl = (xp = x.parent) == null ?null : xp.left;}if (xpl != null) {xpl.red = (xp == null) ? false : xp.red;if ((sl = xpl.left) != null)sl.red = false;}if (xp != null) {xp.red = false;root = rotateRight(root, xp);}x = root;}}}}}

HashMap對左旋右旋的實現

左旋

//root為根節點，p為旋轉的結點static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {// r當前節點的右節點// pp當前節點的父節點// rl當前節點的右節點的左節點TreeNode<K,V> r, pp, rl;//如果p不為空且存在右子結點rif (p != null && (r = p.right) != null) { //判斷右子結點的左子結點rl存在if ((rl = p.right = r.left) != null) //存在設置rl的父節點為prl.parent = p; //判斷p的父節點pp是否存在if ((pp = r.parent = p.parent) == null) //如果不存在設置新的根節點為r且黑色(root = r).red = false; //父結點pp存在且p為pp的左子結點else if (pp.left == p) pp.left = r;else //父結點pp存在且p為pp的左子結點pp.right = r;r.left = p;p.parent = r;}return root;}

右旋

//root為根節點，p為旋轉的結點static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,TreeNode<K,V> p) {// r當前節點的左節點// pp當前節點的父節點// rl當前節點的左節點的右節點TreeNode<K,V> l, pp, lr;//如果p不為空且存在左子結點lif (p != null && (l = p.left) != null) { //判斷左子結點的右子結點lr存在if ((lr = p.left = l.right) != null) //存在則設置rl的父結點為plr.parent = p; //判斷p的父結點pp是否存在if ((pp = l.parent = p.parent) == null)//如果不存在設置新的根節點為l且l為黑色(root = l).red = false;else if (pp.right == p) //父結點pp存在且p為pp的右子結點pp.right = l;else //父結點pp存在且p為pp的左子結點pp.left = l;l.right = p;p.parent = l;}return root;}

總結

以上是生活随笔為你收集整理的【源码解析】HashMap源码跟进（红黑树的实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。