先上源码(JDK1.7transfer)
1 void transfer(Entry[] newTable, boolean rehash) {
//获取新Entry数组的容量
2 int newCapacity = newTable.length;
//遍历旧的Entry数组
3 for (Entry<K,V> e : table) {
// e的下一个entry不为null则循环(链表上的循环)
4 while(null != e) {
5 Entry<K,V> next = e.next;
6 if (rehash) {
7 e.hash = null == e.key ? 0 : hash(e.key);
8 }
//根据e的hash值和容量计算出index值
9 int i = indexFor(e.hash, newCapacity);
//e的下一个Entry为新数组i位置上的值
10 e.next = newTable[i];
//e添加到新数组的i位置上
11 newTable[i] = e;
//next赋值给e
12 e = next;
13 }
14 }
15 }
总结下该函数的主要作用:
在对table进行扩容到newTable后,需要将原来数据转移到newTable中,注意10-12行代码,这里可以看出在转移元素的过程中,使用的是头插法,也就是链表的顺序会翻转,这里也是形成死循环的关键点。
先上源码(JDK1.8putVal)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果table为空,或者还没有元素时,则扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果首结点值为空,则创建一个新的首结点。
// 注意:(n - 1) & hash才是真正的hash值,也就是存储在table位置的index。在1.6中是封装成indexFor函数。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 到这儿了,就说明碰撞了,那么就要开始处理碰撞。
Node<K,V> e; K k;
// 如果在首结点与我们待插入的元素有相同的hash和key值,则先记录。
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);
// 当遍历的结点数目大于8时,则采取树化结构。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果找到与我们待插入的元素具有相同的hash和key值的结点,则停止遍历。此时e已经记录了该结点
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;
// 当结点数+1大于threshold时,则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 这个是空函数,可以由用户根据需要覆盖
return null;
}
这是jdk1.8中HashMap中put操作的主函数, 注意if ((p = tab[i = (n - 1) & hash]) == null)这行代码,如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作,刚好这两条不同的数据hash值一样,并且该位置数据为null,所以这线程A、B都会进入第6行代码中。假设一种情况,线程A进入后还未进行数据插入时挂起,而线程B正常执行,从而正常插入数据,然后线程A获取CPU时间片,此时线程A不用再进行hash判断了,问题出现:线程A会把线程B插入的数据给覆盖,发生线程不安全。
总结:
首先HashMap是线程不安全的,其主要体现:
- 在jdk1.7中,在多线程环境下,扩容时会造成环形链或数据丢失。
- 在jdk1.8中,在多线程环境下,会发生数据覆盖的情况。