今日打卡！面经八股整理！

今天跟着小林coding还有一些文章把一些上周二面pcg面经的一些题搞懂了，借此机会通过写些文章来给自己打个卡！也借此机会能够加深记忆！这篇文章应该会持续更新，因为还有蛮多没弄完

计算机缓存机制的理解

（一开始没想出来，想拿数据库的缓存机制举下例子，后来想起来，是指CPU - 内存 - 硬盘，只简单达到访问缓存读写速度快这样，具体缓存机制，没有提到）

要点：

缓存的原理就是在高速存储介质当中暂时存储常用的数据，以便更快地满足后续的访问请求（为什么利用缓存就能更快提高访问效率？ 局部性原理）。具体缓存机制（缓存映射策略）。

什么是缓存？

局部性原理确保了缓存能够提高数据访问效率

局部性原理：

• 时间局部性：当前使用的指令和数据会在不久的将来还会被使用到
• 空间局部性：一个元素的周围的元素可能接下来会被访问到

在一个简单的处理器缓存模型中，CPU通过一个特定的地址（Address）去访问内存，内存响应请求将数据进行返回

但是，存储器如果容量越大，速度就会越慢。为了处理CPU和缓存之间的这种差异，我们引入了缓存（Cache），缓存依据局部性原理来存储一些数据

缓存命中（Cache Hit）：当处理器请求的数据恰好在缓存中时，缓存可以快速地将数据返回给CPU。

缓存丢失（Cache Miss）：当存储的数据不在缓存中，CPU还是得去内存里面拿取数据。

块的概念？

以64字节的内存为例

按字节Byte编址：

1个格子（Grid）为一个字节（Byte）

需要6位二进制来访问这64个格子

按字Word编址：

1字（Word）= 4字节（Byte）= 4个格子（Grid）= 1行（Line）

需要4位二进制来访问这16行

我们让一个块（Block）= 1字（Word） = 1行（Line）

一个内存行（Memory Line）= 1块（Block）

四行的缓存模型：

1缓存行（Cache Line） = 1块（Block），因此一个内存块就可以放入缓存中的任意一行

缓存映射策略？

内存64B的模型，我们现在让1个块等于两个字，所以也等于两个内存行（Memory Line）

如果按照字编址，在我们定义了内存块和缓存块的基础上，我们可以将编址的4位二进制进行区分

• 偏移量（Offset）：对于缓存中的一块，其中包含了两个字（一块=两字=两行），为了定位数据在一块中的哪一行，我们使用一位二进制来表示，叫做偏移量
• 索引（Index）：为了定位数据在缓存中的哪一块，一共四块，所以需要2位二进制，叫做索引
• 标记（Tag）：当内存里的数据（8块）映射到缓存（4块）的时候，必定会有两块被映射到相同的内存行当中，为了区分，才有了标记。

这里就出现问题了，如果有不止两个被映射到同一个缓存块，那要怎么处理

直接映射

每4个内存块映射到同一个缓存行，这样就保证每一个内存块只存入了两个缓存块

• 优点：硬件设计简单，查询速度很快（只需要通过索引）
• 缺点：冲突概率高（因为对应的内存块只有固定的位置可以存放）

全相联映射

一个内存可以放入任意的缓存行，此时，对于内存地址我们就不需要索引来区分内存块必须放在缓存中的哪个固定位置了

优点：冲突少（内存块可以映射到缓存的不同位置）

缺点：查询速度特别慢，硬件设计复杂（每次我都要计算内存块放到哪一个缓存块去了）

组相连映射

• 组中有一个块：1路组相连
• 组中有两个块：2路组相连

以2路组相联为例，我们可以通过1位的组索引来访问这两个组，此时标记位2位，那么一个组里面可以放入四个内存块。

• 一个内存块可以放入组中的任意一个内存块（全相联）
• 每个内存块都指定放入对应的组内（组索引）【直接相联】

这样，就很好平衡了冲突发生的频率，查询速度和硬件设计复杂度

缓存的结构？

• 内存

包含存储空间和地址，一个地址就对应一个存储空间

• 缓存

同样具有存储空间，但是还有控制信息

• 有效位（V）：标记该行数据是否有效
• 脏数据（D）：CPU多级缓存写入机制那里会讲到

一行被称为一个槽（slot）

CPU里面的多级缓存

要点：

三级缓存（L1,L2,L3），这三个缓存运作的顺序（L1 L2 L3）这三个内存在CPU的位置（L1,L2每个核心独有，L3多核心共享，从L1到L3离CPU核心越来越远，存储器大小越来越大），CPU缓存写入策略（写直达，写回），写回如何保证缓存一致性？（写传播，事务的串行化），写传播的具体实现（总线嗅探），基于总线嗅探实现的协议MESI

存储器的存储结构

寄存器（大脑所想/处理）

最靠近CPU的CPU的控制单元和逻辑计算单元，就是寄存器

寄存器的访问速度特别快，一般要求在半个CPU时钟周期内完成读写，CPU时钟周期跟CPU主频息息相关，比如 2 GHz主频的CPU，那么他的时钟周期就是 1/2G，也就是0.5ns（纳秒）

CPU处理一条指令的时候，除了读写寄存器，还需要解码指令、控制指令执行和计算。

CPU Cache（短期记忆&长期记忆）

CPU Cache使用的是SRAM（Static Random-Access Memory，静态随机存储器）

SRAM「静态」的原因是因为，数据只能在有电的情况下保存，断电数据就会丢失

SRAM的访问速度非常快，这取决于其电路的简单

CPU的高速缓存通常可以分为L1，L2，L3这样的三层高速缓存

每块CPU核心都有属于自己的L1 Cache，L1高速缓存通常分成指令缓存和数据缓存

从L1到L3，位置相距于CPU越来越远，容量越来越大，访问速度越来越慢（再慢也比访问内存快的），成本价格越来越低

内存

内存使用的是DRAM（Dynamic Random Access Memory）芯片

DRAM「动态」的原因是因为电容会漏电，所以需要定时刷新电容，才能保存数据

SSD/HDD硬盘

固态硬盘和机械硬盘

总结

存储空间越大的存储器设备，其访问速度越慢，所需成本越低

存储器每一层的设备只会跟相邻的设备联系

比如，CPU Cache 的数据是从内存加载过来的，写回数据的时候也只写回到内存，CPU Cache 不会直接把数据写到硬盘，也不会直接从硬盘加载数据，而是先加载到内存，再从内存加载到 CPU Cache 中。

CPU的多级缓存机制

当CPU需要访问内存中的某个数据，需要经过寄存器，L1 Cache，L2 Cache，L3 Cache，内存这几个存储器。根据顺序搜索如果在其中的某一层找到了数据，就直接返回数据给CPU

其中，L1，L2是每一个CPU核心独有的，而L3是多个CPU核心共享的

CPU缓存一致性

CPU在什么时机才会把Cache中的数据写回到内存呢？

写直达

将数据直接同时写入内存和Cache中，被叫做写直达（Write Through）

缺点：因为每次写操作都会把数据写入内存中，会消耗大量的时间，对性能会造成很大的影响

写回

当发生写操作时，新的数据只会被写回Cache Block中，只有当发现Cache Block中的数据为脏的（Dirty）才会把数据写回内存

意思就是，当这个数据A不在Cache，并发现Cache Block发现这个数据被「其他数据B」占用了（该数据被标记为脏），我们就把数据B写回内存，并从内存把数据A更新到Cache Block，同时也标记为脏（?这里有点不太懂）

这样减少了写入内存的次数（我让别的数据帮我把新的数据放入内存，反正查询的时候命中缓存返回的也是新数据）

缓存一致性问题

我们上述讲的写入内存的机制都是在单核的情况下考虑的，但如果是多核，因为写回不直接写入内存的特性，可能另外的核心读到的就是没有更新的情况下的。这种情况下要怎么解决呢？

写传播

当某个CPU核心里的Cache数据更新，必须传播到其他核心Cache

事务的串行化

某个CPU核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的

• CPU核心对于Cache中的数据，必须同步到其他CPU核心
• 要引入「锁」的概念，如果两个CPU核心里有相同的数据Cache，那么对于这个Cache数据更新，只有拿到了「锁」才能对对应数据进行更新

总线嗅探

比如核心A修改了L1 Cache中变量i的值，然后我们通过总线将这个事件广播给其他所有的核心，其他核心会监听总线上的广播事件，并检查是否有相同的数据在自己的L1 Cache中，如果其他核心有这个数据，就会更新数据

缺点：每次更新数据都要进行广播，会加重总线的负载

MESI协议

• Modified，已修改
• Exclusive，独占
• Shared，共享
• Invalidated，已失效

我们利用这四个状态来标记Cache Line四个不同的状态

**「已修改」**状态就是所谓的脏标记，表示这个Cache Block上的数据已经被修改过，但是还没写到内存（同「脏」的定义，内存和Cache数据不一致）

**「已失效」**表示这个Cache Block里的数据已经失效，不可再读取该状态的数据

**「独占」和「共享」**都表示Cache Block里的数据是干净的。

• 「独占」：数据只存储在一个CPU核心的Cache当中，其他核心没有这个数据。此时就不会存在缓存一致性的问题
• 「共享」：这个数据在多个CPU的Cache中都存在，此时我们利用**「总线嗅探」**的原理，在修改数据的时候，会通过总线向其他核心广播修改的请求，要求先把其他核心的Cache里面对应的数据修改成「无效」状态，然后再更新当前Cache里面的数据

实例：以两个核心AB先后存储相同的数据i，然后修改A中的数据为例

1. 当CPU A从内存读取i，数据被缓存在CPU A的Cache当中，此时其他CPU核心没有存储这个数据，于是标记Cache Line为「独占」Exclusive，且此时内存和缓存数据一致
2. CPU B也从内存读取i，此时会广播其他的核心，由于A已经缓存这个数据，会把数据返回给B核心。此时，A和B对应的Cache Line存储了相同的数据，Cache Line状态变成「共享」，此时，内存和Cache缓存数据一致
3. A开始修改i的值，因为此时Cache Line为「共享」状态，所以A核心会先广播其他核心修改数据的请求，并将B核心中对应数据的Cache Line的数据置为「无效」，然后A才更改数据，此时，Cache Line的状态为「已修改」
4. 如果，此时A继续修改i的值，此时Cache Line为「已修改」状态，不需要向其他核心广播即可修改数据
5. 如果A中的i对应的Cache Line要被替换，发现此时状态为「已修改」，此时数据为脏，会在替换之前把数据同步到内存（这里就体现了写回机制，当写入新的不在缓存中的数据，且此时对应的Cache Block内的数据为脏，就先把脏数据写入内存，再把新数据进行替换）

缓存淘汰策略

• LRU算法是啥样的？（说了最近最少使用，然后不知道说啥了说了具体实现hashmap+双向链表）
• 其他的缓存淘汰策略？（FIFO，轮询）
• Redis支持哪两种淘汰策略（LRU，LFU）

LFU

Least Frequently Used：最近最不常用算法，根据数据的历史访问频率来淘汰数据

做法：将使用频率最小的数据置换出去。

实现方法：对整个缓存维护一个「程序计数器」，当一个数据被访问的时候，其访问计数器就累加1。当需要淘汰数据的时候，淘汰数据最小的那一个

LRU

Least Recently Used：最近最少使用算法，根据数据的历史访问记录来淘汰数据

实现方法：Hashmap + 双向链表。put数据的时候插入链表尾端，并利用hashMap实现的时间复杂度来访问链表中的节点。当重复数据被访问的时候将其提至链表头部。当缓存满了就淘汰链表尾端的数据

FIFO

First In First Out：先进先出算法，先进的数据最先被淘汰

类似队列

死锁

• 死锁？如何避免？（啊操作系统的东西全忘了，直接红豆泥私密马赛）
• 平时会用到锁吗？（饿汉式单例）

要点：

什么是死锁？死锁发生的条件？如何避免死锁？

死锁发生必须满足四个条件

线程A拿了资源S的锁，线程B拿了资源T的锁，此时A想要拿资源T的数据，B想要拿S的数据，但是B拿着T的锁，A在等B释放；A拿着S的锁，B也在等A释放。

如果没有外力介入，那么这两个线程就会相互等待，程序无法继续运行，陷入了死锁

死锁发生四个条件必须同时满足：

• 互斥

多个线程不能同时使用同一个资源

任意时刻一个资源只能给一个进程使用，如果其他资源想要使用该资源必须得等到资源被释放才能获取

• 拥有并相互等待

线程A在拥有资源1的同时请求资源2，且此时不会释放资源1但是线程B又在等待获取资源1。A请求资源2但是资源2被C拥有（吃完碗里的还看着锅里的）

• 不可剥夺

当线程在使用资源时只能等资源使用完毕才会释放

• 环路等待

死锁发生的时候，两个线程获取资源的顺序构成了环形链

避免死锁？

产生死锁的四个条件为：互斥，拥有并互相等待，不可剥夺，环路等待

那么避免死锁只要破坏其中的一个条件即可，比较常用的是资源有序分配法

资源有序分配法：让两个线程用相同的顺序来申请自己想要的资源

栈和队列

要点

• 数据结构的栈和队列啥区别？
• 一般用在啥场景？举些例子？（栈不记得了，队列说了消息队列）
• 栈和队列经常用的操作？

应用场景

**栈：**语义分析。例如我们进行括号匹配的时候，就可以使用栈来进行匹配

相关题目：

• 括号匹配：左括号入栈，右括号看是否与栈顶括号匹配，匹配就栈顶括号出栈
• 最长有效括号

队列：广泛使用在广度优先搜索中，例如层次遍历一个二叉树的节点值

/**
 * 树相关工具类
 */
public class TreeUtils {
    /**
     * 将数组转化成树
     * @param tree 树的数组
     * @return 一棵树
     */
    public static TreeNode buildTree(int[] tree) {
        TreeNode root = new TreeNode(tree[0]);
        //同样也是利用queue来构建
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        //利用一个下标来维护树的长度
        int index = 1;
        while (!queue.isEmpty() && index < tree.length) {
            TreeNode node = queue.poll();

            if (index < tree.length && tree[index] != -1) {
                node.left = new TreeNode(tree[index]);
                queue.add(node.left);
            }
            index++;
            if (index < tree.length && tree[index] != -1) {
                node.right = new TreeNode(tree[index]);
                queue.add(node.right);
            }
            index++;
        }
        return root;
    }

    /**
     * 层次遍历树并将其输出
     * @return
     */
    public static List<Integer> printTree(TreeNode root) {
        //利用队列
        Deque<TreeNode> queue = new ArrayDeque<>();
        List<Integer> list = new ArrayList<>();

        queue.add(root);



        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            list.add(node.val);
            //用一个boolean值判断是不是叶子节点，如果叶子节点我们就不进行new
            boolean isLeaf = node.left == null && node.right == null;

            if (node.left != null) {
                queue.add(node.left);
            } else if (!isLeaf){
                queue.add(new TreeNode(-1));
            }

            if (node.right != null) {
                queue.add(node.right);
            } else if (!isLeaf){
                queue.add(new TreeNode(-1));
            }

        }
        System.out.println(list);
        return list;
    }

    public static void main(String[] args) {
        printTree(buildTree(new int[]{1, 2, 3, 4, -1, -1, 5}));
    }
}

计网

:star:要点

HTTP和HTTPS区别？HTTP为什么不安全？（明文传输的特点 ）

• Http和Https区别？
• Http没那么安全的例子？（啊？不知道了？随便乱答了个dDos攻击😵‍💫）
• 创建Https的过程有哪些步骤？（八股还没看到这，答不上来）

HTTP和HTTPS区别

• HTTP是超文本传输协议，信息是明文传输，存在安全风险；HTTPS则解决了HTTP不安全的缺陷，在TCP和HTTP网络层之间加入了SSL/TLS安全协议，使得报文能够加密传输
• HTTP连接建立相对简单，TCP三次握手之后就可以进行HTTP报文传输。HTTPS在TCP三次握手之后，还需要进行SSL/TLS的握手过程，才可以加密报文传输
• 默认端口不一样，HTTPS是443，HTTP是80
• HTTPS需要向CA申请数字证书，来保证服务器的身份是可信的

HTTPS解决了HTTP什么问题

HTTP明文传输的特点，所以在安全上会存在以下三个风险

• 窃听风险，比如通信链路上可以获取通信内容
• 篡改风险，比如强制植入垃圾广告
• 冒充风险，比如冒充淘宝网站

HTTPS在HTTP层和TCP层加入了SSL/TLS协议，可以很好的解决上述的风险：

• **信息加密：**交互的信息无法被窃取

  HTTPS通过**混合加密的方式来确保信息的机密性**

• **校验机制：**无法篡改通信内容

  利用**[摘要算法](#摘要算法 + 数字签名)**来实现完整性

• **身份证书：**向CA发送数字证书来证明服务器的身份真实可信

  将服务器的公钥放入**数字证书**当中，解决了冒充的风险

混合加密

HTTPS采用的是对称加密和非对称加密结合的「混合加密」方式

• 在通信建立前采用非对称加密的方式交换「会话秘钥」，后续就不再使用非对称加密（不是说「会话秘钥」是使用非对称加密，只是交换过程使用非对称加密）
• 在通信过程中全部使用对称加密的「会话秘钥」的方式加密明文数据

使用「混合加密」的原因：

• 通信过程使用对称加密，因为只使用一个秘钥，运算速度快，这样就导致秘钥必须保密，无法做到安全的秘钥交换

• 建立连接使用非对称加密，其含有两个秘钥：公钥和私钥，公钥可以随意分发，而私钥保密，解决了秘钥交换问题但是速度慢。通过公钥加密的东西只能通过私钥解开，而通过私钥加密的，可以使用公钥解开。

  • 公钥和私钥的用法：

    1. 公钥加密，私钥解密（用于数据加解密）
    2. 私钥签名，公钥验签（用于身份证明，私钥来证明我的身份）

  • 为什么非对称加密闭对称加密慢？

    • 对称加密主要的运算是位运算，使用机器运算速度会很快

    • 非对称加密运算涉及到大数乘法、大数取模等运算（↩️回忆：Java的HashMap为什么容量是2的幂次 计算桶位置hash % n == hash & (n - 1)）

摘要算法 + 数字签名

我们会根据发送的内容生成一份「指纹」，只有当发送端和接收端收到的「指纹」是一致才能说明内容没有被篡改

计算机通常会使用摘要算法（哈希函数）来计算内容的哈希值，也就是我们所说的「指纹」，这个哈希值是唯一的，且无法通过哈希值推算回原来的内容

虽然哈希算法可以确保内容不会被篡改，但是不能保证「内容 + 哈希值」不会被中间人替换（可能我有个新的内容但是能保证内容 + 哈希值是一致的）

所以我们这里使用非对称加密算法来对内容的hash值来进行加密，这就是我们所说的数字签名

• 「私钥签名，公钥验签」：这样就保证了内容的哈希值不会被其他人替换了

数字证书

上面我们已经解决了发送消息的可靠性（数字签名来确认消息是由持有私钥的一方来发送的）和完整性（对内容利用摘要算法/哈希算法加密），而这些可以归纳为利用了**「混合加密」**的方式

但是我们如何保证这一整套加密方式的可靠性呢？如果公钥和私钥都被伪造了那不就寄了？

这就引入了**「数字证书」**的概念

我们让第三方CA（Certificate Authority）介入

我们将「个人信息 + 公钥 + 数字签名」打包成一个数字证书，由CA来核验这个证书是否是可信的

这个数字签名是由CA来签名确认的

待续...