Java进阶（ConcurrentHashMap）——面试时ConcurrentHashMap常见问题解读 & 结合源码分析 & 多线程CAS比较并交换 初识

在这里插入图片描述

前言

List、Set、HashMap作为Java中常用的集合，需要深入认识其原理和特性。

本篇博客介绍常见的关于Java中线程安全的ConcurrentHashMap集合的面试问题，结合源码分析题目背后的知识点。

关于List的博客文章如下：

关于的Set的博客文章如下：

关于HaseMap的博客文章如下：

其他关于 数据结构 以及 多线程 的文章如下：

在这里插入图片描述

目录

引出

1.从结构上来说jdk7中，ConcurentHashMap是采用Segment段数组 + Entry数组 + 单链表结构；
2.从结构上来说jdk8中，ConcurentHashMap 与 HashMap的结构是一模一样的；
3.ConcurrentHashMap 不支持 key 或者 value 为 null ，避免歧义；
4.JDK1.7和1.8的区别：

  1. 数据结构：取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
  2. 保证线程安全机制：JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+sizeCtl+synchronized保证线程安全。
  3. 锁的粒度：JDK1.7 是对需要进行数据操作的 Segment 加锁，JDK1.8 调整为对每个数组元素加锁（Node）。
  4. 链表转化为红黑树：定位节点的 hash 算法简化会带来弊端，hash 冲突加剧，因此在链表节点数量到达 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储。
  5. 查询时间复杂度：从 JDK1.7的遍历链表O(n)， JDK1.8 变成遍历红黑树O(logN)。

5.CAS是一种乐观锁机制，也被称为无锁机制

核心：线程安全

ConcurentHashMap 在JDK1.7 和JDK1.8的区别？ConcurentHashMap 是怎么保证线程安全的？

  1. 从结构上来说jdk7中，ConcurentHashMap是采用Segment段数组 + Entry数组 + 单链表结构

分段，每个段里面都是hashmap，本质还是以hashmap为单位上锁

在这里插入图片描述

  1. 从结构上来说jdk8中，ConcurentHashMap 与 HashMap的结构是一模一样的

  2. 从线程安全来说，jdk7中，ConcurentHashMap 内部维护的是一个Segment(段)数组，Segment数组中每个元素又是一个HashEntry数组

    在这里插入图片描述

    Segment继承了ReentrantLock这个类，所以segment自然就可以扮演锁的角色，每一个segment相当于一把锁，这就是分段锁

    当其他线程在需要进行put操作时，需要先去获取该对象的锁资源，然而当发现锁资源被占用的时候，该线程会先去进行节点的创建避免线程的空闲，这种思想也叫作预创建的思想

    因为segment在初始化后是不会扩容的，HashEntry数组是会扩容的，与HashMap机制一样，所以HashEntry是依靠于segment锁来维护安全，所以HashEntry的扩容也是线程安全的

1.什么时候初始化

jdk8中，ConcurentHashMap 因为结构变为了 数组+链表+红黑树 结构，所以维护线程安全的机制页相对发生了一些变化，和HashMap同样的，ConcurentHashMap 在put第一个元素时，才会执行初始化

在这里插入图片描述

final V putVal(K key, V value, boolean onlyIfAbsent) {
     if (key == null || value == null) throw new NullPointerException();
     int hash = spread(key.hashCode()); //根据KEY计算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)
             tab = initTable(); //如果数组为null时，表示第一次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
         }
         ...

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

2.如何保证初始化安全 sizeCtl

在这里插入图片描述

此处核心为sizeCtl

  • sizeCtl的不同值表示不同的含义
  • sizeCtl = 0 代表数组还未初始化
  • sizeCtl > 0 如果数组已经初始化，那么表示 扩容阈值
  • sizeCtl = -1 表示数组正在初始化
  • sizeCtl < -1 表示数组正在扩容，并且正在被多线程初始化中

sizeCtl 这个值，就保证了多线程并发状态下，数组的初始化安全

在这里插入图片描述

核心为compareAndSwapInt，比较主存中数据和当前内存中数据是否相同，如果不同代表有别的线程正在操作这个数据那么就返回false，退回重新争取时间片，此处就是保证并发时线程安全的核心。

在这里插入图片描述

private final Node<K,V>[] initTable() {
     Node<K,V>[] tab; int sc;
 //循环判断数组是否为空/null
     while ((tab = table) == null || tab.length == 0) {
         //此处核心为sizeCtl
         /*
             sizeCtl的不同值表示不同的含义
             sizeCtl = 0 代表数组还未初始化
             sizeCtl > 0 如果数组已经初始化，那么表示 扩容阈值
             sizeCtl = -1 表示数组正在初始化
             sizeCtl < -1 表示数组正在扩容，并且正在被多线程初始化中
         */
         if ((sc = sizeCtl) < 0) //此处表示数组正在被某个线程初始化
             Thread.yield(); // lost initialization race; just spin //释放CPU时间片
         //核心为compareAndSwapInt，比较主存中数据和当前内存中数据是否相同，如果不同代表有别的线程正在操作这个数据那么就返回false，退回重新争取
         //时间片
         //此处就是保证并发时线程安全的核心
         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { 
             try {
                 if ((tab = table) == null || tab.length == 0) {
                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY; //得到了数组长度是否为自己设置还是默认16
                     @SuppressWarnings("unchecked")
                     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; //new出数组
                     table = tab = nt;//数组赋值
                     sc = n - (n >>> 2);
                 }
             } finally {
                 sizeCtl = sc;  
             }
             break;
         }
     }
     return tab;
 }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

CAS + sizeCtl 保证了初始化数据的安全

3.putval方法存入元素，加锁

数组的初始完成后，回到putval方法存入元素

在这里插入图片描述

真正存入元素时，是加入了synchronized来加锁保证线程安全

CAS + sizeCtl 和 synchronized 两者共同保证了ConcurentHashMap 的线程安全！

ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？

  1. 假设 ConcurrentHashMap 允许存放值为 null 的 value，这时有A、B两个线程，线程A调用ConcurrentHashMap.get(key)方法，返回为 null ，我们不知道这个 null 是没有映射的 null ，还是存的值就是 null 。
  2. 假设此时，返回为 null 的真实情况是没有找到对应的 key。那么，我们可以用 ConcurrentHashMap.containsKey(key)来验证我们的假设是否成立，我们期望的结果是返回 false 。
  3. 但是在我们调用 ConcurrentHashMap.get(key)方法之后，containsKey方法之前，线程B执行了ConcurrentHashMap.put(key, null)的操作。那么我们调用containsKey方法返回的就是 true 了，这就与我们的假设的真实情况不符合了，这就有了二义性。

JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别？

  1. 数据结构：取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
  2. 保证线程安全机制：JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+sizeCtl+synchronized保证线程安全。
  3. 锁的粒度：JDK1.7 是对需要进行数据操作的 Segment 加锁，JDK1.8 调整为对每个数组元素加锁（Node）。
  4. 链表转化为红黑树：定位节点的 hash 算法简化会带来弊端，hash 冲突加剧，因此在链表节点数量到达 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储。
  5. 查询时间复杂度：从 JDK1.7的遍历链表O(n)， JDK1.8 变成遍历红黑树O(logN)。

涉及到的多线程知识

CAS是啥？

CAS(CompareAnd Swap)，就是比较并交换，是解决多线程情况下，解决使用锁造成性能损耗问题的一种机制。

CAS是一种乐观锁机制，也被称为无锁机制。全称: Compare-And-Swap。它是并发编程中的一种原子操作，通常用于多线程环境下实现同步和线程安全。CAS操作通过比较内存中的值与期望值是否相等来确定是否执行交换操作。如果相等，则执行交换操作，否则不执行。由于CAS是一种无锁机制，因此它避免了使用传统锁所带来的性能开销和死锁问题，提高了程序的并发性能。

CAS包含三个操作数：

  • 变量内存位置(V)
  • 预期的变量原值(A)
  • 变量的新值(B)

当要对变量进行修改时，先会将内存位置的值与预期的变量原值进行比较，如果一致则将内存位置更新为新值，否则不做操作，无论哪种情况都会返回内存位置当前的值。

比较并交换是啥？

在这里插入图片描述

package com.tianju.test2;

import java.util.concurrent.atomic.AtomicInteger;

public class CASTest {
    public static void main(String[] args) {
        AtomicInteger atomicInteger = new AtomicInteger(5);
        System.out.println(atomicInteger.compareAndSet(5,2019));
        System.out.println(atomicInteger);
        System.out.println(atomicInteger.compareAndSet(5,2020));
        System.out.println(atomicInteger.compareAndSet(2019,2020));
        System.out.println(atomicInteger);
        System.out.println(atomicInteger.compareAndSet(2020,5));
        System.out.println(atomicInteger);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

CAS的优缺点

优点：

CAS是一种无锁机制，因此它避免了使用传统锁所带来的性能开销和死锁问题，提高了程序的并发性能。

缺点：

CAS 有自旋锁，如果不成功会一直循环，可能会给 cpu 带来很大开销；

问题就是可能会造成 “ABA”；

解决方案：解决的思路就是引入类似乐观锁的版本号控制，不止比较预期值和内存位置的值，还要比较版本号是否正确。

在这里插入图片描述

AtomicStampedReference atomicStampedReference = new AtomicStampedReference(5, 1);

  • 1

在这里插入图片描述

package com.tianju.test2;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicStampedReference;

public class CASTest {
    public static void main(String[] args) {
        AtomicInteger atomicInteger = new AtomicInteger(5);
        System.out.println(atomicInteger.compareAndSet(5,2019));
        System.out.println(atomicInteger);
        System.out.println(atomicInteger.compareAndSet(5,2020));
        System.out.println(atomicInteger.compareAndSet(2019,2020));
        System.out.println(atomicInteger);
        System.out.println(atomicInteger.compareAndSet(2020,5));
        System.out.println(atomicInteger);

        System.out.println(" ########################################## ");
        AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(5, 1);

        boolean flag1 = atomicStampedReference.compareAndSet(atomicStampedReference.getReference(), 2019,
                atomicStampedReference.getStamp(), 2);
        System.out.println("从5修改为2019："+flag1);
        System.out.println(atomicStampedReference.getReference());

        boolean flag2 = atomicStampedReference.compareAndSet(atomicStampedReference.getReference(), 2020,
                atomicStampedReference.getStamp(), 3);
        System.out.println("从2019修改为2020："+flag2);
        System.out.println(atomicStampedReference.getReference());

        boolean flag3 = atomicStampedReference.compareAndSet(2020, 5, 3, 4);
        System.out.println("从2020修改回5："+flag3);
        System.out.println(atomicStampedReference.getReference());


    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

什么是CAS机制compareAndSwapInt

CAS是Java中Unsafe类里面的方法，它的全称是CompareAndSwap，比较并交换的意思。它的主要功能是能够保证在多线程环境下，对于共享变量的修改的原子性。

如下，成员变量state，默认值是0，定义了一个方法doSomething()，这个方法的逻辑是判断state是否为0，如果为0就修改成1。这个逻辑看起来没有任何问题，但是在多线程环境下，会存在原子性的问题，因为这里是一个典型的，Read-Write的操作。

一般情况下，我们会在doSomething()这个方法上加同步锁来解决原子性问题。

在这里插入图片描述

package com.tianju.test2;

public class Demo1 {
    private int state = 0;
    public void doSomething(){
        if (state==0){
            state=1;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

但是，加同步锁，会带来性能上的损耗，所以，对于这类场景，我们就可以使用CAS机制来进行优化

在这里插入图片描述

package com.tianju.test2;


import sun.misc.Unsafe;

public class Demo2 {
    private volatile int state = 0;
    private static final Unsafe UNSAFE = Unsafe.getUnsafe();
    private static final long stateOffset;

    static {
        try {
            stateOffset = UNSAFE.objectFieldOffset(
                    Demo2.class.getDeclaredField("state")
            );
        } catch (NoSuchFieldException e) {
            throw new RuntimeException(e);
        }
    }

    public void doSomething(){
        if (UNSAFE.compareAndSwapInt(this,stateOffset,0,1)){
            state=1;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

在doSomething()方法中，我们调用了unsafe类中的compareAndSwapInt()方法来达到同样的目的，这个方法有四个参数，分别是：
当前对象实例、成员变量state在内存地址中的偏移量、预期值0、期望更改之后的值1。

CAS机制会比较state内存地址偏移量对应的值和传入的预期值0是否相等，如果相等，就直接修改内存地址中state的值为1。否则，返回false，表示修改失败，而这个过程是原子的，不会存在线程安全问题。

CompareAndSwap是一个native方法，实际上它最终还是会面临同样的问题，就是先从内存地址中读取state的值，然后去比较，最后再修改。

这个过程不管是在什么层面上实现，都会存在原子性问题。所以，CompareAndSwap的底层实现中，在多核CPU环境下，会增加一个Lock指令对缓存或者总线加锁，从而保证比较并替换这两个指令的原子性。

CAS主要用在并发场景中，比较典型的使用场景有两个：

  1. 第一个是J.U.C里面Atomic的原子实现，比如AtomicInteger，AtomicLong。
  2. 第二个是实现多线程对共享资源竞争的互斥性质，比如在AQS、ConcurrentHashMap、ConcurrentLinkedQueue等都有用到。

总结

1.从结构上来说jdk7中，ConcurentHashMap是采用Segment段数组 + Entry数组 + 单链表结构；
2.从结构上来说jdk8中，ConcurentHashMap 与 HashMap的结构是一模一样的；
3.ConcurrentHashMap 不支持 key 或者 value 为 null ，避免歧义；
4.JDK1.7和1.8的区别：

  1. 数据结构：取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
  2. 保证线程安全机制：JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+sizeCtl+synchronized保证线程安全。
  3. 锁的粒度：JDK1.7 是对需要进行数据操作的 Segment 加锁，JDK1.8 调整为对每个数组元素加锁（Node）。
  4. 链表转化为红黑树：定位节点的 hash 算法简化会带来弊端，hash 冲突加剧，因此在链表节点数量到达 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储。
  5. 查询时间复杂度：从 JDK1.7的遍历链表O(n)， JDK1.8 变成遍历红黑树O(logN)。

5.CAS是一种乐观锁机制，也被称为无锁机制

id="article_content" class="article_content clearfix"> id="content_views" class="markdown_views prism-atom-one-light">

摘要

Yolo（You Only Look Once）作为一种高效的目标检测算法，自2015年首次提出以来，经历了多个版本的迭代与改进。以下是对Yolo改进方向、方法及未来发展趋势的总结。
在这里插入图片描述

改进方向

  1. 模型架构优化：

    • 近年来，Yolo的改进主要集中在模型的backbone、neck和head等关键模块上。研究者们通过引入新的网络结构和优化算法，提升模型的性能[3][29]。

  2. 注意力机制的引入：

    • 注意力机制被广泛应用于Yolo的改进中，帮助模型更好地关注图像中的重要部分，从而提高检测的准确性[3][8][29]。

  3. 多尺度特征融合：

    • 为了提升对小目标的检测能力，Yolo的后续版本引入了多尺度特征融合技术，使得模型在处理复杂场景时表现更佳[2][4]。

  4. 数据集的多样化：

    • 使用私有数据集和垂直领域数据集进行训练，能够提高模型在特定应用场景下的表现。这种方法使得Yolo在不同领域的应用更加广泛和有效[3][29]。

  5. 轻量化设计：

    • 随着移动设备和嵌入式系统的普及，Yolo的轻量化设计成为一个重要的研究方向，旨在在保证精度的同时减少计算资源的消耗[1][5]。

改进方法

  • 引入新技术：

    • 采用Transformer模型等新技术，增强Yolo对图像中复杂场景的理解能力，提升模型的泛化能力[3][29]。

  • 优化损失函数：

    • 通过改进损失函数设计，提升模型在训练过程中的收敛速度和准确性[3][29]。

  • 数据增强技术：

    • 采用多种数据增强方法，如随机裁剪、旋转和缩放，增加训练数据的多样性，从而提高模型的鲁棒性和泛化能力[58][60]。

未来发展趋势

  1. 小目标检测的精度提升：

    • 未来的Yolo版本将更加注重提升小目标检测的精度，尤其是在密集排列物体的场景中[2][4]。

  2. 实时性与准确性的平衡：

    • 在保持实时检测能力的同时，进一步提高检测准确性，将是Yolo发展的重要方向[4][5]。

  3. 跨域自适应与多任务学习：

    • 未来的研究可能会集中在跨域自适应和多任务学习上，以增强Yolo在不同应用场景中的适应能力和性能[39][38]。

  4. 集成学习与迁移学习：

    • 集成学习和迁移学习将成为Yolo改进的重要方向，通过结合多个模型的预测结果来提高检测的准确性和鲁棒性[24][29]。

总结

Yolo的改进与发展不仅体现在技术的迭代上，更在于其在实际应用中的广泛适应性和不断优化的能力。随着深度学习技术的进步，Yolo将继续在目标检测领域发挥重要作用，Yolo依然是广大学生和从业者的首选。

>>
id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"> class="blog_extension blog_extension_type5" id="blog_extension"> class="extension_official" data-report-click="{"spm":"1001.2101.3001.6471"}"> class="blog_extension_card_left">
class="blog_extension_card_cont"> 订阅专栏后扫码加群 class="blog_extension_card_cont_r"> QQ群名片
注：本文转载自blog.csdn.net的Perley620的文章"https://blog.csdn.net/Pireley/article/details/134122251"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！