关于后端:Java-18的HashMap为什么改用尾插法

家喻户晓，java 1.7及以前HashMap链表插入元素都是用的头插法，这在多线程环境下会导致链表呈现环，被查找的时候会陷入死循环（CPU爆哭😭）。Java 1.8针对这个问题做了优化，应用了头插法，那么尾插法和头插法到底不同在哪里呢？

准备常识：HashMap的扩容机制
这里先放上源码：

void resize(int newCapacity) {
    ...
    Entry[] newTable = new Entry[newCapacity];
    // 新老table转换
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 1. 遍历老table
    for (Entry<K,V> e : table) {
        // 2. 如果元素不为空，遍历Entry元素
        while(null != e) {
            //先保留e的next结点
            next = e.next;
            ...
            //从新计算下标（因为长度变动）
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            // 3. 元素放入新table
            newTable[i] = e;
            // 4. 持续遍历Entry子节点
            e = next;
        }
    }
}

能够看出扩容有两步：

1. 创立新的Entry数组，容量是原来的两倍
2. 将旧的Entry数组拷贝到新的数组外面

因为Entry数组长度变长，原来的节点的下标可能会发生变化。具体是因为下标的计算方法：(n – 1) & hash。 同样的hash值，如果长度变了，那么最终得出的下标也可能不一样。
顺便说一下HashMap的初始容量16，n只有是2的幂，n – 1的二进制肯定全是1，假如有i位，那么它和任何hash做&操作必定都是保留hash的后i位（&操作两个都是1才是1），这样就十分滴平均，不容易抵触。
再回到这里把旧数组的元素拷贝到新的数组里，如果是尾插法，得遍历整个链表，复杂度是O（N），而头插法复杂度只有O（1），那么为什么要用尾插法呢？
先来看看头插法。借用一张大佬的图：

能够看到，在插入新节点的时候，头插法是先将新节点的next指向c1（L.next），而后再将L.next置为新节点。如果在多线程环境下，键值k对应的链表为k=a->b->null,
1.线程A先运行，put元素c，此时进行扩容，逐渐复制元素，当复制a之后，新链表为a->null
2.接着此时线程B运行，put元素d，B也进行扩容，B中的链表变成b->a->null
3.此时A再运行，将b也复制过去, A中新链表为b->a->null,此时A扩容结束
4.而后B运行，因为此时原数组曾经被A扩容结束，k对应的链表变成b->a->null，此时遍历的元素应该是b元素的字节点a,所以此时a将插入新数组造成a->b->a的环，程序陷入死循环。

此外，头插法在多线程环境下还会呈现put的节点失落的状况。这里就不开展了。
与之相比，尾插法从尾部插入，就不会有环的问题，因为每次都是插到尾部。

final Node<K,V>[] resize() {
    ...
    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;
                // 节点没有hash抵触，间接迁徙至新table
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 红黑树结构
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 存在hash抵触并且非红黑树结构
                else { // preserve order
                    Node<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;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.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;
}

然而还是会有节点失落的问题，因而可见，hashmap是线程不平安的，因为这一毛病，当初在多线程环境下，大多用CocurrentHashMap。

参考：

1. https://blog.csdn.net/u010257…
2. https://www.jianshu.com/p/0df…
3. https://blog.csdn.net/weixin_…
4. https://blog.csdn.net/u010597…