Java集合系列-HashMap 1.8(二)
2020-12-13 01:39
阅读：378
3.5 红黑树
3.5.1 树形化操作
3.5.1.1 操作描述
参照源码
3.5.1.2 源码解析
public class HashMapextends AbstractMap implements Map , Cloneable, Serializable { //... // 树形化准备 final void treeifyBin(Node [] tab, int hash) { int n, index; Node e; if (tab == null || (n = tab.length) MIN_TREEIFY_CAPACITY) // 对于触发了树形化操作，但是桶容量还没达到64的情况下优先去做扩容处理，扩容也会分拆链表 resize(); // 定位要做树形下的桶位置，获取桶位元素e else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode hd = null, tl = null; // 循环遍历链表中的元素，将其改造成为双向链表结构，表头元素为hd do { // 将e元素封装成为树节点TreeNode 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) // 执行树形化 hd.treeify(tab); } } // 将Node节点封装成树节点 TreeNode replacementTreeNode(Node p, Node next) { return new TreeNode(p.hash, p.key, p.value, next); } static final class TreeNode extends LinkedHashMap.Entry { //... // 树形化操作 final void treeify(Node [] tab) { TreeNode root = null;//代表根节点 // 此处循环将this赋值给x,this代表的是当前树节点，这个类是HashMap的内部类用于标识树节点， // this就是当前类的实例，也就是一个树节点，但是是哪个树节点，就要依靠之间的代码上下文来判 // 断了，看看调用该方法的地方有这样的代码：hd.treeify(tab);这就表示当前节点就是那额hd节 // 点，而这个hd节点就是之前改造好的双向链表的表头结点 // 这里循环的是双向链表中的元素 for (TreeNode x = this, next; x != null; x = next) { next = (TreeNode )x.next; x.left = x.right = null; if (root == null) { // root == null的情况是链表头结点的时候才会出现，这时候将这个头结点作为树根节点 x.parent = null;//根节点无父节点 x.red = false;//黑色 root = x;//赋值 } else { // 这里只有非链表头节点才能进来 K k = x.key; int h = x.hash; Class> kc = null; // 此处循环的是已构建的红黑树的节点，从根节点开始，遍历比较当前链表节点与当前红黑树节点的 // hash值，dir用于保存比较结果，如果当前链表节点小，则dir为-1，否则为1，实际情况却是，能 // 拨到同一个桶位的所有元素的hash值那是一样的呀，所以dir的值是无法依靠hash值比较得出结果 // 的，那么重点就靠最后一个条件判断来得出结果了， for (TreeNode p = root;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk);// 最后需要依靠这个方法来决定dir的值 TreeNode xp = p; // 根据dir的值来决定将当前链表节点保存到当前树节点的左边还是右边， // 或者当前链表节点需要与当前树节点的左节点还是右节点接着比较 // 主要寻找子节点为null的情况，将节点保存到null位置 if ((p = (dir null) { x.parent = xp; if (dir ) // dir xp.left = x; else // dir xp.right = x; // 一旦添加的一个新节点，就要进行树平衡操作，以此保证红黑树结构 // 树的平衡操作依靠的就是其左右旋转操作 root = balanceInsertion(root, x); break; } } } } // 最后将组装好的树的根节点保存到桶下标位 moveRootToFront(tab, root); } static void moveRootToFront(Node [] tab, TreeNode root) { int n; if (root != null && tab != null && (n = tab.length) > 0) { // 首先定位桶下标位 int index = (n - 1) & root.hash; TreeNode first = (TreeNode )tab[index]; // 校验当前桶下标位的值是否为根节点的值，可能会存在不同的原因是树的平衡操作将原本的根节点挪移了 // 如果相同，那么不作任何处理，如果不同，就需要替换桶位元素为树根节点元素，然后改变双向链表结构 // 将root根节点作为双向链表表头元素,为何要替换呢，因为在判断桶位元素类型时会对链表进行遍历，如 // 果桶位置放的不是链表头或者尾元素，遍历将变得非常麻烦 if (root != first) { Node rn; tab[index] = root; TreeNode rp = root.prev; if ((rn = root.next) != null) ((TreeNode )rn).prev = rp; if (rp != null) rp.next = rn; if (first != null) first.prev = root; root.next = first; root.prev = null; } // 校验链表和树的结构 assert checkInvariants(root); } } //... } //... }
3.5.2 红黑树分拆操作
3.5.2.1 操作描述
很简单，看源码
3.5.2.2 源码解析
public class HashMapextends AbstractMap implements Map , Cloneable, Serializable { //... static final class TreeNode extends LinkedHashMap.Entry { //... // 将一颗大树分拆为两颗小树，如果树太小，退化为单向链表 final void split(HashMap map, Node [] tab, int index, int bit) { // this代表当前节点，也就是树的根节点，桶位节点 // map代表当前集合 // tab代表新桶数组 // index代表当前节点的桶位下标 // bit为旧桶容量 TreeNode b = this; // Relink into lo and hi lists, preserving order TreeNode loHead = null, loTail = null; TreeNode hiHead = null, hiTail = null; int lc = 0, hc = 0;// lc表示低位树容量，hc表示高位树容量 for (TreeNode e = b, next; e != null; e = next) { next = (TreeNode )e.next; e.next = null; // 分拆树节点的依据，结果为0的一组（低位组），结果不为0的一组（高位组） 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; } } // 针对低位组进行树形化处理，如果该组元素数量少于6个则退化为单向链表 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); } } // 针对高位组进行树形化处理，如果该组元素少于6个则退化为单向链表 if (hiHead != null) { if (hc UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } } //... } //... }
3.5.3 红黑树添加元素操作
3.5.3.1 操作描述
参照源码
3.5.3.2 源码解析
public class HashMapextends AbstractMap implements Map , Cloneable, Serializable { //... static final class TreeNode extends LinkedHashMap.Entry { //... // 红黑树的添加元素，map为当前HashMap，tab为当前桶数组，h为新增元素的key的hash值，k为新增元素的key,v为新增元素的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;;) { // dir代表当前树节点与待添加节点的hash比较结果 // ph代表当前树节点的hash值 // pk代表当前树节点的key // 由于一个桶位的所有元素hash值相等，所以最后得出结果需要依靠 int dir, ph; K pk; if ((ph = p.hash) > h) // 如果当前节点的hash值大，dir为-1 dir = -1; else if (ph h) // 如果当前节点的hash值小，dir为1 dir = 1; else if ((pk = p.key) == k || (k != null && k.equals(pk))) // hash值相等的情况下，如果key也一样直接返回当前节点，返回去之后会执行value的替换操作 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)) // 这个找到的q也是与待添加元素key相同的元素，执行替换 return q; } // 最终需要依靠这个方法来得出dir值的结果 dir = tieBreakOrder(k, pk); } TreeNode xp = p; // 根据dir的值来决定是当前节点的左侧还是右侧，如果该侧右子节点则继续循环寻找位置，否则直接将新元素添加到该侧子节点位置 if ((p = (dir null) { Node xpn = xp.next; TreeNode x = map.newTreeNode(h, k, v, xpn);//封装树节点 if (dir ) // dir xp.left = x; else // 否则将新节点添加到当前节点右侧 xp.right = x; // 设置新节点的链表位置，将其作为xp的下级节点 xp.next = x; x.parent = x.prev = xp; if (xpn != null) // 如果xp节点原本有下级节点xpn，则要将新节点插入到xp和xpn之间（指双向链表中） ((TreeNode )xpn).prev = x; // 插入了新节点之后，要进行树平衡操作，平衡操作完成，将根节点设置为桶位节点 moveRootToFront(tab, balanceInsertion(root, x)); return null; } } } final TreeNode return d; } //... } //... }root() { for (TreeNode r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } // 一般我们在HashMap中保存的键值对的类型都是不变的，这一般用泛型控制， // 那么就意味着，两个元素的key的类型时一样的，所以才需要靠其hashCode来决定大小 // System.identityHashCode(parameter)是本地方法，用于获取和hashCode一样的结果， // 这里的hashCode指的是默认的hashCode方法，与某些类重写的无关 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) );
3.5.4 红黑树添加元素平衡操作
3.5.4.1 操作描述
3.5.4.1.1 左旋操作描述
绕A节点左旋，等于将A的右子节点B甩上来替换自己的位置，而自己顺势下沉成为其左子节点，这时你会发现，B有三个子节点，明显结构不对，将B的原来的左子节点C转移到下沉的A上，成为其右子节点，旋转结束
其实，要保证左子树节点值小于其根节点，右子树节点值大于其根节点，那么在替换AB节点之后，C节点的值就出现了问题，只有将其挪到A节点右边才能继续保证上面的结构。
首先我们知道B节点为A的右节点，那么B>A，而C为B的左节点，则CA,因此：A
3.5.4.1.2 右旋操作描述
上一篇：JS 对象的操作方法
下一篇：学习IT技术网站
评论
亲，登录后才可以留言！