【源码学习】深入剖析核心源码之 ConcurrentHashMap（JDK1.7 和JDK1.8）

╰+哭是因爲堅強的太久メ 2023-07-18 09:41 34阅读 0赞

> 面试中常被问到的数据结构就是哈希表，一般都是先问HashMap，再接着问ConcurrentHashMap，所以深入学习源码以及相关的知识是很重要的。  
> 大家也可以参考我之前的[ 深入剖析核心源码之 HashMap][_ HashMap]

### 源码学习之 ConcurrentHashMap ###

*   *  1.为什么不继续使用HashMap？
     *  2.有什么方式保证多线程安全？
     *  3. Collections.synchronizedMap(Map)怎么实现的？
     *  4.HashTable又是怎么实现的？
     *  5. HashMap和HashTable的区别有哪些？
     *  6.ConcurrentHashMap在JDK1.7中是底层结构是怎样的？
     *  7.ConcurrentHashMap在JDK1.7中各种操作是怎样的？
     *  8.ConcurrentHashMap的JDK1.7版本有什么问题呢？
     *  9.ConcurrentHashMap在JDK1.8中是底层结构是怎样的？
     *  10.ConcurrentHashMap在JDK1.8中各种操作是怎样的？
     *  11.ConcurrentHashMap 1.7和1.8版本的异同

## 1.为什么不继续使用HashMap？ ##

> 因为HashMap在多线程的情况下不安全，只适合单线程下使用，在JDK1.7时，HashMap采用头插方式，这样如果使用多线程在扩容进行重新再散列后，就会产生环形链表的问题。虽然在1.8后优化为了尾插，解决了环形链表的问题，但由于它所有的方法都不是线程安全的，所有多线程环境下并不适合使用。

## 2.有什么方式保证多线程安全？ ##

一般在多线程下，有以下几种方式代替HashMap：

*  使用Collections.synchronizedMap(Map)创建线程安全的map集合；
 *  使用 Hashtable
 *  使用 ConcurrentHashMap

其中，ConcurrentHashMap的效率要高于前两种方式

## 3. Collections.synchronizedMap(Map)怎么实现的？ ##

首先传入一个我们自己的Map m后，会创建一个`SynchronizedMap`类的实例。

![在这里插入图片描述][20200328120030712.png] 接着，来看看`SynchronizedMap`类是怎么实现的： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70] 这个类维护了一个Map用来接收我们的传入参数，还维护了一个Object的对象用来作为锁对象，也可以自己传入一个对象作为锁对象。而在这个类的内部，定义的所有方法都是用`synchronized`关键字对mutex对象加锁包裹一个代码块，实现了多线程下的安全问题。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 1] 当然，使用这种方式的效率会很低，由于锁的是同一个对象，所以哪怕是两个线程同时想读取数据，其中一个也会被锁住。

## 4.HashTable又是怎么实现的？ ##

> 在前面学习的[ HashMap][_ HashMap]中，对于HashMap有个描述：HashMap和HashTable实现基本是相同的，除了HashMap是允许null为Key以及HashMap是线程不安全的。从这里就可以看出，HashTable与HashMap最大的不同就是它是线程安全的。而HashTable实现线程安全的方式也很简单粗暴，那就是**给每一个方法都加上synchronized关键字**

大家可以自己去查看源码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 2]

## 5. HashMap和HashTable的区别有哪些？ ##

>  *  线程安全性不同： HashMap不是线程安全的，Hashtable是线程安全的。
>  *  null为Key的要求不同：HashMap 中null 可以作为Key，而Hashtable中不可以。
>  *  实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。
>  *  初始化容量不同：HashMap 的初始容量为：**16**，Hashtable 初始容量为：**11**，两者的负载因子默认都是：0.75。
>  *  底层实现不同：HashMap底层采用 **数组+链表/红黑树** 来实现的，HashTable采用 **数组+链表**实现。
>  *  扩容机制不同：HashMap 扩容规则为当**前容量2倍**，Hashtable 扩容规则为**当前容量2倍 + 1**。
> 
>  *  迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 是fail—safe 的

小知识：

>  *  fail-fast （快速失败）：在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改）则会抛出Concurrent Modification Exception。java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）
>  *  fail—safe （安全失败）： 采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历，所以元素的更新不影响遍历。java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

## 6.ConcurrentHashMap在JDK1.7中是底层结构是怎样的？ ##

在JDK1.7 中使用的是**分段锁机制**，它的底层结构图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 3]  
其中Segment是一种**可重入锁**（ReentrantLock） 而HashEntry则用于存储键值对数据。这就实现了使用不同的锁锁住不同的数据段，避免了访问所有方法都竞争同一把锁，提高了并发效率。  
一个ConcurrentHashMap中包含着一个Segment数组，Segment结构 是**数组+链表**，也就是**一个Segment中包含一个HashEntry的数组，每个HashEntry又是一个链表结构的元素**（HahsEntry就像HashMap中的Node一样，是真正存放数据的桶）。也就是把HashMap的数组拆分成不同段，然后给不同段加上相应的Segment锁，这样，只有在对同一个Segment中的元素进行操作时才会加同一把锁，而对不同的Segment中元素操作时加不同的锁，不会由器线程阻塞。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 4]

## 7.ConcurrentHashMap在JDK1.7中各种操作是怎样的？ ##

**get操作：**

> 首先会进过一次再散列，得到散列值通过散列运算定位到对应的Segment，再通过散列算法定位到元素。 get操作的高效之处就在于**整个过程是不需要加锁**，为什么呢？因为它将所有的共享变量都定义成了**volatile类型**，这样就能保证变量在线程之间的**可见性**，能够被多线程同时读，且保证读到的都是最新的、正确的值。

**put操作：**

> 为了保证多线程安全，put操作是必须要加锁的。还是同样定位到相应的Segment后在其中插入元素，此时就考虑是否需要对Segment中的HashEntry扩容，如果需要扩容就会调用rehash方法将容量扩大为原来的两倍，注意，这里只是扩大某个Segment而不是整个Map

源码如下：

public V put(K key, V value) {
        
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key);
        int j = (hash >>> segmentShift) & segmentMask;
        if ((s = (Segment<K,V>)UNSAFE.getObject          
             (segments, (j << SSHIFT) + SBASE)) == null) 
            s = ensureSegment(j);
        return s.put(key, hash, value, false);
    }
    
    final V put(K key, int hash, V value, boolean onlyIfAbsent) {
        
       // 尝试获取锁，如果获取失败肯定就有其他线程存在竞争，利用 scanAndLockForPut() 自旋获取锁。
         HashEntry<K,V> node = tryLock() ? null :
             scanAndLockForPut(key, hash, value);
         V oldValue;
         try {
        
             HashEntry<K,V>[] tab = table;
             int index = (tab.length - 1) & hash;
             HashEntry<K,V> first = entryAt(tab, index);
             for (HashEntry<K,V> e = first;;) {
        
                 if (e != null) {
        
                     K k;
    // 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
                     if ((k = e.key) == key ||
                         (e.hash == hash && key.equals(k))) {
        
                         oldValue = e.value;
                         if (!onlyIfAbsent) {
        
                             e.value = value;
                             ++modCount;
                         }
                         break;
                     }
                     e = e.next;
           		}
                 else {
        
              // 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
                     if (node != null)
                         node.setNext(first);
                     else
                         node = new HashEntry<K,V>(hash, key, value, first); //新put的节点
                     int c = count + 1;
                     if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                         rehash(node); //扩容
                     else
                         setEntryAt(tab, index, node);
                     ++modCount;
                     count = c;
                     oldValue = null;
                     break;
                 }
             }
         } finally {
        
             unlock();
         }
         return oldValue;
     }

**size操作：**

> 要统计整个的size，就要统计所有的Segment离元素的大小后求和。虽然Segment里面的count变量是个volatile类型的变量，但还是不可以直接相加。因为不能保证在进行相加的这个过程中没有修改某一个Segment中的count值。第一个想到的就是把能使得count改变的操作都锁住，比如：put、remove等锁住，但这样实在是有些低效。  
> 因为在累加count时，之前的count变化的几率比较小，所以，ConcurrentHashMap做法就是**先尝试2次不锁的方式**来统计大小，如果在统计过程中，count发生了变化在采用加锁的方式统计大小。

## 8.ConcurrentHashMap的JDK1.7版本有什么问题呢？ ##

> 可以看出，1.7版本的 ConcurrentHashMap在线程安全问题上时做到位了，但还存在一点点的不足之处，那就是如果一个HashEntry中数据过多，那么在查询中只能遍历一遍，这样的时间复杂度就是 O(n) 查询的效率相对低下，所以在1.8版本又对 ConcurrentHashMap进行了进一步的改进。

## 9.ConcurrentHashMap在JDK1.8中是底层结构是怎样的？ ##

JDK1.8中ConcurrentHashMap采用**数据 + 链表/红黑树**的结构实现的，结构图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 5]  
在JDK1.8中，抛弃了原有的分段锁结构，改为了`CAS + synchronized` 来保证并发安全性。也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了**volatile**去修饰，保证了**可见性**，并且也引入了**红黑树**，在链表大于一定值的时候会转换（默认是8）。

## 10.ConcurrentHashMap在JDK1.8中各种操作是怎样的？ ##

**各种属性：**

//最大容量
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    //初始容量
    private static final int DEFAULT_CAPACITY = 16;
    //数组最大容量
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //默认并发度，兼容1.7及之前版本
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    //加载/扩容因子，实际使用n - (n >>> 2)
    private static final float LOAD_FACTOR = 0.75f;
    //链表转红黑树的节点数阀值
    static final int TREEIFY_THRESHOLD = 8;
    //红黑树转链表的节点数阀值
    static final int UNTREEIFY_THRESHOLD = 6;
    //当数组长度还未超过64,优先数组的扩容,否则将链表转为红黑树
    static final int MIN_TREEIFY_CAPACITY = 64;
    //扩容时任务的最小转移节点数
    private static final int MIN_TRANSFER_STRIDE = 16;
    //sizeCtl中记录stamp的位数
    private static int RESIZE_STAMP_BITS = 16;
    //帮助扩容的最大线程数
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    //size在sizeCtl中的偏移量
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
     
    // ForwardingNode标记节点的hash值（表示正在扩容）
    static final int MOVED     = -1; // hash for forwarding nodes
    // TreeBin节点的hash值，它是对应桶的根节点
    static final int TREEBIN   = -2; // hash for roots of trees
    static final int RESERVED  = -3; // hash for transient reservations
    static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
     
    //存放Node元素的数组,在第一次插入数据时初始化
    transient volatile Node<K,V>[] table;
    //一个过渡的table表,只有在扩容的时候才会使用
    private transient volatile Node<K,V>[] nextTable;
    //基础计数器值(size = baseCount + CounterCell[i].value)
    private transient volatile long baseCount;
    /**
     * 控制table数组的初始化和扩容，不同的值有不同的含义：
     * -1:表示正在初始化
     * -n:表示正在扩容
     * 0:表示还未初始化，默认值
     * 大于0：表示下一次扩容的阈值
     */
    private transient volatile int sizeCtl;
    //节点转移时下一个需要转移的table索引
    private transient volatile int transferIndex;
    //元素变化时用于控制自旋
    private transient volatile int cellsBusy;
    // 保存table中的每个节点的元素个数 长度是2的幂次方，初始化是2，每次扩容为原来的2倍
    // size = baseCount + CounterCell[i].value

**get操作：**

> 与1.7一样，**get方法是全程没有加锁的，但由于变量是volatile的，所以可以保证线程安全**。它的流程就是：
> 
> 1.  根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
> 2.  如果是红黑树那就按照树的方式获取值。
> 3.  如果不满足那就按照链表的方式遍历获取值。

源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 6]  
**put操作：**

> put操作就做了一些改动了，也是比较复杂的，它的流程如下：
> 
> 1.  根据 key 计算出 hashcode 找到下标索引
> 2.  判断是否需要进行初始化。
> 3.  如果定位出的Node为null，就利用 [CAS][] 尝试写入，无条件自旋保证成功。
> 4.  判断是否在进行扩容（别的线程在扩容，就帮助去扩容）
> 5.  如果都不满足，那就利用 synchronized 锁进行写入数据（分为链表和红黑树两种方式）。
> 6.  最后插入后，如果数量大于 TREEIFY\_THRESHOLD 则要转换为红黑树。

源码如下：

final V putVal(K key, V value, boolean onlyIfAbsent) {
        
    		//Key和value都不为空
            if (key == null || value == null) throw new NullPointerException();
            int hash = spread(key.hashCode()); //得到hash值
            int binCount = 0;
            for (Node<K,V>[] tab = table;;) {
        
                Node<K,V> f; int n, i, fh;
                if (tab == null || (n = tab.length) == 0) //进行初始化整个Map
                    tab = initTable();
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        
                //元素定位出的Node位置为null，表示可直接写入，使用CAS自旋直到写入成功
                    if (casTabAt(tab, i, null,
                                 new Node<K,V>(hash, key, value, null)))
                        break;                   // no lock when adding to empty bin
                }
                //看是否在进行扩容
                else if ((fh = f.hash) == MOVED)
                    tab = helpTransfer(tab, f);
                else {
        
                //在桶或红黑树中插入数据，使用synchronized锁住要插入的位置节点
                    V oldVal = null;
                    synchronized (f) {
        
                        if (tabAt(tab, i) == f) {
        
                        //链表形式插入
                            if (fh >= 0) {
        
                                binCount = 1;
                                for (Node<K,V> e = f;; ++binCount) {
        
                                    K ek;
                                    if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                         (ek != null && key.equals(ek)))) {
        
                                        oldVal = e.val;
                                        if (!onlyIfAbsent)
                                            e.val = value;
                                        break;
                                    }
                                    Node<K,V> pred = e;
                                    if ((e = e.next) == null) {
        
                                        pred.next = new Node<K,V>(hash, key,
                                                                  value, null);
                                        break;
                                    }
                                }
                            }
                            //红黑树形式插入
                            else if (f instanceof TreeBin) {
        
                                Node<K,V> p;
                                binCount = 2;
                                if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                               value)) != null) {
        
                                    oldVal = p.val;
                                    if (!onlyIfAbsent)
                                        p.val = value;
                                }
                            }
                        }
                    }
                    //插入后看链表是否需要树化
                    if (binCount != 0) {
        
                        if (binCount >= TREEIFY_THRESHOLD)
                            treeifyBin(tab, i);
                        if (oldVal != null)
                            return oldVal;
                        break;
                    }
                }
            }
            addCount(1L, binCount);
            return null;
        }

> JDK1.7到1.8对ConcurrentHashMap有着很大的修改，最大的还是将原本的segment分段锁改为了CAS和synchronized（空节点插入用CAS，有节点插入用synchronized），因为在1.6以后，synchronized进行优化后，不像之前那样 “ 笨重 ” 而是加上了[偏向锁，轻量级锁，重量级锁][Link 1] 之间的一个锁膨胀的过程，所以1.8优化后不仅保证了高效率下的线程安全，同时解决了1.7中查询效率慢的问题，改为红黑树后，查询效率大大提高。

综合而言，1.8的ConcurrentHashMap已经很接近HashMap了，只是增加了并发控制，所以在理解了HashMap的设计后再理解ConcurrentHashMap，就比较容易了。

## 11.ConcurrentHashMap 1.7和1.8版本的异同 ##

相同点：

> 1.  读操作都没加锁，使用volatile保证了可见性
> 2.  读写分离，无论是对Segment加锁还是对Node加锁，只是对一部分数据加锁，多线程对于不同的Segment和Node都可以并发执行。
> 3.  使用fail-safe迭代器，创建迭代器后可对元素进行更新

不同点：

> 1.  JDK1.7 使用数组加链表，1.8使用数组+链表/红黑树
> 2.  JDK1.7 使用分段锁机制，基于ReentrantLock实现，JDK1.8基于CAS和synchronized实现

--------------------

> **唠唠叨叨**：  
> 在理解HashMap的基础上再来理解HashTable和ConcurrentHashMap就会容易很多，也要理解1.7和1.8的异同点以及各自的put方法都是重点，还有很多细节点都需要自己一点点去看源码理解。文章如果有什么问题欢迎留言指正，另外如果对你有帮助也欢迎小伙伴们点赞关注一起进步！

[_ HashMap]: https://blog.csdn.net/Moo_Lavender/article/details/104479183
[20200328120030712.png]: https://img-blog.csdnimg.cn/20200328120030712.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020032812241687.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 1]: /images/20230528/45968ccb9e95435f8ae4d76e0055bf81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 2]: /images/20230528/043d36bb93e149568a8e7a736827f74f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 3]: /images/20230528/e8bb8eac7a7f4d5bb17e8316eb54a55f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 4]: /images/20230528/100f28c8bfc245258f8dccaf460d96d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 5]: /images/20230528/42810c05a79d47b795a632ff7887defd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01vb19MYXZlbmRlcg_size_16_color_FFFFFF_t_70 6]: /images/20230528/09f0d780cea947929d63fcc6b9de37cf.png
[CAS]: https://blog.csdn.net/Moo_Lavender/article/details/105013580
[Link 1]: https://blog.csdn.net/Moo_Lavender/article/details/105134739