一文说透ConcurrentHashMap及大厂面试题

本期说一下ConcurretHashmap及相关知识点的面试题及答案。

jdk1.7中和jdk1.8中ConcurretHashMap的区别？

jdk1.7中：

alt

分段锁：JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，不同段之间可以并发访问。锁粒度：基于 Segment，包含多个 HashEntry。相当于一个锁管多条链表。
HashEntry数组：每个段内部是一个 HashEntry 数组，数组中每个元素都是一个链表，用于解决哈希冲突。

jdk1.8中：

alt

CAS（无锁算法）+synchronized+Node+红黑树：引入了 CAS（Compare and Swap）操作，使用了 synchronized 关键字，节点结构变为 Node，并引入了红黑树（当链表长度达到一定阈值时，链表会转换为红黑树，提高查询效率）。锁粒度：Node，粒度降低了，相当于一个锁管一条链表。
Node替代HashEntry
引入了红黑树

更新元素时，先回去synchronized锁定的node，然后便利链表或红黑树，找到需要修改的key，使用CAS判断值是否等于预期值，若等于，说明在此期间没被其他线程修改过，则更新，否则不更新或重试。（CAS操作一气呵成，不会被打断，是原子操作）

注：

ConcurrentHashMap的并发度是指：程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16，且可以在构造函数中设置。当用户设置并发度时，ConcurrentHashMap 会使用大于等于该值的最小2幂指数作为实际并发度（假如用户设置并发度为17，实际并发度则为32）。

对红黑树的理解

alt

红黑树是一个自平衡的二叉查找树（BST）。

性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL,java中为null）是黑色。
性质4：每个红节点的两个子节点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。红黑树中，平衡的概念是通过性质4（红节点不相邻）和性质5（黑平衡）来定义的，保证了红黑树的高度相对较小。

对CAS怎么理解？

CAS（Compare and Swap，比较与交换）是一种多线程同步的原子操作，用于实现多线程环境下的并发算法。

执行过程为：

读取内存位置的当前值。
检查读取的值是否等于预期值。
- 如果等于，则说明内存位置的值没有被其他线程修改，可以执行更新操作。
- 如果不等于，说明其他线程已经修改了内存位置的值，操作失败，需要重新尝试或采取其他策略。
- 如果相等，则使用新值更新内存位置的值。
以上操作一气呵成，不会被其他线程打断，因此CAS是原子性的。

CAS 的优势在于它是一种非阻塞算法，不需要使用锁，避免了锁的开销和可能引起的死锁问题。它是一种乐观锁的实现，通过不加锁的方式进行并发控制。

CAS实现类有：AtomicInteger（提供了一个整数变量的原子操作类）、AtomicLong（提供了长整型变量的原子操作）

**注：**原子操作是指执行过程不被其他线程干扰，要么执行成功要么执行不执行，不存早执行过程被中断的情况。

乐观锁和悲观锁？

乐观锁：

乐观锁是一种并发控制机制，它的基本思想是假设并发冲突的概率较低，因此在绝大多数情况下不会发生冲突。因此，乐观锁不会在访问共享资源之前加锁，而是在更新操作时检查在此期间是否有其他线程对数据进行了修改。

实现方式

方式一：CAS。但存在ABA问题
- 所谓ABA问题，即一个线程将内存值从A改为B，另一个线程又从B改回到A。
方式二：版本号机制。

在数据结构中增加一个版本号字段，每次更新时递增版本号。在比较并更新时，不仅要比较值是否相等，还需要比较版本号是否一致。这种方式能够避免 CAS 中的 ABA 问题。
- JUC中对应版本号机制的类为原子包中的AtomicStampedReference类。
方式三：使用时间戳。

每个事务或线程在进行更新时附带一个时间戳，当更新时检查时间戳是否一致，从而确定是否发生冲突。这种方式可以解决 ABA 问题，并提供更精确的冲突检测。

以上内容出自本人整理的面试秘籍。链接: https://pan.baidu.com/s/1o014Ems8diV0D3h8K15olA?pwd=fi3x 提取码: fi3x 复制这段内容后打开百度网盘手机App，操作更方便哦