HashMap不安全后果及ConcurrentHashMap线程安全原理

时间:2022-09-14 19:56:05

Java集合HashMap不安全后果及ConcurrentHashMap 原理

HashMap

Map是我们在集合中非常重要的一个集合、我们刚学习HashMap的时候就说它不安全、可是不知道不安全会发生什么后果

我们先来看看JDK7和JDK8当中的HashMap有什么不一样

JDK7 JDK8
数据结构 数组+ 链表。复杂度:O(n) 数组 + 链表 + 红黑树
插入位置 头插法 尾插法

JDK7 HashMap链表循环造成死循环

造成HasMap链表循环列表的原因就是因为在hash冲突的时候采用了头插法且没有加锁的方式插入链表、在HashMap put的时候,put函数会检查元素是否超出了阈值【数组的总的添加元素数大于了 数组长度 * 0.75(默认,也可自己设定)】,如果超出了数组长度扩容为两倍,下面是它扩容时将旧hash表转到新hash表从而完成扩容的源代码

 /**
   * 作用:将旧数组上的数据(键值对)转移到新table中,从而完成扩容
   * 过程:按旧链表的正序遍历链表、在新链表的头部依次插入。但是这样会导致扩容完成后,链表逆序
   */ 	
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //通过遍历 旧数组,将旧数组上的数据(键值对)转移到新数组中
        for (Entry<K,V> e : table) {
            // 遍历hash碰撞形成的链表
            while(null != e) {
                // 拿到当前头节点的下一个节点
                Entry<K,V> next = e.next;
                // 是否要重新计算hashCode
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                 //通过hashCode计算出hash表的槽
                int i = indexFor(e.hash, newCapacity);
                // 新hash表的hash槽赋值给e 的下一个节点
                e.next = newTable[i];
                // 讲当前元素,赋给新数组的对应下标位置。
                newTable[i] = e;
                // 访问下1个Entry链上的元素,如此不断循环,直到遍历完该链表上的所有节点
                e = next;
            }
        }
    }

在单线程中,这样的代码是没有什么问题,问题就是有很多个线程,我们假设有两个线程t1和t2,他们都执行到Entry<K,V> next = e.next;这一行,此时图示:

HashMap不安全后果及ConcurrentHashMap线程安全原理

,t1的时间片已经用完了,t2还在继续执行,此时t1、t2获取的e和next分别为e1、e2、next1、next2,再之后t2完成了扩容操作,链表顺序已经从原来的abcd变成了dcba,t1线程的e在next的上方,如下图示:

HashMap不安全后果及ConcurrentHashMap线程安全原理

此时t1线程醒过来了,继续执行就会出现链表循环,造成while死循环

HashMap不安全后果及ConcurrentHashMap线程安全原理

JDK8 HashMap中已经采用尾插法进行插入避免了链表循环、且链表长度大于8会变成红黑树

HashMap数据丢失

jdk7:hashMap put的时候有hash冲突如果没有超过阈值,就会采用头插法来插入链表,假如有t1和t2线程,它们都同时获得了,链表的头节点,此时t1线程的时间片没有了,t2线程还在继续,t2线程已经执行完了put操作,t1线程醒过来,t1线程会将自己的下一个节点指向头节点,这样刚刚t2线程put的节点就丢失了

jdk8: 采用的是尾插法、一样的两个线程都同时获取了尾节点、后执行的那个线程会覆盖掉前一个线程的节点、造成丢失

HashMap在官方的设定的就是线程不安全的,要安全选ConcurrentHashMap

JDK7 ConcurrentHashMap

在jdk7 ConcurrentHashMap当中采用了一个分段锁的方式(Segment[])来保证线程安全

HashMap不安全后果及ConcurrentHashMap线程安全原理

Segment类继承了ReentrantLock,Segment类里有多个槽。

put:

计算出key在那个Segment,然后上锁,再算出在哪个槽里,此时如果有其它线程访问这个Segment会被阻塞住,直到unlock。

get:

CAS + volatile

在HashTable当中是锁住了整个对象,线程t1 get("key1") 、线程t2 put("key2", "value2"),线程t2也会被阻塞住,在ConcurrentHashMap中这两个操作是不会阻塞且不受影响。

值得注意的是Segment[]的初始长度,默认是16,不会因为数据的多少而改变,所以默认最多只有16个线程获得锁,这个初始值可以设置,但是需要我们自己去评估多少合适。

Segment分段锁实现下的ConcurrentHashMap的劣势:

  • 寻找元素需要经过两次hash
  • 并发级别(Segment[]长度)的合理设置问题。虽然提供了默认的并发级别,但是是否在大多数场景下都适用?归根结底,就是需要用户自己来评估需要多少把锁来分段治理的问题。
  • 在存储成本比HashMap高。每个Segment管理的最少容量是2,而默认的并发级别为16,即16个Segment。假如我只需要存储的是16个元素,那么ConcurrentHashMap会需要占用2倍的存储空间。

JDK8 ConcurrentHashMap

在JDK8中,ConcurrentHashMap采用更加细粒度的锁取消分段锁,synchronized + CAS

put:

如果发现该槽没有数据,初始化头节点时,ConcurrentHashMap并没有加锁,而是CAS的方式进行原子替换(原子操作,基于Unsafe类的原子操作API)

如果发现该槽有数据,判断是否正在扩容,如果是则会去帮助扩容,扩容时会进行加锁处理,锁定是头节点。

如果发现该槽有节点且不在扩容,则会去锁(synchronized)住该槽的头节点,进行插入

get:

没有什么加锁的操作,hash表被volatile修饰