Java 1.8的HashMap为什么改用尾插法后端java

【Java 1.8的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 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; } } }

可以看出扩容有两步：

创建新的Entry数组，容量是原来的两倍
将旧的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[] resize() { ... Node[] newTab = (Node[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node 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)e).split(this, newTab, j, oldCap); // 存在hash冲突并且非红黑树结构 else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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。
参考：