浅析HashMap源码系列----resize过程(JDK1.8版)

1 java.util.HashMap#resize()方法源码解析

保存原来数据(扩容阈值、容量大小、具体数据等)判断oldCap。 如果大于0，说明之前已经初始化过。 如果旧容量已经超过最大容量，将阈值设置到最大。返回原有数组，让其碰撞。如果新容量是旧容量右移一位得到。新容量大于默认容量16，小于最大容量，将原来阈值扩大两倍。 如果旧阈值大于零。初始化容器，并设置为阈值 初始阈值为0，表示采用默认初始化过程。创建新容量的node数组。容量为旧容量的2倍。采用for循环依次遍历旧Tab。 如果索引为 j 处的只有一个数据，用e.hash&(newCapacity-1) 算出新位置，直接放入如果索引为 j 处的node为红黑树。采用红黑树的散列方式 红黑树和链表都是采用lo和hi两个链表暂时存放数据。套路和下面链表一样。判断lo和hi的元素个数。 如果小于等于6,则将treeNode转化为普通Node。如果超过6，就进行树化处理，和put的树化处理一样。 如果索引为 j 处的node为链表。 用lo和hi的两个链表存放此处的数据。 如果该节点node.hash(也就是key的hash)&oldCap == 0 。就放在原位置。 散列过程中，先用loTail的子节点设置为要散列数据，然后loTail再设置为散列数据，最后将子节点数据置null。保证没有重复，在置null前，最后一个和上一个loTail是相同的。 如果该节点node.hash(也就是key的hash)&oldCap != 0。就放在原位置+oldCap。 散列过程中，先用hiTail的子节点设置为要散列数据，然后hiTail再设置为散列数据，最后将子节点数据置null。保证没有重复，在置null前，最后一个和上一个hiTail是相同的。 最后将lo和hi的Head放入数组的 j 位置。

2 具体源码解析

2.1 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; if (oldCap > 0) { // 如果大于最大容量(2的30次方)，将阈值设置为Integer最大数值。返回原有数组，不扩容 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; } else if (oldThr > 0) // 初始化容器，并设置为阈值 newCap = oldThr; else { // 初始阈值为零,表示使用默认值初始化 newCap = DEFAULT_INITIAL_CAPACITY; // 16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12 } // 如果新阈值为0。再次用指定的加载因子初始化新阈值。 if (newThr == 0) { // 初始化HashMap指定的加载因子。 float ft = (float)newCap * loadFactor; // 扩容后长度没有超过最大capacity。用计算出来的。如果超过就用Integer的最大值。 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 新阈值生效 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) // 创建新容量的Node数组 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; // 如果j桶中有数据，先用临时e节点储存 if ((e = oldTab[j]) != null) { // 该桶和数组连接置空，方便后面GC数组 oldTab[j] = null; // 如果该桶就有一个元素， if (e.next == null) // 计算出新数组的位置，并将Node放入 newTab[e.hash & (newCap - 1)] = e; // 桶中数据为红黑树。 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 链表的散列 Node<K,V> loHead = null, loTail = null;// 表示还在原角标位上的node元素 Node<K,V> hiHead = null, hiTail = null;// 表示在原角标+oldCapacity位 Node<K,V> next; // 依次将原先的节点拿出来重新挂在node中。 do { // 保存第二个节点 next = e.next; // 根据当前节点hash&oldCapacity整除，来判断该节点在原来的j位置。 // 如果有余，就散列到新的j+oldCap位置 if ((e.hash & oldCap) == 0) { //loTail在保存node节点的时候，先赋next，然后覆盖loTail，最后next置空 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; }// 不整除，就将这一串数据放到j+oldCap位置。 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { // 尾节点置null，上一节点和本节点数据相同； loTail.next = null; // 将列表头放入数组的角标微商 newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

2.2 split() 红黑树的散列方式

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; // b，e是当前节点。 for (TreeNode<K,V> e = b, next; e != null; e = next) { // 保存下一个节点。 next = (TreeNode<K,V>)e.next; e.next = null; // bit是oldCapcatity；和链表的一个套路，整除的就在原来位置 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) { // 小于树化阈值，不进行树化 if (lc <= UNTREEIFY_THRESHOLD) // 将treeNode转化为普通的node tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // 走的二次树化的代码 loHead.treeify(tab); } } // 原来位置+oldCap的情况，和上面一样 if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } }