final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; // 老的node数组int oldCap = (oldTab == null) ? 0 : oldTab.length; //老的容量int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {// 判断数组是否达到了极限大小，若判定成功将不再扩容，直接将老表返回if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 新表大小 小于 数组极限大小 老的数组大小 大于等于 16（默认大小）else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold 扩容阈值 * 2}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaults//数组为空newCap = DEFAULT_INITIAL_CAPACITY; // 新容量为默认大小 16// 扩容阈值为12newThr = (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;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];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) // 当数组的第j个节点只有一个数据时newTab[e.hash & (newCap - 1)] = e; //直接转移到新数组else if (e instanceof TreeNode) // 节点为树节点时//分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {TreeNode<K,V> b = this; //bit 为老容量// Relink into lo and hi lists, preserving orderTreeNode<K,V> loHead = null, loTail = null;TreeNode<K,V> hiHead = null, hiTail = null;int lc = 0, hc = 0;// e 为当前的树节点for (TreeNode<K,V> e = b, next; e != null; e = next) {next = (TreeNode<K,V>)e.next;e.next = null;// 1、等于0时，则将该树链表头节点放到新数组时的索引位置等于其在旧数组时的索引位置，记为低位区树链表lo。// 2、不等于0时，则将该树链表头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度，记为高位区树链表hi。if ((e.hash & bit) == 0) {if ((e.prev = loTail) == null)loHead = e; //低位链表头 = eelseloTail.next = e; //相当于尾插loTail = e; //loTail指针向后移动++lc;}else {if ((e.prev = hiTail) == null)hiHead = e; //高位链表头 = eelsehiTail.next = e;hiTail = e;++hc;}}// 现在拆出两条链表 loTail hiHead 低位或高位链表 此时为treeNode链表if (loHead != null) {if (lc <= UNTREEIFY_THRESHOLD) //链表长度小于6tab[index] = loHead.untreeify(map);else {tab[index] = loHead;//如果高位首节点不为空，说明原来的红黑树已经被拆分成两个链表了if (hiHead != null) // (else is already treeified)//那么就需要构建新的红黑树了loHead.treeify(tab);}}//如果高位链表首节点不为null，说明有这个链表存在if (hiHead != null) {//如果链表下的元素小于等于6if (hc <= UNTREEIFY_THRESHOLD)//那就从红黑树转链表了，高位链表，迁移到新数组中的下标=【旧数组+旧数组长度】tab[index + bit] = hiHead.untreeify(map);else {//高位链表，迁移到新数组中的下标=【旧数组+旧数组长度】，把高位链表整个拉到这个新下标下，做赋值tab[index + bit] = hiHead;//如果低位首节点不为空，说明原来的红黑树已经被拆分成两个链表了if (loHead != null)//那么就需要构建新的红黑树了hiHead.treeify(tab);}}}
// 此方法将treeNode 转化为Nodefinal 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<K,V> p = map.replacementNode(q, null);if (tl == null)hd = p;elsetl.next = p;tl = p;}return hd;}
/*** 参数为HashMap的元素数组*/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; // 取得当前链表节点的keyint h = x.hash; // 取得当前链表节点的hash值Class<?> kc = null; // 定义key所属的Classfor (TreeNode<K,V> p = root;;) { // 从根节点开始遍历，此遍历没有设置边界，只能从内部跳出// GOTO1int dir, ph; // dir 标识方向（左右）、ph标识当前树节点的hash值K pk = p.key; // 当前树节点的keyif ((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; // 保存当前树节点/** 如果dir 小于等于0 ： 当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子 或者 更深层次的节点。* 如果dir 大于0 ： 当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子 或者 更深层次的节点。* 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩子 为 起始节点 再从GOTO1 处开始 重新寻找自己（当前链表节点）的位置* 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。* 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点进行处理了。*/if ((p = (dir <= 0) ? p.left : p.right) == null) {x.parent = xp; // 当前链表节点 作为 当前树节点的子节点if (dir <= 0)xp.left = x; // 作为左孩子elsexp.right = x; // 作为右孩子root = balanceInsertion(root, x); // 重新平衡break;}}}}// 把所有的链表节点都遍历完之后，最终构造出来的树可能经历多个平衡操作，根节点目前到底是链表的哪一个节点是不确定的// 因为我们要基于树来做查找，所以就应该把 tab[N] 得到的对象一定根节点对象，而目前只是链表的第一个节点对象，所以要做相应的处理。moveRootToFront(tab, root); // 单独解析}
treenode链表表示在扩容是，将红黑树分割成的高低位链表
root是把链表转换成红黑树的根节点
总结
第一步：开始循环遍历treenode链表，如果没有设置root，则设置root
第二步：存在root节点时，从root节点遍历
root节点的hash值 > 当前treenode 表示当前链表节点会放到当前树节点的左侧
root节点的hash值 < 当前treenode 表示当前链表节点会放到当前树节点的右侧
root节点的hash值 < 当前treenode
若有收获，就点个赞吧
0 人点赞
