Java 并发
58 同城 Java ⾯试
分享过很多⼩⼚和⼤⼚的后端⾯经，这次来分享互 联⽹中⼚的⾯经，⾯试难度也是刚好介于 ⼤⼚
和⼩⼚之间。
除了技术问题之外，互联⽹中⼚⾯试环节也需要⼿撕算法，所以想冲中⼤⼚的同学们，算法不能
拉下。
这次分享 58 同城的Java 后端开发⾯经，问题不算特别多，15 个左右，再加上 1 个算法题
考察的知识点；
Java ：HashMap 、ConcurrentHashMap 、volatile 、sychronized 、线程池
⽹络：TCP 三次握⼿、四次挥⼿、netstat 命令
mysql ：B+ 树和B树、聚簇索引和⾮聚簇索引
排序算法：快排时间复杂度、冒泡排序时间复杂度
⼿撕算法：单链表删除重复元素
Java 并发
HashMap 和ConcurrentHashMap 区别是什么 ？
HashMap 不是线程安全的，ConcurrentHashMap 是线程安全的。
HashMap 底层实现
在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap 通过哈希算法将元素的键
（Key ）映射到数组中的槽位（Bucket ）。如果多个键映射到同⼀个槽位，它们会以 链表的形式
存储在同⼀个槽位上，因为链表的查询时间是O(n) ，所以冲突很严重，⼀个索引上的链表⾮常⻓，效率就很低了。
所以在 JDK 1.8 版本的时候做 了优化，当⼀个链表的⻓度超过8的时候就转换数据结构，不再使
⽤链表存储，⽽是使⽤红⿊树，查找时使⽤红⿊树，时间复杂度O（log n ），可以提⾼查询性
能，但是在数量较少时，即数量⼩于6时，会将红⿊树转换回链表。
ConcurrentHashMap 底层实现
在 JDK 1.7 中它使⽤的是数组加链表的形式 实现的，⽽数组⼜分为：⼤数组 Segment 和⼩数组
HashEntry 。Segment 是⼀种可重⼊锁（ReentrantLock ），在 ConcurrentHashMap ⾥扮演锁的
⻆⾊；HashEntry 则⽤于存储键值对数据。⼀个 ConcurrentHashMap ⾥包含⼀个 Segment 数
组，⼀个 Segment ⾥包含⼀个 HashEntry 数组，每个 HashEntry 是⼀个链表结构的元素。简单
理解就是，ConcurrentHashMap 是⼀个 Segment 数组，Segment 通过继承 ReentrantLock 来
进⾏加锁，所以每次 需要加锁的操作锁住的是⼀个 segment ，这样只要保证每个 Segment 是线
程安全的，也就实现了全局的线程安全。
JDK 1.8 也引⼊了红⿊树，优化了之 前的固定链表，那么当数据量⽐较⼤的时候，查询性能也得
到了很⼤的提升，从之 前的 O(n) 优化到了 O(logn) 的时间复杂度。 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的，ConcurrentHashMap 通过对头结
点加锁来保证线程安全的，锁的粒度相⽐ Segment 来说更⼩了，发⽣冲突和加锁的频率降低
了，并发操作的性能就提⾼了。
CAS 和sychronized 分别 ⽤于ConcurrentHashMap 什么 场景？
添加元素时⾸先会判断容器是否为空：
如果为空则使⽤ volatile 加 CAS 来初始化
如果容器不为 空，则根据存储的元素计算该位置是否为空。
如果根据存储的元素计算结果为空，则利 ⽤ CAS 设置该节点；
如果根据存储的元素计算结果不为 空，则使⽤ synchronized ，然后，遍历桶中的数据，并替换
或新增节点到桶中，最后再判断是否需要转为红⿊树，这样就能保证并发访问时的线程安全
了。
volatile 和sychronized ⽐较，原理？
Synchronized 解决了多线程访问共享资源时可能出现的竞态条件和数据不⼀致的问题，保证了线程
安全性。Volatile 解决了变量在多线程环境下的可⻅性和有序性问题，确保了变量的修改对其他线
程是可⻅的。
Synchronized: Synchronized 是⼀种排他性的同步机制，保证了多个线程访问共享资源时的互斥
性，即同⼀时刻只允许⼀个线程访问共享资源。通过对代码块或⽅法添加Synchronized 关键字
来实现同步。
Volatile: Volatile 是⼀种轻量级的同步机制，⽤来保证变量的可⻅性和禁⽌指令重排序。当⼀个
变量被声明为Volatile 时，线程在读取该变量时会直接从内存中读取，⽽不会使 ⽤缓存，同时对
该变量的写操作会 ⽴即刷回主内存，⽽不是缓存在本地内存中。
volatile 和sychronized 如何实现单例模式
public class Singleton {
private volatile static Singleton single ;
private Singleton (){}
public static Singleton getSingleton () {
if (single == null ) {
// 双重检查加锁，只有在第一次实例化时，才启用同步机制，提高了性能。
synchronized (Singleton .class ) {
if (single == null ) {
}
return single;
}
}正确的双重检查锁定模式需要需要使⽤ volatile 。volatile 主要包含两个 功能。
保证可⻅性。使⽤ volatile 定义的变量，将会保 证对所有线程的可⻅性。
禁⽌指令重排序优化。
由于 volatile 禁⽌对象创建时指令之间重排序，所以其他线程不会访问到⼀个未初始化的对象，从
⽽保证安全性。
线程池的⼯作流程是什么 ？
线程池是为了 减少频繁的创建线程和销毁线程带来的性能损耗。
线程池分为核⼼线程池，线程池的最⼤容量，还有等待任务的队列，提交⼀个任务，如果核⼼线
程没有满，就创建⼀个线程，如果满了，就是会加⼊等待队列，如果等待队列满了，就会增加线
程，如果达到最⼤线程数量，如果都达到最⼤线程数量，就会按照⼀些丢 弃的策略进⾏处理。
线程池的构造函数有7个参数：
corePoolSize ：线程池核⼼线程数量。默认情况下，线程池中线程的数量如果 <= corePoolSize ，那么即使这些线程处于空闲状态，那也不 会被销毁。maximumPoolSize ：限制了线程池能创建的最⼤线程总数（包括核⼼线程和⾮核⼼线程），当
corePoolSize 已满 并且 尝试将新任务加 ⼊阻塞队列失败（即队列已满）并且 当前线程数 <maximumPoolSize ，就会创建新线程执⾏此任务，但是当 corePoolSize 满 并且 队列满 并且
线程数已达 maximumPoolSize 并且 ⼜有新任务提交时，就会触发拒绝策略。
keepAliveTime ：当线程池中线程的数量⼤于corePoolSize ，并且某个线程的空闲时间超过了
keepAliveTime ，那么这个线程就会被销毁。
unit ：就是keepAliveTime 时间的单位。
workQueue ：⼯作队列。当没有空闲的线程执⾏新任务时，该任务就会被放⼊⼯作队列中，等
待执⾏。
threadFactory ：线程⼯⼚。可以⽤来给线 程取名字等等
handler ：拒绝策略。当⼀个新任务交给线 程池，如果此时线程池中有空闲的线程，就会直接执
⾏，如果没有空闲的线程，就会将该任务加 ⼊到阻塞队列中，如果阻塞队列满了，就会创建⼀
个新线程，从阻塞队列头部取出⼀个任务来执⾏，并将新任务加 ⼊到阻塞队列末尾。如果当前
线程池中线程的数量等于maximumPoolSize ，就不会创建新线程，就会去执⾏拒绝策略。
使⽤过什么 线程池？
ScheduledThreadPool ：可以设置定期的执⾏任务，它⽀持定时或周期性执⾏任务，⽐如每隔
10 秒钟执⾏⼀次任务，我通过这 个实现类设置定期执⾏任务的策略。
FixedThreadPool ：它的核⼼线程数和最⼤线程数是⼀样的，所以可以把它看作是固定线程数的
线程池，它的特点是线程池中的线程数除了初始阶段需要从 0 开始增加外，之后的线程数量就
是固定的，就算任务数超过线程数，线程池也不 会再创建更多的线程来处理任务，⽽是会把超
出线程处理能⼒的任务放到任务队列中进⾏等待。⽽且就算任务队列满了，到了本该继续增加
线程数的时候，由于它的最⼤线程数和核⼼线程数是⼀样的，所以也⽆法再增加新的线程了。
CachedThreadPool ：可以称作可缓存线程池，它的特点在于线程数是⼏乎可以⽆限增加的（实
际最⼤可以达到 Integer.MAX_VALUE ，为 2^31-1 ，这个数⾮常⼤，所以基本不可能达到），⽽当线程闲置时还可以对线程进⾏回收。也就是说该线程池的线程数量不是固定不变的，当然它
也有⼀个⽤于存储提交任务的队列，但这个队列是 SynchronousQueue ，队列的容量为0，实际
不存储任何任 务，它只负责 对任务进⾏中转和传递，所以效率⽐较⾼。
SingleThreadExecutor ：它会使 ⽤唯⼀的线程去执⾏任务，原理和 FixedThreadPool 是⼀样的，
只不过这 ⾥线程只有⼀个，如果线程在执⾏任务的过程中发⽣异常，线程池也会重新创建⼀个
线程来执⾏后续的任务。这种线程池由于只有⼀个线程，所以⾮常适合⽤于所有任务都需要按
被提交的顺序依次执⾏的场景，⽽前⼏种线程池不⼀定能够保障任务的执⾏顺序等于被提交的
顺序，因为它们是多线程并⾏执⾏的。
SingleThreadScheduledExecutor ：它实 际和 ScheduledThreadPool 线程池⾮常相似，它只是
ScheduledThreadPool 的⼀个特例，内部只有⼀个线程。
⽹络
tcp 的三次握⼿过程说⼀下
⼀开始，客⼾端和服务端都处于 CLOSE 状态。先是服务端主动监听某个端⼝，处于 LISTEN 状
态客⼾端会随机初始化序号（client_isn ），将此序号置于 TCP ⾸部的「序号」字段中，同时把
SYN 标志位置为 1，表⽰ SYN 报⽂。接着把第⼀个 SYN 报⽂发送给服务端，表⽰向服务端发起
连接，该报⽂不包含应⽤层数据，之后客⼾端处于 SYN-SENT 状态。
服务端收到客⼾端的 SYN 报⽂后，⾸先服务端也随机初始化⾃⼰的序号（server_isn ），将此序
号填⼊ TCP ⾸部的「序号」字段中，其次把 TCP ⾸部的「确认应答号」字段填⼊ client_isn + 1,接着把 SYN 和 ACK 标志位置为 1。最后把该报⽂发给客⼾端，该报⽂也不 包含应⽤层数据，之
后服务端处于 SYN-RCVD 状态。
客⼾端收到服务端报⽂后，还要向服务端回应最后⼀个应答报⽂，⾸先该应答报⽂ TCP ⾸部
ACK 标志位置为 1 ，其次「确认应答号」字段填⼊ server_isn + 1 ，最后把报 ⽂发送给服务
端，这次报⽂可以携带客⼾到服务端的数据，之后客⼾端处于 ESTABLISHED 状态。
服务端收到客⼾端的应答报⽂后，也进⼊ ESTABLISHED 状态。
四次挥⼿的各个状态说⼀下
具体过程：
客⼾端主动调⽤关闭连接的函数，于是就会发送 FIN 报⽂，这个 FIN 报⽂代表客⼾端不会再发
送数据了，进⼊ FIN_WAIT_1 状态；服务端收到了 FIN 报⽂，然后⻢上回复⼀个 ACK 确认报⽂，此时服务端进⼊ CLOSE_WAIT 状
态。在收到 FIN 报⽂的时候，TCP 协议栈会为 FIN 包插⼊⼀个⽂件结束符 EOF 到接收缓冲区
中，服务端应⽤程序可以通过 read 调⽤来感知这个 FIN 包，这个 EOF 会被放在已排队等候的
其他已接收的数据之后，所以必须要得继续 read 接收缓冲区已接收的数据；
接着，当服务端在 read 数据的时候，最后⾃然就会读到 EOF ，接着 read() 就会返回 0，这时服务端应⽤程序如果有 数据要发送的话，就发完数据后才调⽤关闭连接的函数，如果服 务端应⽤
程序没有数据要发送的话，可以直接调⽤关闭连接的函数，这时服务端就会发⼀个 FIN 包，这
个 FIN 报⽂代表服务端不会再发送数据了，之后处于 LAST_ACK 状态；
客⼾端接收到服务端的 FIN 包，并发送 ACK 确认包给服务端，此时客⼾端将进⼊ TIME_WAIT
状态；
服务端收到 ACK 确认包后，就进⼊了最后的 CLOSE 状态；
客⼾端经过 2MSL 时间之后，也进⼊ CLOSE 状态；
为什么 创建连接是三次握⼿？
三次握⼿的原因：
三次握⼿才可以阻⽌重复历史连接的初始化（主要原因）
三次握⼿才可以同步双⽅的初始序列号
三次握⼿才可以避免资源浪费
原因⼀：避免历史连接
我们来看看 RFC 793 指出的 TCP 连接使⽤三次握⼿的⾸要原因：
The principle reason for the three-way handshake is to prevent old duplicate connection initiations from causing confusion.
简单来说，三次握⼿的⾸要原因是为了 防⽌旧的重复连接初始化造成混乱。
我们考虑⼀个场景，客⼾端先发送了 SYN （seq = 90 ）报⽂，然后客⼾端宕机了，⽽且这个 SYN报⽂还被⽹络阻塞了，服务端并没有收到，接着客⼾端重启后 ，⼜重新向服务端建⽴连接，发送
了 SYN （seq = 100 ）报⽂（注意！不是重传 SYN ，重传的 SYN 的序列号是⼀样的）。看看 三次握⼿是如何阻⽌历史连接的：
客⼾端连续发送多次 SYN （都是同⼀个四元组）建⽴连接的报⽂，在⽹络拥堵情况下：
⼀个「旧 SYN 报⽂」⽐「最新的 SYN 」 报⽂早到达了服务端，那么此时服务端就会回⼀个
SYN + ACK 报⽂给客⼾端，此报⽂中的确认号是 91 （90+1 ）。
客⼾端收到后，发现⾃⼰期望 收到的确认号应该是 100 + 1 ，⽽不是 90 + 1 ，于是就会回 RST
报⽂。
服务端收到 RST 报⽂后，就会释放连接。
后续最新的 SYN 抵达了服务端后，客⼾端与服务端就可以正常的完成三次握⼿了。
上述中的「旧 SYN 报⽂」称为历史连接，TCP 使⽤三次握⼿建⽴连接的最主要原因就是防⽌「历
史连接」初始化了连接。
如果是两次握⼿连接，就⽆法阻⽌历史连接，那为什么 TCP 两次握⼿为什么 ⽆法阻⽌历史连接
呢？
我先直接说结论，主要是因为在两次握⼿的情况下，服务端没有中间状态给客⼾端来阻⽌历史连
接，导致服务端可能建⽴⼀个历史连接，造成资源浪费。
你想想 ，在两次握⼿的情况下，服务端在收到 SYN 报⽂后，就进⼊ ESTABLISHED 状态，意味着这
时可以给对⽅发送数据，但是客⼾端此时还没有进⼊ ESTABLISHED 状态，假设这次是历史连接，
客⼾端判断到此次 连接为历史连接，那么就会回 RST 报⽂来断开连接，⽽服务端在第⼀次握⼿的
时候就进⼊ ESTABLISHED 状态，所以它可以发送数据的，但是它并不知道这个是历史连接，它只
有在收到 RST 报⽂后，才会断开连接。
可以看到，如果采⽤两次握⼿建⽴ TCP 连接的场景下，服务端在向客⼾端发送数据前，并没有阻
⽌掉历史连接，导致服务端建⽴了⼀个历史连接，⼜⽩⽩发送了数据，妥妥 地浪费了服务端的资
源。
因此，要解 决这种现象，最好就是在服务端发送数据前，也就是建⽴连接之前，要阻⽌掉历史连
接，这样就不会造成资源浪费，⽽要实现这个功能，就需要三次握⼿。
所以，TCP 使⽤三次握⼿建⽴连接的最主要原因是防⽌「历史连接」初始化了连接。
原因⼆：同步双⽅初始序列号
TCP 协议的通信双⽅， 都必须维护⼀个「序列号」， 序列号是可靠传输的⼀个关键因素，它的作
⽤：
接收⽅可以去除重复的数据；
接收⽅可以根据数据包的序列号按序接收；
可以标识发送出去的数据包中， 哪些是已经被对⽅收到的（通过 ACK 报⽂中的序列号知道）；
可⻅，序列号在 TCP 连接中占据着⾮常重要的作⽤，所以当客⼾端发送携带「初始序列号」的
SYN 报⽂的时候，需要服务端回⼀个 ACK 应答报⽂，表⽰客⼾端的 SYN 报⽂已被服务端成功接
收，那当服务端发送「初始序列号」给客⼾端的时候，依然也要得到客⼾端的应答回应，这样⼀
来⼀回，才能确保双⽅的初始序列号能被可靠的同步。
四次握⼿其实也能够可靠的同步双⽅的初始化序号，但由于第⼆步和第三步可以优 化成⼀步，所
以就成了「三次握⼿」。
⽽两次握⼿只保证了⼀⽅的初始序列号能被对⽅成功接收，没办法保证双⽅的初始序列号都能被
确认接收。
原因三：避免资源浪费
如果只有「两次握⼿」，当客⼾端发⽣的 SYN 报⽂在⽹络中阻塞，客⼾端没有接收到 ACK 报⽂，
就会重新发送 SYN ，由于没有第三次握⼿，服务端不清楚客⼾端是否收到了⾃⼰回复的 ACK 报
⽂，所以服务端每收到⼀个 SYN 就只能先主动建⽴⼀个连接，这会造成什么 情况呢？
如果客⼾端发送的 SYN 报⽂在⽹络中阻塞了，重复发送多次 SYN 报⽂，那么服务端在收到请求后
就会建⽴多个冗余的⽆效链接，造成不必要的资源浪费。
即两次握⼿会造成消息滞留情况下，服务端重复接受⽆⽤的连接请求 SYN 报⽂，⽽造成重复分配
资源。
为什么 断开连接是四次挥⼿？
服务器收到客⼾端的 FIN 报⽂时，内核会⻢上回⼀个 ACK 应答报⽂，但是服务端应⽤程序可能还
有数据要发送，所以并不能⻢上发送 FIN 报⽂，⽽是将发送 FIN 报⽂的控制权交给服务端应⽤程
序：
如果服 务端应⽤程序有数据要发送的话，就发完数据后，才调⽤关闭连接的函数；
如果服 务端应⽤程序没有数据要发送的话，可以直接调⽤关闭连接的函数，
从上 ⾯过程可知，是否要发送第三次挥⼿的控制权不在内核，⽽是在被动关闭⽅的应⽤程序，因
为应⽤程序可能还有数据要发送，由应⽤程序决定什么 时候调⽤关闭连接的函数，当调⽤了关闭
连接的函数，内核就会发送 FIN 报⽂了，所以服务端的 ACK 和 FIN ⼀般都会分开发送。
linux 使⽤什么 命令查看某个端⼝被占⽤？
netstat 命令
MySQL
mysql 的为什么 选取B+ 树，作为存储结构，与B树的⽐较？
B+ 树与 B 树差异的点，主要是以下这⼏点：
叶⼦节点（最底部的节点）才会存放实际数据（索引+记录），⾮叶⼦节点只会存放索引；
所有索引都会在叶⼦节点出现，叶⼦节点之间构成⼀个有序链表；
⾮叶⼦节点的索引也会同时存在在 ⼦节点中，并且是在⼦节点中所有索引的最⼤（或最⼩）。
⾮叶⼦节点中有多少个⼦节点，就有多少个索引；
MySQL 默认的存储引擎 InnoDB 采⽤的是 B+ 作为索引的数据结构，原因有：
B+ 树的⾮叶⼦节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相⽐存储
即存索引⼜存记录的 B 树，B+ 树的⾮叶⼦节点可以存放更多的索引，因此 B+ 树可以⽐ B 树更
「矮胖」，查询底层节点的磁盘 I/O 次数会更少。
B+ 树有⼤量的冗余节点（所有⾮叶⼦节点都是冗余索引），这些冗余索引让 B+ 树在插⼊、删
除的效率都更⾼，⽐如删除根节点的时候，不会像 B 树那样会发⽣复杂的树的变化 ；
B+ 树叶⼦节点之间⽤链表连接了起来，有利于范围查询，⽽ B 树要实现范围查询，因此只能通
过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。
聚集索引和⾮聚集索引区别是什么 ？
回表
在 MySQL 的 InnoDB 引擎中，每个索引都会对应⼀颗 B+ 树，⽽聚簇索引和⾮聚簇索引最⼤的区
别在于叶⼦节点存储的数据不同，聚簇索引叶⼦节点存储的是⾏数据，因此通过聚簇索引可以直
接找到真正的⾏数据；⽽⾮聚簇索引叶⼦节点存储的是主键id ，所以使 ⽤⾮聚簇索引还需要回表查
询。
因此聚簇索引和⾮聚簇索引的区别主要有以下⼏个：
聚簇索引叶⼦节点存储的是⾏数据；⽽⾮聚簇索引叶⼦节点存储的是聚簇索引（通常是主键
ID ）。
聚簇索引查询效率更⾼，⽽⾮聚簇索引需要进⾏回表查询，因此性能不如聚簇索引。
聚簇索引⼀般为主 键索引，⽽主键⼀个表中只能有⼀个，因此聚簇索引⼀个表中也 只能有⼀
个，⽽⾮聚簇索引则没有数量上的限制。
排序算法
快速排序最坏复杂度，最坏是什么 情况
快速排序是⼀种不稳定排序，它的时间复杂度为O(n·lgn) ，最坏情况为O(n2) ；空间复杂度为
O(n·lgn)快速排序最坏的情况还得看枢轴（pivot ）的选择策略。在快速排序的早期版本中呢，最左⾯或者
是最右⾯的那个元素被选为枢轴，那最坏的情况就会在下⾯的情况下发⽣啦：
数组已经是正序（same order ）排过序的。
数组已经是倒序排过序的。
所有的元素都相同（1、2的特殊情况）
因为这些案例在⽤例中⼗分常⻅，所以这个问题可以通过要么选择⼀个随机的枢轴，或者选择⼀
个分区中间的下标作为枢轴，或者（特别是对于相⽐更⻓的分区）选择分区的第⼀个、中间、最
后⼀个元素的中值作为枢轴。
有了这些修改，那快排的最差的情况就不那么容易出现了，但是如果输⼊的数组最⼤（或者最⼩
元素）被选为枢轴，那最坏的情况就⼜来了。
冒泡排序最坏复杂度，最好情况？
冒泡排序的最好时间复杂度出现在以下情况：当待 排序数组已经有序时，即每个元素都⽐其前
⾯的元素⼩，那么在第⼀次遍历数组时就可以确定排序已 经完成，因此时间复杂度为O(n) 。
冒泡排序的时间复杂度为O(n^2) 。因为在排序过程中，需要进⾏多次遍历和元素交换，⽽每次
遍历都需要⽐较相邻的元素并决定是否进⾏交换，这种操作需要花费O(n) 的时间。因此，冒泡
排序的时间复杂度通常为O(n^2) 。算法
单链表删除重复元素