导图社区 Java 基础

Java 基础

Java 大厂面试必备，涵盖 HashMap、ConcurrentHashMap、AQS、可重入锁、信号量、计数器、线程池、NIO、AIO、poll、epoll 等重要知识点，如果需要 JVM 相关知识，请持续关注

提示: 本内容由社区用户上传并分享。平台不对内容的真实性、合法性、知识产权归属及是否侵害第三方权利进行事前审核或保证。本内容可能包含受版权保护的图片、字体或其他第三方素材，使用前请自行确认授权范围。

编辑于2022-04-01 19:58:15

大厂面试

ED4wj1Vf

他的近期作品查看更多>>

Java 基础

社区模板帮助中心，点此进入>>

ED4wj1Vf

他的近期作品查看更多>>

相似推荐
大纲

计算机操作系统思维导图
- 9.9k
- 362
- 213
- 14
- 0
journey
简单介绍MYSQL数据库软件的基本命令
- 1.2k
- 0
- 96
- 15
- 0
壞灬
计算机基础知识
- 2.9k
- 183
- 215
- 26
- 0
莫挽????
.net学习总结
- 654
- 0
- 41
- 12
- 0
长方体混凝土瞬移工程师
python基础知识点简单总结
- 5.2k
- 103
- 66
- 9
- 0
排列&组合
序列类型的方法
- 1.6k
- 13
- 19
- 1
- 0
排列&组合
管理信息系统
- 1.9k
- 109
- 84
- 12
- 0
欲戴王冠必承其重????????
Python3.0入门知识思维导图
- 1.5k
- 6
- 173
- 11
- 0
颜老师的作品
java 从入门到精通(第四版本)
- 735
- 27
- 78
- 10
- 0
吕远征
软考架构设计师
- 1.2k
- 8
- 40
- 0
- 0
轻风

Java 基础

集合

HashMap

初始化逻辑

传入初始大小，HashMap 将选择最近的 2 的幂作为哈希表的大小

传入扩容因子，当元素个数等于扩容因子乘哈希表大小时扩容

太大了难以扩容，冲突概率增大

太小了扩容频繁，性能和空间利用率低

默认为 0.75

0.693 是最佳的

插入时逻辑

哈希值 h = key.hash ^ (h >>> 16)

让哈希值的高 16 位参与进来，减少冲突概率

下标 i = h & (n - 1)

位运算，等同于取模

如果 n 不是 2 的幂，n - 1 低位不会全 1，h 位利用率不高，冲突概率大

树化

哈希冲突严重时，查找和插入(尾插法)时效率沦为线性

红黑树中隐藏了一个双向链表，利于扩容时使用

树化条件

链表元素大于等于 8

哈希表大小大于等于 64

扩容也能有效避免哈希冲突

红黑树

概念

从一个节点到任意一个叶子节点不同路径上的黑色节点数目都是一样的

根节点一定是黑色的

红节点的孩子必须是黑色的（不存在亲子关系的红节点）

插入

首先定位到待插入的节点，然后向上递归调整，插入节点默认为红色

父节点为空

树空，直接作为根节点插入，将自己染黑

父节点黑色

直接插入

父节点红色

叔叔节点为空

旋转，父节点和祖父节点变色

叔叔节点黑色

旋转，父节点和祖父节点变色

叔叔节点红色

祖父节点、父亲和叔叔均颜色反转

从祖父节点开始继续循环检查

扩容时逻辑

有意思的结论：hash[i] 中的元素扩容后只会存在与 newHash[i] 或 newHash[i + n] 中

对于 hash[i] 中的元素，维护 low 和 hi 两个链表，分别接入 newHash[i] 和 newHash[i + n] 中，树中也有一个链表，因此遍历非常高效

jdk1.7 时没有维护 low 和 hi，而是在线使用头插法扩容，多线程下存在死环问题

如果是树并且 low 或 hi 链表元素小于等于 6，红黑树会退化为链表

删除时逻辑

根据链表或红黑树执行不同的逻辑

红黑树退化时会执行特殊的判断，当红黑树过小时则退化

并不是直接比较数目

最小可以是 4 个，最多可以是 6 个

ConcurrentHashMap

初始化逻辑

当有线程正在初始化时，调用 Thread.yield() 让出时间片

一旦初始化成功，sizeCtl 被设置为 0.75 × N，扩容因子固定为 0.75

插入时逻辑

jdk1.7 将哈希表分段，对对于分段上锁

jdk1.8 后对要操作的下标 hash[i]上锁

更细粒度的锁，只有哈希冲突的元素会发生竞争

红黑树的根会变动，因此使用 Treebin 封装红黑树的根

使用 synchronized 锁住 hash[i]

大小改变

直接 size++ 或 size-- 是不安全的

利用原子类底层还是利用 CAS，高并发下自旋效率差

如果更新大小字段失败，则更新 CounterCell 数组值

将需要竞争的资源分散开来，以减小冲突，需要时再重新聚合起来

统计大小时遍历 CounterCell 数组

CounterCell 元素选择也是通过哈希映射的

CounterCell 数组大小最大不超过 CPU 核心

扩容时逻辑

有意思的结论：hash[i] 中的元素扩容后只会存在与 newHash[i] 或 newHash[i + n] 中

允许多个线程一起参与扩容

每个线程选定一个下标 transforIndex，对 hash[index] 的的元素进行扩容，不同下标之间不会发生竞争

transforIndex 指示线程开始的下标(逆序)，线程选取 stride 个元素作为自己的任务，并将 transforIndex 用 CAS 减 stride

步长 stride 最低为 16，根据数组大小计算出来

每一轮扩容都有一个标识符

sc 的高 16 位，并且此时 sc 一定是负的

初始时 sc 设置为标识符 + 2，每个帮忙线程都会自增 sc

sc 的低 16 位减 1 为正在扩容线程数

sizeCtl

未初始化

-1

正在初始化，等待的线程需降低 CPU 执行优先级

sc < 0 && sc != -1

正在执行扩容

前 16 位为扩容标识戳，后 16 位为执行的线程数加一

sc > 0

扩容阈值

多线程

Synchronized

对象头 MarkWorld 32/64bit

锁标志位 01 && 可偏向位 0：无锁

对象 Hash、分代年龄、是否可偏向、锁标志位

锁标志位 01 && 可偏向位 1：偏向锁

线程 ID、Epoch、分代年龄、是否可偏向、锁标志位

锁标志位 00：轻量级锁

指向线程栈帧中锁记录的指针、锁标志位

锁标志位 10：重量级锁

指向重量级锁的指针、锁标记位

锁标志位 11：GC 标记

偏向锁

偏向某一个线程，案例： StringBuffer 在同一个线程中执行方法却不停的加锁

开启偏向锁后，new 出的对象处于匿名偏向状态；当真正发生竞争时，会进入轻量级锁，一旦可偏向位为 0，将禁止重偏向发生

当对象已经计算 Hash 后，不会进入偏向状态；当对象正在偏向状态却收到计算 Hash 指令时，会进入轻量级锁；偏向锁只会偏向线程一次，当发生重偏向或升级后，要么禁止重偏向（升级）、要么禁止该线程偏向（重偏向）。

锁升级时，会比对 Epoch 查看当前线程是否持有偏向锁，是的话将扫描线程栈帧(必须是安全点)，CAS 将锁记录修改为轻量级锁；如果未持有，则按照常规方式竞争

重偏向

多线程串行执行

线程如何判断是否真的串行？

退出同步语句块后，锁标志位、线程 ID 和可偏向位并没有改变

Epoch 时间戳

线程获取到偏向锁后，Class 中的 Epoch 会自增，并且会更新对象的 Epoch

线程退出同步语句块后，Class 中的 Epoch 会自增，但不会更新对象

只需要比较 Class 中的 Epoch 和对象的 Epoch 是否相等就可以知道偏向锁是否正在被持有

重偏向是默认关闭的，只有触发阈值（批量重偏向）时才会开启重偏向

批量重偏向和重偏向之间的关系

批量重偏向

Class 文件中存在一个计数器，每一次关联的对象进行偏向锁获取或撤销时都会自增该计数器

当计数器达到阈值(20)后，重偏向被打开，对象可以重新偏向线程

当计数器达到阈值(40)后，JVM 认为该类可能存在并发问题，会禁止此类的偏向锁

jdk 15 后弃用

轻量级锁已经非常高效了，轻量级锁也是可重入的

轻量级锁

设计思想：先自旋等待一会，不行在陷入休眠

检查轻量级锁是否被占有，若未被占有则线程复制一份 MarkWorld 到线程栈帧中，用 CAS 修改 MarkWorld 为指向锁记录的指针

被占有则检查指针是否指向当前栈帧(可重入的)

成功则占有锁

失败则自旋重试

利用 CAS 将锁记录复制回去

成功则是否成功，修改为无锁状态

失败，则一定是膨胀为重量级锁，需要唤醒逻辑

锁膨胀

自旋次数超过阈值(10次)

等待的线程不止一个

收到重新计算哈希的请求

重量级锁

ObjectMonitor 对象

markOop：锁对象的 MarkWorld

owner：指向占有者线程

可重入的

count：计数器

EntryList：处于等待获取锁的线程

线程被封装成 ObjectWaiter

底层是操作系统互斥量实现的

陷入系统调用，性能查

自旋一段时间后未获得锁，将陷入休眠等待唤醒休眠时根据具体策略可能会移动到 cxq 队列

monitorexit 指令会唤醒相关线程，默认策略下会唤醒 cxq 队列

WaitSet：陷入休眠的线程

wait() 方法

必须修改 owner 为 null 释放监视器

调用 wait 时不允许持有锁

等待唤醒，被唤醒的线程将移动至 EntryList 或 cxq 队列

monitorenter - monitorexit 字节码

cxq 队列

根据具体的策略作为等待被唤醒的线程的中间队列

AQS

同步阻塞队列，一个抽象的可以实现阻塞线程、排队控制、唤醒线程等操作的同步器基础框架类

AQS 必须要保证整个队列入队和出队操作的原子性，同时要保证入队的线程在休眠后必须能够被唤醒

独占模式

如果第一次尝试获取失败，则入队进入 acquireQueued 方法

在 while 中不停获取锁，获取失败时则休眠

获取锁成功则将自己设置为头节点

队头不允许休眠，必须不断自旋

队头 ws = singal，释放锁时必须唤醒后继节点

休眠时必须保证前驱节点正常

修改前驱节点 ws = singal，保证自己会被唤醒

如果前驱节点被取消，则重新链接到正常的节点

共享模式

最后一个获取到锁的节点作为 head

头节点的 ws = singal

如果还有资源可用或者 ws <0 时 ws= PROPAGATE(-3) 或 ws == SINGAL(-1) 时，必须唤醒后继节点

tryAcquireShared

1 表示获取成功而且还有资源可用

必须唤醒头节点的后继节点

0 表示获取成功但没有资源可用

-1 表示获取失败

释放锁时如果头节点 ws == singal，则必须唤醒头节点的后继节点

头节点 ws = singal，那么唤醒后继节点，然后设置 ws = 0

后继节点如果获取锁，会成为新头

如果没获取锁，会修改前驱 ws 陷入休眠

如果头节点 ws = 0，则设置 ws = PROPAGATE 告诉头节点我释放了资源，你应该唤醒后继节点

Node.PROPAGATE 状态

为了解决一个 BUG，该 BUG 导致线程永久堵塞

早期没有这个字段

假设当前资源为 0，线程 A 和 B 正在尝试获取资源而堵塞

头节点 ws 被后继节点设置为 singal

线程 C 释放资源

头节点 ws = singal，唤醒后继节点 A

设置 ws = 0

线程 A 被唤醒，尝试获取资源，获取资源成功，但就在 CAS 设置为头节点后，发生中断

线程 D 抢占，释放资源

头节点 ws = 0，因此不会唤醒节点

线程 B 得不到运行

线程 A 继续运行，不会唤醒线程 B

早期的判断为资源可用 && ws != 0，才会唤醒节点

资源是一个 int 值，在线程 A 的私有栈中是不可用的

此时 ws = 0，因此不会唤醒 B

虽然有资源，但线程 B 永久堵塞

引入 Node.PROPAGATE 字段

线程 D 发现头节点 ws = 0，则设置 ws = Node.PROPAGATE

线程 A 继续运行，发现 ws = Node.PROPAGATE，继续唤醒后继节点

思想就是，在共享模式中，凡是有线程释放资源，则必须至少要唤醒后继节点一次

条件队列

调用 await 的线程将被加入 ConditionObject 维护的条件队列中

加入到条件队列后，线程会释放占有的锁

随后线程在 while 循环中检查是否在条件队列中

在则陷入休眠等待唤醒继续判断

如果不在说明被唤醒了，已经被添加到同步队列中，剩余逻辑与独占模式 acquireQueued 相同

唤醒其实就是选择条件队列中的队头加入到同步队列中竞争

可重入锁实现

内部维护一个 AQS 继承类，实现 tryAcquire 和 tryRelease 方法

AQS 继承了 AbstractOwnableSynchronizer 类，可以 set 和 get 独占线程

实现可重入

公平锁的实现只需要比对当前线程是否是同步队列的第一个线程(通常是 head.next.Thread)

信号量实现

实现共享模式的 AQS

计数器实现

实现共享模式的 AQS

资源 = 0 时表示已完成，返回 1 以唤醒节点

否则应该返回 -1

线程池

线程池状态

RUNNING：能接受新提交的任务，并且也能处理阻塞队列中的任务，即存在核心线程空闲

SHUTDOWN：指调用了 shutdown() 方法，不再接受新提交的任务，但却可以继续处理既有的任务以及阻塞队列中已保存的任务

STOP：指调用了 shutdownNow() 方法，不再接受新提交的任务，同时抛弃阻塞队列里的所有任务并中断所有正在执行任务

TIDYING：所有任务都执行完毕，workerCount 有效线程数为 0

TERMINATED：终止状态，当执行 terminated() 后会更新为这个状态

工作原理

原子数 ctl 前 3 位保存线程池的 5 大状态，后 29 位保存有效线程数

任何写操作都是利用 CAS

线程数最多为 2^29 - 1

如果线程数小于核心线程数且线程池运行中

addWorker 直接运行线程

如果线程数大于等于核心线程数且线程池运行中

添加至堵塞队列等待线程取任务

如果添加队列失败

如果线程数小于最大线程数，则直接 addWorker 运行

否则拒绝处理

线程 run 方法内不停在 while 循环内取任务

线程复用

线程执行任务时会上锁(Worker 继承 AQS)

在关闭线程池时(shoutDown)，只会中断能够获取锁的线程，即正在运行的线程不会被中断

取任务的方法为 getTask，一旦没取到任务，线程就会注销

超过最大线程数时将返回 NULL

最大线程数可以更改

当前状态为 STOP，返回 NULL

当前状态为 SHOUTDOWN 并且队列为空，返回 NULL

当前线程数大于核心线程数并且线程执行时间大于 keepAlive，返回 NULL

其他情况下，从堵塞队列中不停获取任务

shoutDown 和 shoutDownNow 方法的区别

线程池参数

核心线程数

最大线程数

空闲线程等待时间

时间单位

堵塞队列

线程工厂

拒绝处理程序

优点

● 避免频繁创建销毁，降低资源消耗，提高任务响应速度。 ● 显示指定参数，便于管理线程。 ● 线程池会记录一些信息，便于管理、排错。

同步堵塞的概念

同步与非同步

从 CPU 的角度看

同步 IO 指数据到达网卡时，通知 CPU，CPU 主动读取数据到内存中

异步 IO 指数据到达网卡时，由硬件读取数据到内存中，再通知 CPU

DMA

从用户的角度看

同步 IO 指数据到达内存时，通知用户应用程序，用户发起读取指令，读取数据到用户态中，读取时陷入系统调用，用户线程是堵塞的

异步 IO 指数据到达内存时，由操作系统等中间程序读取数据到用户预先准备的缓冲区中，然后通知用户，用户可以直接处理数据而不必发起读取

Netty 对应用程序来说是异步的，Netty 本身实现是同步还是异步的依赖底层 API

堵塞与非堵塞

从系统层面和用户层面看

select 对于用户而言是堵塞的

对于操作系统而言是非堵塞的，CPU 发送读信号，然后等待中断发生

堵塞至指发起操作到操作完成时必须是堵塞的

非堵塞指如果数据还没准备好，那么会立即返回

Reactor 模型

注册所有感兴趣的事件处理器，单线程轮询选择就绪事件，执行事件处理器

IO 多路复用

同步

操作系统只是通知用户事件到来，读操作还是由用户发起

堵塞

需要堵塞，但堵塞为了等待任一通道上的 IO 发生

Proactor 模型

异步 IO，AIO

对用户模拟出的 AIO

真正的 AIO 需要系统 API 的支持

Netty 本身是同步的，但用户看来就是异步的

相比于 Reactor 模型，Proactor 模型会将读事件执行完毕，将数据拷贝到用户缓冲区中才会调用用户处理程序

proactor 关注于 “读完了”，reactor 关注 "可以读了"

底层都是 IO 多路复用

Java NIO

NIO 模式

channel.configureBlocking(false)

调用 connect、read、write 都是非堵塞的

要在循环中不断调用

Reactor 模式

channel.register(selector, SelectionKey.OP_ACCEPT)

到 Selector 中注册通道，同时表明对该通道上何种事件感兴趣

IO 多路复用

底层是 select、poll、epoll

多路复用底层原理

select

创建文件描述符集合，将集合拷贝到内核态中

最大数量为 1024

用 bitset 维护

检测到 IO 事件发生时，唤醒正在等待此事件的线程

操作系统设置文件描述符状态

操作系统唤醒 select

select 返回可读写的文件描述符总数

select 会将内核态的文件描述符集合拷贝回用户态

根据返回的总数遍历文件描述符集合，轮询得到对应的描述符集合

select 靠修改状态位表示文件描述符就绪

状态位改变，再次监控是需重新执行此步骤

epoll

在内核态高速缓冲区中开辟一份空间存放红黑树和就绪链表

创建文件描述符集合，将文件描述符添加至红黑树中，注册文件句柄的回调函数

IO 事件发生时，内核执行对应文件描述符的回调函数，通知 epoll

该回调函数将文件描述符放入就绪链表

内核唤醒 epoll

epoll 被唤醒，监控就绪链表，如果链表非空，将链表中的文件句柄拷贝到用户态

内核没有修改状态位，因此再次监控时无须拷贝

调用 add 或 delete 动态操作文件句柄

水平触发 LT

只要文件句柄可读并且读缓冲区非空

不停发送可读信号通知 epoll

只要文件句柄可写并且写缓冲区非满

不停发送可写信号通知 epoll

除非调用 flush 刷新写事件

边缘触发 ET

只有当文件句柄最开始触发相应事件时进行通知

对比

select 每一次监听都需要拷贝全部的描述符，而 epoll 不需要

select 事件触发时会拷贝全部描述符给用户态，而 epoll 只拷贝触发事件的描述符

select 需要遍历所有描述符，而 epoll 就绪链表中就是对应描述符

虽然 epoll 很高效，但内核态维护红黑树的成本也是不可忽视的