03、ConcurrentHashMap的get()方法真的不需要加锁吗?

一、前言

我们都知道,ConcurrentHashmap这个并发集合框架是线程安全的,当我们看get()方法的源码时,会发现get操作全程没有加锁。但是真的是这样的吗?本文我们就深入的看看它为什么大家都说它不需要加锁?是不是真的不需要加锁?留个悬念,在一种特殊场景下是要加锁的。

二、ConCurrentHashMap#get()方法

1、流程:

1、 使用扰动函数计算key的hash值,取到其所在的数组下标位置;
2、 如果节点是首节点,直接返回;
3、 如果节点的hasheh是负值,说明ConCurrentHashMap正在进行扩容,或该节点是一个树节点TreeBin;

  1. 如果eh=-1表示正在扩容,该节点是一个 ForwardingNode(树头节点),直接调用ForwardingNode的find方法去nextTable里找;
  2. 如果eh=-2,该节点是一个TreeBin,调用TreeBin的find()方法遍历红黑树,由于红黑树有可能在变色旋转,所以find()里会有读写锁

1、 最后如果eh>0说明节点是链表,遍历链接即可;

public V get(Object key) {

    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // 计算key的hash值
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {

      // 读取首节点的Node元素
        // 如果当前节点的hash值和首节点的Hash值相同,并且value也相同,直接返回。
        if ((eh = e.hash) == h) {

            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // hash为负值,表示正在扩容。这时需要用到ForwardingNode的find()方法定位到nextTable。
        //   1) eh=-1,说明该节点是一个ForwardingNode,正在扩容迁移,此时调用ForwardingNode的find()方法去nextTable里找
        //   2) eh=-2,说明该节点是一个TreeBin,此时调用TreeBin的find()方法遍历红黑树,注意:由于红黑树可能正在旋转变色,所以find()方法里会加一个读写锁。
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        // eh >=0 说明该节点是一个链表节点,直接遍历链表即可。
        while ((e = e.next) != null) {

            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

2、get()方法如何保证读取到的数据不是脏数据?

get()方法常规情况下没有加锁,却保证读到的数据不是脏数据。这是因为volatile的作用:保证可见性。

关于volatile?

volatile是Java提供的一种轻量级的同步机制,能够保证线程可见性、禁止指令重排序。也就是当给一个非引用变量值加volatile修饰之后,能够保证一个线程对改变量值的改变,另一个线程可以即时看到。

3、我们看一下Node#find()方法

其有四个实现:
&nbsp;

ForwardingNode表示一个因为扩容而正在移动中的节点;
ReservationNode表示一个空节点,加锁时使用;
TreeNode表示红黑树中普通的节点;
TreeBin表示红黑树的根节点,封装了红黑树中左旋、右旋、新增节点、删除节点等维护红黑树平衡的逻辑。

我们主要看一下TreeBin#find()方法。

该方法多了一个基于CAS实现的读写锁

  1. 通过TreeBin查找某个节点时,如果当前写锁被占用或者有等待获取写锁的线程,表示红黑树处于正在调整的过程中,则遍历链表查找;
  2. 如果写锁没有被占用且没有等待的线程,则抢占读锁遍历红黑树的节点来查找;
  3. 读锁释放时会判断是否所有的读锁都释放了,如果都释放了且当前有等待获取写锁的线程,则唤醒正在等待中的线程。
/**
 * Returns matching node or null if none. Tries to search
 * using tree comparisons from root, but continues linear
 * search when lock not available.
 */
final Node<K,V> find(int h, Object k) {

    if (k != null) {

        for (Node<K,V> e = first; e != null; ) {

            int s; K ek;
            // 如果当前读写锁的状态是WAITER或者WRITER,则通过链表遍历查找,此时红黑树正在调整的过程中。
            if (((s = lockState) & (WAITER|WRITER)) != 0) {

                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
                e = e.next;
            }
            // //如果不是上述两种状态,则将状态设置为READER,每次都会加上READER,表示正在遍历红黑树,此时就不能调整红黑树了
            else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                         s + READER)) {

                TreeNode<K,V> r, p;
                try {

                    // 如果根节点为null,则返回null;否则通过根节点查找匹配的节点。注意:进入此方法根节点不可能为null
                    p = ((r = root) == null ? null :
                         r.findTreeNode(h, k, null));
                } finally {

                    Thread w;
                    if (U.getAndAddInt(this, LOCKSTATE, -READER) == //所有的读锁都释放了
                        (READER|WAITER) && (w = waiter) != null) //且有等待获取写锁的线程
                        // 唤醒该线程
                        LockSupport.unpark(w);
                }
                return p;
            }
        }
    }
    return null;
}

三、总结

1、ConcurrentHashMap的get方法需要加锁吗?

1)java8中ConcurrentHashMap的get()操作正常情况是不需要加锁的,这也是它比其他并发集合,如hashtable、用Collections.synchronizedMap()包装的hashmap;效率高的原因之一。
2)正常情况get()操作全程不需要加锁是因为:

  1. get()方法访问的大多数变量是volatile关键字修饰的,比如:Node.val、Node.next、count,volatile保证了其值的修改对其他线程的可见性。
    :在多线程环境下线程A修改Node节点的val或者新增节点对线程B是可见的。
  2. 像引用类型:数组table用volatile修饰,在数组扩容的时候就保证了其引用的改变对其他线程的可见性。

3)但是当节点是红黑树的时候,如果树正在变色旋转并且要查询的值不是红黑树的头节点,会加一个读写锁
4)另外其迭代器iterator是弱一致性的,因为在迭代过程中可以向map中添加元素;而HashMap是强一致性的。

最后我们再聊一下ConcurrentHashMap中变量使用final和volatile修饰的作用。

2、ConcurrentHashMap中变量使用final和volatile修饰的作用?

  • final域确保变量初始化的安全性,初始化安全性让不可变对象不需要同步就可以被自由的访问和共享。
  • volatile关键字保证某个变量在内存的改变对其他线程即时可见;再配合CAS可以实现无锁并发操作。
  • 而get()方法可以无锁,是由于Node的元素val和指针next都是volatile修改的,在多线程环境下线程A修改节点的val或者新增节点对线程B是可见的。