ConcurrentHashMap（jdk1.8）讲解及常见面试题

柔情只为你懂 2023-10-01 17:22 29阅读 0赞

#### 文章目录 ####

*  前言
 *  一、ConcurrentHashMap存储结构
 *  二、存储元素
 *   *  1、第一步：初始化数组长度
     *  2、第二步：索引位为空时存储元素
     *  3、第三步：索引位不为空时存储元素
     *  4、第四步：并发扩容
 *  三、ConcurrentHashMap常见面试题
 *   *  1、ConcurrentHashMap使用什么技术来保证线程安全？
     *  2、HashMap 和 ConcurrentHashMap 的区别
     *  3、ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？
     *  4、ConcurrentHashMap默认初始容量是多少？
     *  5、ConCurrentHashmap 的key，value是否可以为null？为什么？
     *  6、ConCurrentHashmap 每次扩容是原来容量的几倍
     *  7、ConCurrentHashmap的数据结构是怎么样的？
     *  8、ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？

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

## 前言 ##

我们都知道HashMap是线程不安全的，而ConcurrentHashMap是线程安全的。在1.8中，两者之间的数据结构是一样的，但是它们的底层代码却有一些很大的不同，让我们来看看ConcurrentHashMap是如何实现线程安全的！

## 一、ConcurrentHashMap存储结构 ##

DK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的Node数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 `Segment 分段锁`，采用`CAS + synchronized`实现更加细粒度的锁。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]

## 二、存储元素 ##

### 1、第一步：初始化数组长度 ###

**问题：多线程并发的情况，可能会导致多个线程同时进行初始化数组操作**

**解决：CAS乐观锁，这个办法，就让一个线程在初始化的时候，其他线程如果进来了，就在外面等着。**

当tab也就是原来的数组为空的时候，就要进行初始化数组过程，调用initTable()方法。  
![在这里插入图片描述][8165868016b349c49fdbbe89790c7433.png]  
初始化数组initTable()

private final Node<K,V>[] initTable() {
        
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
        
            if ((sc = sizeCtl) < 0) //SIZECTL<0时，说明已经有线程在初始化数组，那么就让线程等待
                Thread.yield(); //线程让步
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
          //当SIZECTL等于sc时，将SIZECTL值设为-1。成功返回true，失败返回false
                try {
        
                //初始化
                    if ((tab = table) == null || tab.length == 0) {
        
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;  //sc<0的时候取一个默认容量16
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; //创建一个初始化长度为16的数组
                        table = tab = nt;  //赋值给tab和table
                        sc = n - (n >>> 2);  //12，相当于扩容阈值
                    }
                } finally {
        
                    sizeCtl = sc; //12
                }
                break;
            }
        }
        return tab;
    }
    ------------------------------
    sizeCtl三个值代表的意思
    sizeCtl=0  :  未初始化
    sizeCtl=-1  :  有线程正在初始化
    sizeCtl=12  :  预扩容大小

SIZECTL其实就是内存中sizeCtl值  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
CAS – compareAndSwapInt（Object obj, long offset, int expect, int update）实际上就是在比较某个对象(obj)的某个字段在内存的值(offset)和期望(expect)，如果offset==expect，就更新(update)。

**总结：iniTable()通过CAS机制，将内存中sizeCtl（通过SIZECTL得到）值，与sc进行比较，如果相等返回true并替换SIZECTL=-1，接着就执行初始化数组(16)的过程了。当下一个线程进来的时候，因为sizeCtl已经是-1了，就会执行Thread.yield()让步，此刻保证初始化过程中的线程安全。**

### 2、第二步：索引位为空时存储元素 ###

初始化过程结束了之后，要继续进行判断索引位置上是否有节点，没有节点的话就创建一个节点，和HashMap类似，但是在存储的过程中也要考虑线程安全。

**问题：多线程并发的情况，可能会存在多个线程同时在一个位置上放元素情况。比如说一个null的地方，线程t1和线程t2同时进来得到null信息，也就会同时创建新节点。**

**解决：采用CAS，判断i和null是否相等，是则替换i的值不为空，这样下一个并发线程进来的时候就无法重复put。**

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        
        if (casTabAt(tab, i, null,
                     new Node<K,V>(hash, key, value, null)))
            break;                   // no lock when adding to empty bin
    }

比HashMap多了一个步骤就是casTabAt()，也是CAS机制：在这个tab中，判断i和null是否相等，如果相等才可以创建新节点。

### 3、第三步：索引位不为空时存储元素 ###

依旧是为了保证多线程并发时的线程安全，之前说过1.7采用的是Segment 分段锁，而1.8则采用CAS + synchronized。  
下面的过程就体现了synchronized的作用，以数组上的每个索引，也就是头结点/根节点为一把锁，实现互斥访问。  
![在这里插入图片描述][02dfe0cce51c4555b8340b4f647fa6e7.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]

else {
        
        V oldVal = null;
        synchronized (f) {
         //f是数组上的索引，加锁确保线程安全
            if (tabAt(tab, i) == f) {
         //如果i位置是索引也就是头结点
                /*
                * 第一段：如果是链表，就遍历链表，找合适位置放元素
                * */
                if (fh >= 0) {
         //fh是索引位置元素的hash值，大于等于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;
                        }
                    }
                }
                /*
                * 第二段：如果是树节点，就按照putTreeVal方式放元素
                * */
                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;
        }
    }

这段主要是synchronized用法，其他代码和HashMap1.8的底层原理类似

### 4、第四步：并发扩容 ###

**问题：当有线程在进行扩容操作的时候，其他线程如果put元素，不清楚是否会往老数组中放元素还是新数组中放元素**

**解决：在扩容的时候，暂不允许put元素，空闲线程则去帮忙扩容**

在putval源码中这段代码就是解决方法

else if ((fh = f.hash) == MOVED)
    	tab = helpTransfer(tab, f);

在扩容的时候会把头节点的hash置为MOVED(-1)，当线程运行到这段代码的时候，就知道正在扩容，于是会帮忙扩容转移元素 - - - - helpTransfer()

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        
        Node<K,V>[] nextTab; int sc;
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
        
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
        
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }

具体实现transfer

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        
        int n = tab.length, stride;
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        if (nextTab == null) {
                    // initiating
            try {
        
                @SuppressWarnings("unchecked")
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {
              // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab;
            transferIndex = n;
        }
        int nextn = nextTab.length;
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        boolean advance = true;
        boolean finishing = false; // to ensure sweep before committing nextTab
        for (int i = 0, bound = 0;;) {
        
            Node<K,V> f; int fh;
            while (advance) {
        
                int nextIndex, nextBound;
                if (--i >= bound || finishing)
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) {
        
                    i = -1;
                    advance = false;
                }
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
        
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            if (i < 0 || i >= n || i + n >= nextn) {
        
                int sc;
                if (finishing) {
        
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
        
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            else {
        
                synchronized (f) {
        
                    if (tabAt(tab, i) == f) {
        
                        Node<K,V> ln, hn;
                        if (fh >= 0) {
        
                            int runBit = fh & n;
                            Node<K,V> lastRun = f;
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
        
                                int b = p.hash & n;
                                if (b != runBit) {
        
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            if (runBit == 0) {
        
                                ln = lastRun;
                                hn = null;
                            }
                            else {
        
                                hn = lastRun;
                                ln = null;
                            }
                            for (Node<K,V> p = f; p != lastRun; p = p.next) {
        
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                if ((ph & n) == 0)
                                    ln = new Node<K,V>(ph, pk, pv, ln);
                                else
                                    hn = new Node<K,V>(ph, pk, pv, hn);
                            }
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                        else if (f instanceof TreeBin) {
        
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> lo = null, loTail = null;
                            TreeNode<K,V> hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
        
                                int h = e.hash;
                                TreeNode<K,V> p = new TreeNode<K,V>
                                    (h, e.key, e.val, null, null);
                                if ((h & n) == 0) {
        
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else {
        
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin<K,V>(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin<K,V>(hi) : t;
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }

## 三、ConcurrentHashMap常见面试题 ##

### 1、ConcurrentHashMap使用什么技术来保证线程安全？ ###

jdk1.7：Segment+HashEntry来进行实现的；

jdk1.8：放弃了Segment臃肿的设计，采用Node+CAS+Synchronized来保证线程安全；

### 2、HashMap 和 ConcurrentHashMap 的区别 ###

1.  ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。）
2.  HashMap的键值对允许有null，但是ConCurrentHashMap都不允许

### 3、ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？ ###

**JDK1.7**

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式进行实现，结构如下：

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

![在这里插入图片描述][79a096e1ed1e427782619ba95e7ea203.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]

1.  该类包含两个静态内部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角色；
2.  Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个HashEntry 数组里得元素，当对HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁。

**JDK1.8**

在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

结构如下：  
![在这里插入图片描述][5135f0148fcc443aadcf7ad5aa678949.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]

### 4、ConcurrentHashMap默认初始容量是多少？ ###

从下面ConcurrentHashMap类的静态变量可以看出它的初始容量为16

### 5、ConCurrentHashmap 的key，value是否可以为null？为什么？ ###

不行 如果key或者value为null会抛出空指针异常

ConrrentHashMap 是一个用于多线程并发场景下的并发容器(Map),也就是在多线程环境下执行增删改查方法要保证线程安全性,

为什么不能为null？这里涉及到二义性问题，所以当我们用get方法获取到一个value为null的时候，这里会产生二义性：

*  可能没有这个key
 *  可能有这个key，只不过value为null

**HashMap如何解决二义性问题**

containsKey方法的结果一个为false一个为true，可以通过这个方法来区分上面说道的二义性问题

> public boolean containsKey(Object key) \{  
> return getNode(hash(key), key) != null;  
> \}

*  如果存在key为null的元素（key=null对应的hash值=0），getNode获取到值不为null；
 *  如果不存在key为null的元素，此时hash值=0对应的下标元素为null，即getNode获取到的值为null；

**ConcurrentHashMap为什么不能解决二义性问题**

因为ConcurrentHashMap是一个用在多线程并发的Map容器，不能put null是因为无法分辨是key没找到的null，还是有key值为null。这在多线程里面是没发保证会不会有其他线程修改为null键和null值的情况，所以不让put null。

### 6、ConCurrentHashmap 每次扩容是原来容量的几倍 ###

2倍 在transfer方法里面会创建一个原数组的俩倍的node数组来存放原数据

### 7、ConCurrentHashmap的数据结构是怎么样的？ ###

在java1.8中，它是一个数组+链表+红黑树的数据结构。

### 8、ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？ ###

弱一致性，HashMap强一致性。

ConcurrentHashMap可以支持在迭代过程中，向map添加新元素，而HashMap则抛出了ConcurrentModificationException，因为HashMap包含一个修改计数器，当你调用他的next()方法来获取下一个元素时，迭代器将会用到这个计数器。

> ConcurrentHashMap面试题参考链接  
> [https://blog.csdn.net/QGhurt/article/details/107323702][https_blog.csdn.net_QGhurt_article_details_107323702]  
> [https://blog.csdn.net/xt199711/article/details/114339022][https_blog.csdn.net_xt199711_article_details_114339022]  
> [https://blog.csdn.net/afreon/article/details/120397899][https_blog.csdn.net_afreon_article_details_120397899]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7f28a869a9e944ec837f2283b079c341.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[8165868016b349c49fdbbe89790c7433.png]: https://img-blog.csdnimg.cn/8165868016b349c49fdbbe89790c7433.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/6186bd2d83bc482eb890eac0b2b39397.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[02dfe0cce51c4555b8340b4f647fa6e7.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/02dfe0cce51c4555b8340b4f647fa6e7.png?type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[79a096e1ed1e427782619ba95e7ea203.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/79a096e1ed1e427782619ba95e7ea203.png?type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[5135f0148fcc443aadcf7ad5aa678949.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/5135f0148fcc443aadcf7ad5aa678949.png?type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[https_blog.csdn.net_QGhurt_article_details_107323702]: https://blog.csdn.net/QGhurt/article/details/107323702
[https_blog.csdn.net_xt199711_article_details_114339022]: https://blog.csdn.net/xt199711/article/details/114339022
[https_blog.csdn.net_afreon_article_details_120397899]: https://blog.csdn.net/afreon/article/details/120397899