ConcurrentHashMap的锁

悠悠 2022-06-09 01:23 222阅读 0赞

ConcurrentHashMap是Java5中新增加的一个线程安全的Map集合。对于ConcurrentHashMap是如何提高其效率的，可能大多人只是知道它使用了多个锁代替HashTable中的单个锁，也就是锁分离技术（Lock Stripping）。实际上，ConcurrentHashMap对提高并发方面的优化，还有一些其它的技巧在里面（比如在get操作的时候它是否也使用了锁来保护？）。

**相比较与HashMap、HashTable：**

对于哈希表，Java中采用链表的方式来解决hash冲突的。  
一个HashMap的数据结构看起来类似下图：  
![T1RhSyXA4fXXXFjgjHLAIWANG1022m_63a092b0_1280_689.jpg][]

实现了同步的HashTable也是这样的结构，它的同步使用锁来保证的，并且所有同步操作使用的是同一个锁对象。这样若有n个线程同时在get时，这n个线程要串行的等待来获取锁。

**ConcurrentHashMap中对这个数据结构，针对并发稍微做了一点调整。**  
它把区间按照并发级别(concurrentLevel)，分成了若干个segment。默认情况下内部按并发级别为16来创建。对于每个segment的容量，默认情况也是16。当然并发级别(concurrentLevel)和每个段(segment)的初始容量都是可以通过构造函数设定的。

创建好默认的ConcurrentHashMap之后，它的结构大致如下图：  
![T15NSxXspiXXXqt03KLAIWANG102zx_662174d7_1280_777.jpg][]

看起来只是把以前HashTable的一个hash bucket创建了16份而已。有什么特别的吗？没啥特别的。

**继续看每个segment是怎么定义的：**

static final class Segment<K,V> extends ReentrantLock implements Serializable

Segment继承了ReentrantLock，表明每个segment都可以当做一个锁。这样对每个segment中的数据需要同步操作的话都是使用每个segment容器对象自身的锁来实现。只有对全局需要改变时锁定的是所有的segment。

上面的这种做法，就称之为**“分离锁（lock striping）”**。有必要对**“分拆锁”**和**“分离锁”**的概念描述一下：

> **分拆锁(lock spliting)**就是若原先的程序中多处逻辑都采用同一个锁，但各个逻辑之间又相互独立，就可以拆(Spliting)为使用多个锁，每个锁守护不同的逻辑。  
> 分拆锁有时候可以被扩展，分成可大可小加锁块的集合，并且它们归属于相互独立的对象，这样的情况就是**分离锁(lock striping)**。（摘自《Java并发编程实践》）

**get,put,remove这三个函数怎么保证数据同步的：**

看上去，单是这样就已经能大大提高多线程并发的性能了。下面继续看我们关注get,put,remove这三个函数怎么保证数据同步的。

先看get方法：

public V get(Object key) {
        int hash = hash(key); // throws NullPointerException if key null
        return segmentFor(hash).get(key, hash);
    }

它没有使用同步控制，交给segment去找，再看Segment中的get方法：

V get(Object key, int hash) {
            if (count != 0) { // read-volatile // ①
                HashEntry<K,V> e = getFirst(hash); 
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)  // ② 注意这里
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
    }

它也没有使用锁来同步，只是判断获取的entry的value是否为null，为null时才使用加锁的方式再次去获取。

这个实现很微妙，没有锁同步的话，靠什么保证同步呢？我们一步步分析。

第一步，先判断一下 count != 0；count变量表示segment中存在entry的个数。如果为0就不用找了。  
假设这个时候恰好另一个线程put或者remove了这个segment中的一个entry，会不会导致两个线程看到的count值不一致呢？  
看一下count变量的定义： `transient volatile int count;`  
它使用了volatile来修改。Java5之后，JMM实现了对volatile的保证：对volatile域的写入操作happens-before于每一个后续对同一个域的读写操作。  
所以，每次判断count变量的时候，即使恰好其他线程改变了segment也会体现出来。

第二步，获取到要该key所在segment中的索引地址，如果该地址有相同的hash对象，顺着链表一直比较下去找到该entry。当找到entry的时候，先做了一次比较： `if(v != null)` 我们用红色注释的地方。  
这是为何呢？

考虑一下，如果这个时候，另一个线程恰好新增/删除了entry，或者改变了entry的value，会如何？

先看一下HashEntry类结构。

static final class HashEntry<K,V> {
        final K key;
        final int hash;
        volatile V value;
        final HashEntry<K,V> next;
        。。。
    }

除了 value，其它成员都是final修饰的，也就是说value可以被改变，其它都不可以改变，包括指向下一个HashEntry的next也不能被改变。（那删除一个entry时怎么办？后续会讲到。）

1) 在get代码的①和②之间，另一个线程新增了一个entry  
如果另一个线程新增的这个entry又恰好是我们要get的，这事儿就比较微妙了。

下图大致描述了put 一个新的entry的过程。  
![T1fX9AXqxdXXXTyB6SLAIWANG103b0_353917e0_1280_696.jpg][]

因为每个HashEntry中的next也是final的，没法对链表最后一个元素增加一个后续entry  
所以新增一个entry的实现方式只能通过头结点来插入了。

newEntry对象是通过 `new HashEntry(K k , V v, HashEntry next)` 来创建的。如果另一个线程刚好new 这个对象时，当前线程来get它。因为没有同步，就可能会出现当前线程得到的newEntry对象是一个没有完全构造好的对象引用。

这里会出现我们常讨论的DCL的问题，没有锁同步的话，new 一个对象对于多线程看到这个对象的状态是没有保障的，这里同样有可能一个线程new这个对象的时候还没有执行完构造函数就被另一个线程得到这个对象引用。  
所以才需要判断一下：`if (v != null)` 如果确实是一个不完整的对象，则使用锁的方式再次get一次。

有没有可能会put进一个value为null的entry？ 不会的，已经做了检查，这种情况会抛出异常，所以 ②处的判断完全是出于对多线程下访问一个new出来的对象的状态检测。

2) 在get代码的①和②之间，另一个线程修改了一个entry的value  
value是用volitale修饰的，可以保证读取时获取到的是修改后的值。

3) 在get代码的①之后，另一个线程删除了一个entry

假设我们的链表元素是：e1-> e2 -> e3 -> e4 我们要删除 e3这个entry  
因为HashEntry中next的不可变，所以我们无法直接把e2的next指向e4，而是将要删除的节点之前的节点复制一份，形成新的链表。它的实现大致如下图所示：

![T1ywGnXzhhXXclcY3HLAIWANG103b1_e28c76ed_1280_647.jpg][]

如果我们get的也恰巧是e3，可能我们顺着链表刚找到e1，这时另一个线程就执行了删除e3的操作，而我们线程还会继续沿着旧的链表找到e3返回。  
这里没有办法实时保证了。

我们第①处就判断了count变量，它保障了在 ①处能看到其他线程修改后的。  
①之后到②之间，如果再次发生了其他线程再删除了entry节点，就没法保证看到最新的了。

不过这也没什么关系，即使我们返回e3的时候，它被其他线程删除了，暴漏出去的e3也不会对我们新的链表造成影响。

这其实是一种乐观设计，设计者假设 ①之后到②之间 发生被其它线程增、删、改的操作可能性很小，所以不采用同步设计，而是采用了事后（其它线程这期间也来操作，并且可能发生非安全事件）弥补的方式。  
而因为其他线程的“改”和“删”对我们的数据都不会造成影响，所以只有对“新增”操作进行了安全检查，就是②处的非null检查，如果确认不安全事件发生，则采用加锁的方式再次get。

这样做减少了使用互斥锁对并发性能的影响。可能有人怀疑remove操作中复制链表的方式是否代价太大，这里我没有深入比较，不过既然Java5中这么实现，我想new一个对象的代价应该已经没有早期认为的那么严重。

我们基本分析完了get操作。对于put和remove操作，是使用锁同步来进行的，不过是用的ReentrantLock而不是synchronized，性能上要更高一些。它们的实现前文都已经提到过，就没什么可分析的了。

我们还需要知道一点，ConcurrentHashMap的迭代器不是Fast-Fail的方式，所以在迭代的过程中别其他线程添加/删除了元素，不会抛出异常，也不能体现出元素的改动。但也没有关系，因为每个entry的成员除了value都是final修饰的，暴漏出去也不会对其他元素造成影响。

[T1RhSyXA4fXXXFjgjHLAIWANG1022m_63a092b0_1280_689.jpg]: /images/20220609/727ae58cdf1a4e2385dfe95d6b4058cf.png
[T15NSxXspiXXXqt03KLAIWANG102zx_662174d7_1280_777.jpg]: /images/20220609/e18787bcee5f4632a9ce4510bae88194.png
[T1fX9AXqxdXXXTyB6SLAIWANG103b0_353917e0_1280_696.jpg]: /images/20220609/917c76c8b6d34efbada87631d79b36ee.png
[T1ywGnXzhhXXclcY3HLAIWANG103b1_e28c76ed_1280_647.jpg]: /images/20220609/781d733d19704813a698b1290aa88574.png