HashMap在1.8（不含）之前对于新增元素的hash冲突的链表插入采用的是头插法，1.8之后开始改用尾插法。那么头插法有什么问题呢？为什么改用尾插法呢？源码学习一下咯

HashMap-jdk1.7.0_80

put新增map元素

public V put(K key, V value) {...// 添加新元素addEntry(hash, key, value, i);return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {// 如果当前map大小超出阈值，并且当前值再次触发了hash冲突，则resize mapif ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);
}

resize

对map进行扩容

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);
}

transfer

转换所有老table数据至新table

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;// 1. 遍历老tablefor (Entry<K,V> e : table) {// 2. 如果元素不为空，遍历Entry元素while(null != e) {next = e.next;...int i = indexFor(e.hash, newCapacity);e.next = newTable[i];// 3. 元素放入新tablenewTable[i] = e;// 4. 继续遍历Entry子节点e = next;}}
}

扩容问题

两个线程由于并发问题，触发并发扩容

数据丢失

线程1：put c

1. 当前old table（后面简称OT）的索引3: 3=a->b->null
2. 当前new table（后面简称NT）的索引3：null
3. 取出OT索引3处节点a
4. 节点a子节点置为NT的索引3处节点，即：a->null
5. 放入NT索引3处节点a
6. 当前new table（后面简称NT）的索引3：3=a->null
7. 取出OT索引3处节点的子节点b
8. 节点b子节点置为NT的索引3处节点，即：b->a->null
9. 放入NT索引3处节点b，并将NT索引3处的节点a置为节点b的子节点
10. 当前new table（后面简称NT）的索引3：3=b->a->null
11. 线程1扩容结束

线程2：put d

1. 当前old table（后面简称OT）的索引3: 3=a->b->null
2. 当前new table（后面简称NT）的索引3：3=null
3. 取出OT索引3处节点a
4. 节点c子节点置为NT的索引3处节点，即：a->null
5. 放入NT索引3处节点a
6. 此时节点a子节点为null，遍历结束
7. 最终new table（后面简称NT）的索引3：3=a->null
8. 线程2扩容结束

死循环

线程1：put c

1. 当前old table（后面简称OT）的索引3: 3=a->b->null
2. 当前new table（后面简称NT）的索引3：null
3. 取出OT索引3处节点a
4. 节点a子节点置为NT的索引3处节点，即：a->null
5. 放入NT索引3处节点a
6. 当前new table（后面简称NT）的索引3：3=a->null
7. 取出OT索引3处节点的子节点b

线程2：put d

1. 当前old table（后面简称OT）的索引3: 3=a->b->null
2. 当前new table（后面简称NT）的索引3：3=null
3. 取出OT索引3处节点a
4. 节点c子节点置为NT的索引3处节点，即：a->null
5. 放入NT索引3处节点a
6. 此时节点a子节点为b
7. 取出节点b，复制，NT此时为：b->a->null

线程1

1. 节点b子节点置为NT的索引3处节点，即：b->a->null
2. 放入NT索引3处节点b，并将NT索引3处的节点a置为节点b的子节点
3. 当前new table（后面简称NT）的索引3：3=b->a->null
4. 线程1扩容结束

线程2

1. 取出节点b子节点，此时为节点a
2. 切换指针插入NT，此时NT为：3=a->b->a，由于更新了a节点的next指针，形成环路：a->b->a
3. 线程2扩容结束

此时两个线程或者其他读取该索引处的线程都将进入死循环，cpu也将随着死循环的增加被打满导致服务凉凉

createEntry

插入新value值计算出的索引依然为3

void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);size++;
}
// 创建新Entry元素
Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;
}

假设两个线程没有出现并发带来的扩容问题，完美完成扩容后进行插入新value值

并发插入问题

线程1：put c

1. table索引3: 3=b->a->null
2. 取出索引3节点：b->a->null
3. 创建新Entry value为c

线程2：put d

1. table索引3: 3=b->a->null
2. 取出索引3节点：b->a->null
3. 创建新Entry value为d
4. 节点d子节点置为原索引3节点，即：d->b->a->null
5. 索引3节点置为新节点，即：3=d->b->a->null

此时线程1继续执行

1. 节点c子节点置为原索引3节点，即：c->b->a->null
2. 索引3节点置为新节点，即：3=c->b->a->null

此时插入的节点d因并发原因丢失

HashMap-jdk1.8.0_271

put新增map元素

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
// put value
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {...else {for (int binCount = 0; ; ++binCount) {// 遍历hash冲突处的node节点，直至为node的子节点为null，即尾节点if ((e = p.next) == null) {// 执行尾部插入p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 存在相同hash与相同key的元素，直接终止遍历重写value值即可if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 当存在相同hash与相同key的元素时，重写value值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

并发插入问题

依然存在并发插入丢失节点问题，毕竟HashMap本身就是线程不安全

扩容问题

头插法改为尾插发解决了死循环问题

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冲突，直接迁移至新tableif (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 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;
}