HashMap学习笔记

HashMap线程不安全体现在会造成死循环、数据丢失、数据覆盖这些问题。其中死循环和数据丢失是在JDK1.7中出现的问题，在JDK1.8中已经得到解决，然而1.8中仍会有数据覆盖这样的问题。

JDK1.7的Entry<K,V>（JDK1.8改成了 Node）:

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;//key的hashcode值
......
}

JDK1.7 扩容代码：

void transfer(Entry[] newTable, boolean rehash) {
//新hashMap的大小
int newCapacity = newTable.length;
//重新hash原数组(table)的数据找到新数组(newTable)中的新位置
for (Entry<K,V> e : table) {
 //链表中最后一个元素的next为null则退出，进入上一层继续对数组中的下一个链表中的元素进行操作
 while(null != e) {
   //初始化next指向操作元素的下一个，防止丢失
   Entry<K,V> next = e.next;
   if (rehash) {
     e.hash = null == e.key ? 0 : hash(e.key);
   }
   //计算新位置，i可能是新的（无值）可能是旧的（有值）
   int i = indexFor(e.hash, newCapacity);
   //操作元素指向新位置的元素（头插法），此时e是操作元素和原i位置元素的链表
   e.next = newTable[i];
   //新数组newTable第i个赋值e（操作元素和原i位置元素的链表），至此完成对一个元素的重新hash
   newTable[i] = e;
   //对e重新赋值下一个要操作的元素（即链表的下一个元素）
   e = next;
 }
}
}

扩容会造成死循环的简单描述：
线程A,线程B同时对HashMap进行扩容操作，线程A操作到 newTable[i] = e; 时CPU分配的时间片用完*挂起，而线程B完成了扩容过程。当线程A再次被唤醒时会继续从中断位置开始执行，table和newTable是线程B扩容后的了，由于头插法会导致以后循环的时候产生闭环。 扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。

多线程put时可能会导致数据丢失：
主要问题出在addEntry方法的new Entry (hash, key, value, e)，如果两个线程都同时取得了e,则他们下一个元素都是e，然后赋值给table元素的时候有一个成功有一个丢失。

JDK1.8 put值代码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//多个线程进入会导致值覆盖
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

JDK1.8的扩容做了优化，每次扩容都是原长度的2倍， 所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash值了。

JDK1.8的hash方法做了优化，低16位和高16位进行异或计算，这样就保证在数组比较小时候hashcode的高低位都能参与到运算中，防止一些散列不均匀的情况。

参考博客（有图）：https://blog.csdn.net/swpu_ocean/article/details/88917958

Q&A:

Q：Hashtable扩容的数组长度为什么是旧数组长度乘以2加1？

A：Hashtable中数组的长度尽量为素数或者奇数，同时Hashtable采用取模的方式来计算数组下标，这样减少Hash碰撞，计算出来的数组下标更加均匀。但是这样效率会比HashMap利用位运算计算数组下标低。

Q：Hashtable为什么采用头插法的方式迁移数组？

A：采用头插法的方式效率更高。如果采用尾插法需要遍历数组将元素放置到链表的末尾，而采用头插法将结点放置到链表的头部，减少了遍历数组的时间，效率更高。

Q：JDK1.8前HashMap也是采用头插法迁移数据，多线程情况下会造成死循环，JDK1.8对HashMap做出了优化，为什么JDK1.8Hashtable还是采用头插法的方式迁移数据？

A：Hashtable是线程安全的，所以Hashtable不需要考虑并发冲突问题，可以采用效率更高的头插法。

Q：为什么Hashtable渐渐被弃用？

A：Hashtable使用synchronized来实现线程安全，在多并发的情况下效率低下。

本文地址：https://blog.csdn.net/qq_36042338/article/details/107689175