JDK8HashMap的扩容核心解读，尾插法

青旅半醒 2023-07-22 03:55 3阅读 0赞

看懂了JDK7Hashmap的扩容头插法，及其可能产生的循环引用问题，今天看看JDK8的HashMap扩容实现。采取的是用四个结点，两条链表完成重新分配位置，比较简单有趣。解析如下：

//如果原来的table等于null，直接返回
             if (oldTab != null) {
                 //遍历原来的table，bucket
                 for (int j = 0; j < oldCap; ++j) {
                     HashMap.Node<K, V> e;//bucket
                     if ((e = oldTab[j]) != null) {//如果当前桶位上有元素，不为null
                         oldTab[j] = null;//当前位置置空
                         if (e.next == null)//如果只有一个元素e，e.next为null，直接安排e到新表新家
                             newTab[e.hash & (newCap - 1)] = e;
                         else if (e instanceof HashMap.TreeNode)//判断e是不是树形节点，也就是超过8个元素
                             ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);//
                         else { // preserve order
                             HashMap.Node<K, V> loHead = null, loTail = null;//低位的头结点，尾结点
                             HashMap.Node<K, V> hiHead = null, hiTail = null;//高危的头结点，尾结点
                             HashMap.Node<K, V> next;//下个节点
                             do {//在这个循环里，依次处理该桶上链表，分裂成高位链和低位链
                                 next = e.next;//后一个节点元素
                                 //如果元素的hash值，与 原来表的容量 等于0,实际上是把原来在一个桶位的元素分流
                                 //例如e.hash & 10000，值会有0和1两种，等于0的，还是相对于原表的索引位置
                                 //等于1,把他向高位调整
                                 if ((e.hash & oldCap) == 0) {
                                     if (loTail == null)//只有第一次进来的时候，loTail为null
                                         loHead = e;//设置头结点位e
                                     else
                                         loTail.next = e;//尾插
                                     loTail = e;//低位链指针下移
                                 } else {
                                     if (hiTail == null)
                                         hiHead = e;
                                     else
                                         hiTail.next = e;
                                     hiTail = e;
                                 }
                             } while ((e = next) != null);
                             //while循环完之后，大概会形成两个链表【高位链hiHead--hiTail，低位链loHead--loTail】,最极端的情况是只有高位链或
                             //只有低位链。拿着这两个链表，插入到对应桶位，入驻新家。
                             //判断低位链中是否有元素
                             if (loTail != null) {
                                 loTail.next = null;//干掉低位链尾部的next，因为e的下一个结点很可能被分到高位，所以我们要干掉这个叛徒
                                 newTab[j] = loHead;
                             }
                             //判断高位链中是否有元素
                             if (hiTail != null) {
                                 hiTail.next = null;
                                 newTab[j + oldCap] = hiHead;
                             }
                         }
                     }
                 }
             }