为什么HashMap是线程不安全的？

2019-07-22 本文已影响85人 Sophia_dd35

一、背景

HashMap的扩容机制就是重新申请一个容量是当前容量2倍的桶数组，然后将旧数组中的元素逐个映射到新的数组里边，然后将原先的桶逐个置为引用失效。HashMap之所以线程不安全，就是resize这里出的问题。

二、线程不安全场景

1、put的时候导致的多线程数据不一致。
这个问题比较好想象，比如有两个线程A和B，首先A希望先插入一个key-value到HashMap中，首先计算key-value索引位置，然后获取到该桶里面链表的头节点，并且key不存在桶中，需要新建节点插入，此时线程A的时间片用完了；线程B被调度得以执行，和线程A一样执行，但线程B比较幸运，成功的将key-vaule插入到了链表中，随后线程A再次被调度运行时，它依然持有过期的链表头但它对此一无所知，如此一来就覆盖了线程B插入的记录，但线程B插入的记录就凭空消失了。

void createEntry(int hash, K key, V value, int bucketIndex) { 

    // 1. 把table中该位置原来的Entry保存  
    Entry<K,V> e = table[bucketIndex];

    // 2. 在table中该位置新建一个Entry：将原头结点位置（数组上）的键值对 放入到（链表）后1个节点中、将需插入的键值对 放入到头结点中（数组上）-> 从而形成链表
    // 即 在插入元素时，是在链表头插入的，table中的每个位置永远只保存最新插入的Entry，旧的Entry则放入到链表中（即 解决Hash冲突）
    table[bucketIndex] = new Entry<>(hash, key, value, e);  

    // 3. 哈希表的键值对数量计数增加
    size++;  
}

2、HashMap的get操作死循环
达到resize条件，两个线程各自进行resize的第一步-扩容。让我们回顾一下ReHash源码

//resieze的核心源码如下
//这个方法的功能时将原来的记录重新计算在新桶的位置，然后迁移过去
void transfer(Entry[] newTable, boolean rehash) {  
        int newCapacity = newTable.length;  
        for (Entry<K,V> e : table) {  
  
            while(null != e) {  
                Entry<K,V> next = e.next;          
                if (rehash) {  
                    e.hash = null == e.key ? 0 : hash(e.key);  
                }  
                int i = indexFor(e.hash, newCapacity);   
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
            } 
        }  
    }

从上面可看出：在扩容resize（）过程中，在将旧数组上的数据转移到新数组上时，转移数据操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况
此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则容易出现环形链表，从而在获取数据、遍历链表时形成死循环（Infinite Loop），即死锁的状态。