最近有位读者去虾皮面试啦，所以今天给大家推荐一篇整理了 15 道虾皮面试真题答案的文章。

文中比较长，大家可以收藏慢慢看。

image.png

排序链表
对称与非对称加密算法的区别
TCP如何保证可靠性
聊聊五种IO模型
hystrix 工作原理
延时场景处理
https请求过程
聊聊事务隔离级别，以及可重复读写的原理
聊聊索引在哪些场景下会失效？
什么是虚拟内存
排行榜的实现，比如高考成绩排序
分布式锁实现
聊聊零拷贝
聊聊synchronized
分布式ID生成方案

1. 排序链表

给你链表的头结点head ，请将其按升序排列并返回排序后的链表。

image.png

实例1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

实例2：

image.png

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

这道题可以用 双指针+归并排序 算法解决，主要以下四个步骤

\1. 快慢指针法，遍历链表找到中间节点
\2. 中间节点切断链表
\3. 分别用归并排序排左右子链表
\4. 合并子链表

完整代码如下：

class Solution {
    public ListNode sortList(ListNode head) {
        //如果链表为空，或者只有一个节点，直接返回即可，不用排序
        if (head == null || head.next == null)
            return head;

        //快慢指针移动，以寻找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next !=null){
          fast = fast.next.next;
          slow = slow.next;
        }
        //找到中间节点，slow节点的next指针，指向mid
        ListNode mid = slow.next;
        //切断链表
        slow.next = null;

        //排序左子链表
        ListNode left = sortList(head);
        //排序左子链表
        ListNode right = sortList(mid);

        //合并链表
        return merge(left,right);
    }

    public ListNode merge(ListNode left, ListNode right) {
       ListNode head = new ListNode(0);
       ListNode temp = head;
       while (left != null && right != null) {
           if (left.val <= right.val) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        if (left != null) {
            temp.next = left;
        } else if (right != null) {
            temp.next = right;
        }
        return head.next;
    }
}

2.对称与非对称加密算法的区别

先复习一下相关概念：

明文：指没有经过加密的信息/数据。
密文：明文被加密算法加密之后，会变成密文，以确保数据安全。
密钥：是一种参数，它是在明文转换为密文或将密文转换为明文的算法中输入的参数。密钥分为对称密钥与非对称密钥。
加密：将明文变成密文的过程。
解密：将密文还原为明文的过程。

对称加密算法:加密和解密使用 相同密钥 的加密算法。常见的对称加密算法有 AES、3DES、DES、RC5、RC6 等。

image.png

非对称加密算法：非对称加密算法需要两个密钥（公开密钥和私有密钥）。公钥与私钥是成对存在的，如果用公钥对数据进行加密，只有对应的私钥才能解密。主要的非对称加密算法有： RSA、Elgamal、DSA、D-H、ECC 。

image.png

3. TCP如何保证可靠性

首先，TCP的连接是基于三次握手，而断开则是四次挥手。确保连接和断开的可靠性。
其次，TCP的可靠性，还体现在有状态;TCP会记录哪些数据发送了，哪些数据被接受了，哪些没有被接受，并且保证数据包按序到达，保证数据传输不出差错。
再次，TCP的可靠性，还体现在可控制。它有报文校验、ACK应答、超时重传(发送方)、失序数据重传（接收方）、丢弃重复数据、流量控制（滑动窗口）和拥塞控制等机制。

4. 聊聊五种IO模型

4.1 阻塞IO 模型

假设应用程序的进程发起IO调用，但是如果内核的数据还没准备好的话，那应用程序进程就一直在阻塞等待，一直等到内核数据准备好了，从内核拷贝到用户空间，才返回成功提示，此次IO操作，称之为阻塞IO。

image.png

4.2 非阻塞IO模型

如果内核数据还没准备好，可以先返回错误信息给用户进程，让它不需要等待，而是通过查询的方式再来请求。这就是非阻塞IO，流程图如下：

image.png

4.3 IO多路复用模型

IO多路复用之select

应用进程通过调用select函数，可以同时监控多个fd，在select函数监控的fd中，只要有任何一个数据状态准备就绪了，select函数就会返回可读状态，这时应用进程再发起recvfrom请求去读取数据。

image.png

select有几个缺点：

最大连接数有限，在Linux系统上一般为1024。
select函数返回后，是通过遍历fdset，找到就绪的描述符fd。

IO多路复用之epoll

为了解决select存在的问题，多路复用模型epoll诞生，它采用事件驱动来实现，流程图如下：

image.png

epoll先通过epoll_ctl()来注册一个fd（文件描述符），一旦基于某个fd就绪时，内核会采用回调机制，迅速激活这个fd，当进程调用epoll_wait()时便得到通知。这里去掉了遍历文件描述符的坑爹操作，而是采用监听事件回调的机制。这就是epoll的亮点。

4.4 IO模型之信号驱动模型

信号驱动IO不再用主动询问的方式去确认数据是否就绪，而是向内核发送一个信号（调用sigaction的时候建立一个SIGIO的信号），然后应用用户进程可以去做别的事，不用阻塞。当内核数据准备好后，再通过SIGIO信号通知应用进程，数据准备好后的可读状态。应用用户进程收到信号之后，立即调用recvfrom，去读取数据。

image.png

4.5 IO 模型之异步IO(AIO)

AIO实现了IO全流程的非阻塞，就是应用进程发出系统调用后，是立即返回的，但是立即返回的不是处理结果，而是表示提交成功类似的意思。等内核数据准备好，将数据拷贝到用户进程缓冲区，发送信号通知用户进程IO操作执行完毕。

流程如下：

image.png

5. hystrix 工作原理

Hystrix 工作流程图如下:

image.png

构建命令

Hystrix 提供了两个命令对象：HystrixCommand和HystrixObservableCommand，它将代表你的一个依赖请求任务，向构造函数中传入请求依赖所需要的参数。

执行命令

有四种方式执行Hystrix命令。分别是：

R execute()：同步阻塞执行的，从依赖请求中接收到单个响应。
Future queue()：异步执行，返回一个包含单个响应的Future对象。
Observable observe()：创建Observable后会订阅Observable，从依赖请求中返回代表响应的Observable对象
Observable toObservable()：cold observable，返回一个Observable，只有订阅时才会执行Hystrix命令，可以返回多个结果

检查响应是否被缓存

如果启用了 Hystrix缓存，任务执行前将先判断是否有相同命令执行的缓存。如果有则直接返回包含缓存响应的Observable；如果没有缓存的结果，但启动了缓存，将缓存本次执行结果以供后续使用。

检查回路器是否打开回路器(circuit-breaker)和保险丝类似，保险丝在发生危险时将会烧断以保护电路，而回路器可以在达到我们设定的阀值时触发短路(比如请求失败率达到50%)，拒绝执行任何请求。

如果回路器被打开，Hystrix将不会执行命令，直接进入Fallback处理逻辑。

检查线程池/信号量/队列情况 Hystrix 隔离方式有线程池隔离和信号量隔离。当使用Hystrix线程池时，Hystrix 默认为每个依赖服务分配10个线程，当10个线程都繁忙时，将拒绝执行命令,，而是立即跳到执行fallback逻辑。
执行具体的任务通过HystrixObservableCommand.construct() 或者 HystrixCommand.run() 来运行用户真正的任务。
计算回路健康情况每次开始执行command、结束执行command以及发生异常等情况时，都会记录执行情况，例如：成功、失败、拒绝和超时等指标情况，会定期处理这些数据，再根据设定的条件来判断是否开启回路器。
命令失败时执行Fallback逻辑在命令失败时执行用户指定的 Fallback 逻辑。上图中的断路、线程池拒绝、信号量拒绝、执行执行、执行超时都会进入Fallback处理。
返回执行结果原始对象结果将以Observable形式返回，在返回给用户之前，会根据调用方式的不同做一些处理。

6. 延时场景处理

日常开发中，我们经常遇到这种业务场景，如：外卖订单超30分钟未支付，则自动取消订单；用户注册成功15分钟后，发短信消息通知用户等等。这就是延时任务处理场景。针对此类场景我们主要有以下几种处理方案：

JDK的DelayQueue延迟队列
时间轮算法
数据库定时任务（如Quartz）
Redis ZSet 实现
MQ 延时队列实现

7.https请求过程

HTTPS = HTTP + SSL/TLS，即用SSL/TLS对数据进行加密和解密，Http进行传输。
SSL，即Secure Sockets Layer（安全套接层协议），是网络通信提供安全及数据完整性的一种安全协议。
TLS，即Transport Layer Security(安全传输层协议)，它是SSL 3.0的后续版本。

image.png

http请求流程

用户在浏览器里输入一个https网址，然后连接到server的443端口。
服务器必须要有一套数字证书，可以自己制作，也可以向组织申请，区别就是自己颁发的证书需要客户端验证通过。这套证书其实就是一对公钥和私钥。
服务器将自己的数字证书（含有公钥）发送给客户端。
客户端收到服务器端的数字证书之后，会对其进行检查，如果不通过，则弹出警告框。如果证书没问题，则生成一个密钥（对称加密），用证书的公钥对它加密。
客户端会发起HTTPS中的第二个HTTP请求，将加密之后的客户端密钥发送给服务器。
服务器接收到客户端发来的密文之后，会用自己的私钥对其进行非对称解密，解密之后得到客户端密钥，然后用客户端密钥对返回数据进行对称加密，这样数据就变成了密文。
服务器将加密后的密文返回给客户端。
客户端收到服务器发返回的密文，用自己的密钥（客户端密钥）对其进行对称解密，得到服务器返回的数据。

8. 聊聊事务隔离级别，以及可重复读实现原理

8.1 数据库四大隔离级别

为了解决并发事务存在的 脏读、不可重复读、幻读 等问题，数据库大叔设计了四种隔离级别。分别是 读未提交，读已提交，可重复读，串行化 （Serializable）。

读未提交隔离级别：只限制了两个数据不能同时修改，但是修改数据的时候，即使事务未提交，都是可以被别的事务读取到的，这级别的事务隔离有脏读、重复读、幻读的问题；
读已提交隔离级别：当前事务只能读取到其他事务提交的数据，所以这种事务的隔离级别解决了脏读问题，但还是会存在重复读、幻读问题；
可重复读：限制了读取数据的时候，不可以进行修改，所以解决了重复读的问题，但是读取范围数据的时候，是可以插入数据，所以还会存在幻读问题；
串行化：事务最高的隔离级别，在该级别下，所有事务都是进行串行化顺序执行的。可以避免脏读、不可重复读与幻读所有并发问题。但是这种事务隔离级别下，事务执行很耗性能。

四大隔离级别，都会存在哪些 并发问题 呢

image.png

8.2 Read View可见性规则

image.png

Read View的 可见性规则 如下：

如果数据事务ID trx_id < min_limit_id ，表明生成该版本的事务在生成 Read View 前，已经提交(因为事务ID是递增的)，所以该版本可以被当前事务访问。
如果 trx_id>= max_limit_id ，表明生成该版本的事务在生成 Read View 后才生成，所以该版本不可以被当前事务访问。
如果 min_limit_id =<trx_id< max_limit_id ,需要分3种情况讨论

m_ids trx_id Read View trx_id creator_trx_id
m_ids trx_id trx_id creator_trx_id Read View
m_ids trx_id Read View

8.3 可重复读实现原理

数据库是通过加锁实现隔离级别的，比如，你想一个人静静，不被别人打扰，你可以把自己关在房子，并在房门上加上一把锁！串行化隔离级别就是加锁实现的。但是如果频繁加锁，性能会下降。因此设计数据库的大叔想到了 MVCC 。

可重复读的实现原理就是 MVCC多版本并发控制 。在一个事务范围内，两个相同的查询，读取同一条记录，却返回了不同的数据，这就是 不可重复读 。可重复读隔离级别，就是为了解决 不可重复读 问题。

查询一条记录，基于 MVCC ，是怎样的流程呢？

获取事务自己的版本号，即事务ID
获取Read View
查询得到的数据，然后Read View中的事务版本号进行比较。
如果不符合Read View的可见性规则，即就需要Undo log中历史快照;
最后返回符合规则的数据

InnoDB 实现 MVCC ，是通过 Read View+ Undo Log 实现的， Undo Log 保存了历史快照， Read View 可见性规则帮助判断当前版本的数据是否可见。

可重复读（RR）隔离级别，是如何解决不可重复读问题的？

假设存在事务A和B，SQL执行流程如下

image.png

在可重复读（RR）隔离级别下，一个事务里只会获取一次 read view ，都是副本共用的，从而保证每次查询的数据都是一样的。

假设当前有一张core_user表，插入一条初始化数据,如下：

image.png

基于MVCC，我们来看看执行流程

A开启事务，首先得到一个事务ID为100
B开启事务，得到事务ID为101
事务A生成一个Read View，read view对应的值如下

image.png

然后回到版本链：开始从版本链中挑选可见的记录：

image.png

由图可以看出，最新版本的列name的内容是孙权，该版本的trx_id值为100。开始执行 read view可见性规则 校验：

min_limit_id(100)=<trx_id（100）<102;
creator_trx_id = trx_id =100;

由此可得，trx_id=100的这个记录，当前事务是可见的。所以查到是 name为孙权 的记录。

事务B进行修改操作，把名字改为曹操。把原数据拷贝到undo log,然后对数据进行修改，标记事务ID和上一个数据版本在undo log的地址。

image.png

事务B提交事务
事务A再次执行查询操作，因为是RR（可重复读）隔离级别，因此会复用老的Read View副本，Read View对应的值如下

image.png

然后再次回到版本链：从版本链中挑选可见的记录：

image.png

从图可得，最新版本的列name的内容是曹操，该版本的trx_id值为101。开始执行read view可见性规则校验：

min_limit_id(100)=<trx_id（101）<max_limit_id（102);
因为m_ids{100,101}包含trx_id（101），
并且creator_trx_id (100) 不等于trx_id（101）

所以， trx_id=101 这个记录，对于当前事务是不可见的。这时候呢，版本链 roll_pointer 跳到下一个版本， trx_id=100 这个记录，再次校验是否可见：

虾皮面试经历：惨遭面试官吊打

实例1：

实例2：

2.对称与非对称加密算法的区别

3. TCP如何保证可靠性

4. 聊聊五种IO模型

4.1 阻塞IO 模型

4.2 非阻塞IO模型

4.3 IO多路复用模型

IO多路复用之select

IO多路复用之epoll

4.4 IO模型之信号驱动模型

4.5 IO 模型之异步IO(AIO)

5. hystrix 工作原理

6. 延时场景处理

7.https请求过程

8. 聊聊事务隔离级别，以及可重复读实现原理

8.1 数据库四大隔离级别

8.2 Read View可见性规则

8.3 可重复读实现原理