问题11:hashmap底层技术、hashmap是线程不安全的

为什么线程不安全

一般我们声明HashMap时,使用的都是默认的构造方法:HashMap<K,V>,看了代码你会发现,它还有其它的构造方法:

 

HashMap(int initialCapacity, float loadFactor),

 

其中参数initialCapacity为初始容量,loadFactor为加载因子,扩容就是在put加入元素的个数超过initialCapacity * loadFactor的时候就会将内部Entry数组大小扩大至原来的2倍,然后将数组元素按照新的数组大小重新计算索引,放在新的数组中,同时修改每个节点的链表关系(主要是next和节点在链表中的位置)。

 

假设这里有两个线程同时执行了put()操作,并进入了transfer()环节:

刚开始:

线程1中的e指向key(0),next指向key(4),此时线程1挂起。

线程2调度完成所有节点的移动,移动后结果为:

线程1继续执行,线程一会把线程二的新表当成原始的hash表,将原来e指向的key(0)节点当成是线程二中的key(0),放在自己所建table[0]的头节点。注意线程1的next仍然指向key(4),

 

虽然此时key(0)的next已经是null。

执行e.next = newTable[i],于是 key(0)的 next 指向了线程1的新 Hash 表,因为新 Hash 表为空,所以e.next = null,

执行newTable[i] = e,所以线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(0)。好了,e 处理完毕。

执行e = next,将 e 指向 next,所以新的 e 是 key(4)

 

 

线程1的e指向了上一次循环的next,也就是key(4),此时key(4)的next已经是key(0)。将key(4)插入到table[0]的头节点,并且将key(4)的next设置为key(0)。此时仍然没有问题。

1、现在的 e 节点是 key(4),首先执行Entry<K,V> next = e.next,那么 next 就是 key(0)了

2、执行e.next = newTable[i],于是key(0) 的 next 就成了 key(4)

3、执行newTable[i] = e,那么线程1的新 Hash 表第一个元素变成了 key(4)

4、执行e = next,将 e 指向 next,所以新的 e 是 key(0)

 

1、现在的 e 节点是 key(0),首先执行Entry<K,V> next = e.next,那么 next 就是 null

2、执行e.next = newTable[i],于是key(0) 的 next 就成了 key(4)

3、执行newTable[i] = e,那么线程1的新 Hash 表第一个元素变成了 key(0)

4、执行e = next,将 e 指向 next,所以新的 e 是 key(4)

 

总结版:HashMap在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。