09-26 14:51 已编辑南京邮电大学安卓发布于北京

关注

面试八股系列（更新中）

1、TCP？如何实现可靠传输的？

三次握手建立连接：在传输数据之前，TCP使用三次握手（SYN, SYN-ACK, ACK）过程建立一个可靠的连接。这个过程确保了双方都准备好接收和发送数据。
序列号和确认应答：TCP为每个发送的数据包分配一个序列号，并要求接收方对数据进行确认应答（ACK）。接收方通过发送确认应答，告诉发送方哪些数据已经被成功接收。如果发送方在一定时间内没有收到确认应答，它会重新发送数据。
数据校验和：TCP头部包含一个校验和字段，用于检查数据在传输过程中是否出现错误。如果接收到的数据包校验和不正确，TCP将丢弃该数据包并等待重传。
流量控制：TCP使用滑动窗口机制进行流量控制，确保发送方不会因为发送数据过快而淹没接收方。窗口大小可以动态调整，以匹配接收方的处理能力。
拥塞控制：TCP还实现了几种拥塞控制算法（如慢启动、拥塞避免、快速重传和快速恢复），以避免网络拥塞。这些算法通过动态调整数据的发送速率来响应网络条件的变化。
有序数据传输：TCP保证数据按照发送顺序到达接收方。如果数据包到达顺序不正确，TCP会重新排序，确保应用层接收到有序的数据流。
连接终止：TCP使用四次挥手过程来终止一个连接。这个过程确保了双方都完成了数据的发送和接收。

2、 HTTPS加密

HTTPS加密是通过SSL（安全套接层）或TLS（传输层安全）协议来实现的，这两种协议为网站的安全通信提供了加密和身份验证。整个过程大致可以分为以下几个步骤：

1. 握手阶段

客户端向服务器发送握手请求：这个请求包括客户端支持的加密方法（密码套件）、一个客户端生成的随机数（Client Random），以及其他会话参数。
服务器响应：服务器选择一个客户端也支持的加密方法，并发送给客户端。同时，服务器也会发送一个服务器生成的随机数（Server Random）和服务器的证书（包含公钥）。
验证服务器证书：客户端验证服务器的证书（通常是通过证书颁发机构CA）。这一步是为了确认服务器的身份，防止中间人攻击。
预主密钥生成：客户端生成一个预主密钥（Pre-Master Secret），并使用服务器的公钥加密这个预主密钥，然后发送给服务器。只有拥有对应私钥的服务器才能解密获得预主密钥。
会话密钥生成：客户端和服务器分别使用Client Random、Server Random和Pre-Master Secret，通过特定的算法生成会话密钥（Session Keys），这些密钥将用于后续的通信加密。

2. 加密通信

一旦握手完成，客户端和服务器就会使用会话密钥对数据进行加密和解密。这确保了数据的机密性和完整性。加密过程如下：
客户端加密：客户端使用会话密钥对数据进行加密，然后将加密的数据发送给服务器。
服务器解密：服务器接收到加密的数据后，使用会话密钥对数据进行解密，获取原始数据。
服务器响应加密：服务器将响应数据加密后发送给客户端。
客户端解密：客户端使用会话密钥解密服务器的响应，获取数据。

3. 结束会话

当通信结束时，客户端和服务器会发送消息来关闭安全连接，并丢弃会话密钥，确保会话结束后数据不会被解密。

3、 TCP窗口控制

TCP窗口控制是一种关键的流量控制机制，用于确保网络中的数据传输既高效又可靠。它主要通过调整发送方的发送窗口大小来实现，以此来控制发送方的数据发送速率，防止接收方的缓冲区溢出，并确保网络不会因为过载而导致拥塞。下面是窗口控制的详细分析：

1. 发送窗口和接收窗口

发送窗口：发送方根据接收方的能力和网络条件动态调整的发送数据的最大量。发送窗口的大小决定了发送方可以发送但未被确认的数据量。
接收窗口：接收方告知发送方它的缓冲区还能接收多少数据，这个值通过TCP报文段的窗口字段告知发送方。

2. 窗口大小的调整

窗口的大小是动态调整的，主要基于以下几个因素：
接收方的缓冲区大小：接收方根据自己的处理能力和缓冲区的剩余空间，动态调整接收窗口的大小，并通过确认报文（ACK）告知发送方。
网络拥塞情况：发送方还需要根据网络的拥塞情况来调整发送窗口的大小，以避免因为网络拥塞导致的数据丢失和重传。

3. 流量控制的实现

当接收方处理数据的速度低于发送方发送数据的速度时，接收方的缓冲区可能会被填满。为了防止缓冲区溢出，接收方会通过减小TCP报文段中的窗口字段值来减小发送方的发送窗口，从而降低发送方的发送速率。
当接收方的缓冲区有足够的空间时，它会增加窗口字段的值，允许发送方增加发送速率。

4. 零窗口问题

如果接收方的缓冲区被完全填满，它会通知发送方窗口大小为零，这会导致发送方停止发送数据。
为了解决这个问题，TCP实现了零窗口探测机制。当发送方收到零窗口通知时，它会定期发送一个特殊的TCP报文段（零窗口探测报文）给接收方，以探测接收方窗口是否已经有可用空间。

4、三次握手、四次挥手

三次握手

1）第一次握手：建立连接时，客户端向服务器发送SYN包（seq=x），请求建立连接，等待确认
2）第二次握手：服务端收到客户端的SYN包，回一个ACK包（ACK=x+1）确认收到，同时发送一个SYN包（seq=y）给客户端
3）第三次握手：客户端收到SYN+ACK包，再回一个ACK包（ACK=y+1）告诉服务端已经收到
4）三次握手完成，成功建立连接，开始传输数据

四次挥手

1）客户端发送FIN包（FIN=1）给服务端，告诉它自己的数据已经发送完毕，请求终止连接，此时客户端不发送数据，但还能接收数据
2）服务端收到FIN包，回一个ACK包给客户端告诉它已经收到包了，此时还没有断开socket连接，而是等待剩下的数据传输完毕
3）服务端等待数据传输完毕后，向客户端发送FIN包，表明可以断开连接
4）客户端收到后，回一个ACK包表明确认收到，等待一段时间，确保服务端不再有数据发过来，然后彻底断开连接

5、进程和线程（常考）

1. 定义

进程：是操作系统中资源分配的基本单位，是一个正在执行的程序的实例。每个进程都有自己的地址空间、数据栈和其他辅助数据。
线程：是进程中的一个执行单元，是程序执行的最小单位。一个进程可以包含多个线程，这些线程共享进程的资源。

2. 资源分配

进程：每个进程都有独立的内存空间和资源，进程之间的通信相对复杂，通常需要使用进程间通信（IPC）机制，如管道、消息队列等。
线程：同一进程中的线程共享进程的内存和资源，因此线程间的通信相对简单，可以直接访问共享数据。

3. 创建和销毁

进程：创建和销毁进程的开销较大，因为需要分配和回收独立的资源。
线程：创建和销毁线程的开销较小，因为线程共享进程的资源。

4. 调度

进程：进程的调度相对复杂，操作系统需要管理多个进程的状态和资源。
线程：线程的调度相对简单，线程的切换速度比进程快。

5. 可靠性

进程：由于进程之间相互独立，一个进程的崩溃不会影响其他进程。
线程：同一进程中的线程相互依赖，一个线程的崩溃可能导致整个进程的崩溃。

6. 使用场景

进程：适合需要高隔离性和独立性的应用，如服务器应用。
线程：适合需要高并发和共享资源的应用，如多线程下载、图形界面等。

6、说说什么是大端小端，如何判断大端小端？

小端模式：低的有效字节存储在低的存储器地址。小端一般为主机字节序；常用的X86结构是小端模式。很多的ARM，DSP都为小端模式。
大端模式：高的有效字节存储在低的存储器地址。大端为网络字节序；KEIL C51则为大端模式。
有些ARM处理器还可以由硬件来选择是大端模式还是小端模式。

int fun1(){  
    union test{   
        char c;   
        int i; 
    };  
    test t; t.i = 1;  
    //如果是大端，则t.c为0x00，则t.c != 1，反之是小端  
    return (t.c == 1);  
}

7、`brk` 和`mmap` 实现原理

`（1）、brk` 实现原理

brk 和 sbrk 系统调用用于调整进程的数据段（heap）的大小。它们通过改变进程的“程序断点”（program break）来实现内存分配和释放。

程序断点：程序断点是进程地址空间中数据段的末尾。通过调整程序断点的位置，可以增加或减少数据段的大小。
brk：brk 系统调用直接设置程序断点的位置。
sbrk：sbrk 系统调用通过增加或减少程序断点的位置来调整数据段的大小。

实现原理：

初始化：当进程启动时，操作系统会为其分配一个初始的堆空间，并设置初始的程序断点。
内存分配：当进程需要更多的堆内存时，可以调用 brk 或 sbrk 来增加程序断点的位置，从而扩大堆空间。
内存释放：当进程不再需要某些堆内存时，可以调用 brk 或 sbrk 来减少程序断点的位置，从而释放堆空间。

优缺点：

优点：brk 和 sbrk 实现简单，适用于小规模的内存分配。
缺点：堆空间必须是连续的，无法处理大规模的、非连续的内存分配需求。

`（2）、mmap` 实现原理

mmap 系统调用用于将文件或设备映射到进程的地址空间，或者直接分配匿名内存（不与文件关联）。

文件映射：将文件的内容映射到进程的地址空间，使得文件内容可以像内存一样被访问。
匿名映射：分配一块内存，不与任何文件关联，通常用于大规模的内存分配。

实现原理：

文件映射：调用 mmap 时，操作系统会在进程的地址空间中找到一块合适的虚拟内存区域，并将该区域与文件的内容关联。访问该内存区域时，操作系统会将相应的文件内容加载到内存中。
匿名映射：调用 mmap 时，操作系统会在进程的地址空间中找到一块合适的虚拟内存区域，并分配实际的物理内存。该内存区域不与任何文件关联，可以用于大规模的内存分配。

优缺点：

优点：mmap 支持大规模的、非连续的内存分配，适用于内存映射文件和共享内存。
缺点：实现相对复杂，可能涉及页表管理和文件系统操作。

8、MySQL中，有一个超级大表，如何优化分页查询？

9、Innodb数据结构

1. B+树（B+ Tree）

B+树是 InnoDB 用于存储表和索引的主要数据结构。B+树是一种平衡树，具有以下特点：

所有叶子节点在同一层：这保证了所有数据的访问路径长度相同，从而提高了查询效率。
叶子节点存储实际数据：非叶子节点只存储键值和指向子节点的指针。
顺序访问：叶子节点通过链表连接，支持顺序访问。

用途

聚簇索引（Clustered Index）：每个 InnoDB 表都有一个聚簇索引，表的数据存储在聚簇索引的叶子节点中。主键是聚簇索引的键。
辅助索引（Secondary Index）：辅助索引的叶子节点存储索引键和对应的主键值。通过辅助索引查找数据时，需要先通过辅助索引找到主键值，再通过聚簇索引找到实际数据。

2. 页（Page）和区（Extent）

InnoDB 将数据存储在页（Page）和区（Extent）中。

页（Page）：InnoDB 的基本存储单位，每页大小为 16KB。页用于存储表数据、索引、Undo 日志等。
区（Extent）：区是由连续的 64 个页组成的存储单元，每区大小为 1MB。InnoDB 以区为单位进行空间分配。

3. Redo 日志

Redo 日志用于记录事务的修改操作，以便在系统崩溃后进行恢复。Redo 日志是顺序写入的，具有以下特点：

循环写入：Redo 日志文件是循环使用的，当写满时会从头开始覆盖旧的日志。
日志缓冲区：事务的修改操作首先记录在内存中的日志缓冲区，然后周期性地刷新到磁盘上的 Redo 日志文件。

4. Undo 日志

Undo 日志用于支持事务的回滚和多版本并发控制（MVCC）。Undo 日志记录了事务修改前的数据，以便在事务回滚时恢复数据。

回滚段（Rollback Segment）：Undo 日志存储在回滚段中，每个回滚段包含多个 Undo 日志页。
多版本并发控制（MVCC）：通过保存旧版本的数据，支持一致性读和快照隔离。

5. 自适应哈希索引（Adaptive Hash Index）

InnoDB 会自动监测 B+树索引的访问模式，并在热点数据上创建哈希索引，以提高查询性能。自适应哈希索引是动态创建和维护的，不需要用户干预。

6. 双写缓冲（Doublewrite Buffer）

双写缓冲用于防止部分页写入导致的数据损坏。写入数据页时，InnoDB 会先将页写入双写缓冲区，然后再写入实际的数据文件。这样可以确保即使在写入过程中发生崩溃，也能通过双写缓冲区恢复数据。

7. 插入缓冲（Insert Buffer）

插入缓冲用于优化辅助索引的插入操作。对于非唯一索引的插入操作，InnoDB 会先将其记录在插入缓冲区中，然后批量合并到辅助索引中，从而减少磁盘 I/O。

8. 锁（Locks）

InnoDB 支持多种锁机制来保证数据的一致性和并发性：

行锁（Row Lock）：InnoDB 主要使用行级锁来实现高并发性。
间隙锁（Gap Lock）：用于防止幻读，锁定一个范围内的所有可能插入的位置。
意向锁（Intention Lock）：用于表级锁和行级锁之间的协调。

10、设计线程池需要考虑什么

线程数量：确定线程池中线程的数量，通常需要根据系统的硬件资源（如CPU核心数）和任务的性质来决定。
任务队列：选择合适的任务队列类型（如有界队列或无界队列），以便有效管理待处理的任务。
任务调度：设计任务的调度策略，包括任务的优先级、执行顺序等。
线程生命周期管理：管理线程的创建、销毁和复用，避免频繁创建和销毁线程带来的性能损耗。
异常处理：设计异常处理机制，确保线程在执行任务时出现异常时能够安全地处理。
资源管理：合理管理线程池中的资源，避免资源泄漏和竞争。
监控与统计：实现对线程池的监控和统计功能，以便及时发现和解决性能瓶颈。
扩展性：设计时考虑到未来可能的扩展需求，确保线程池能够适应不同的负载情况。
配置参数：提供灵活的配置选项，让用户能够根据具体需求调整线程池的行为。

11、如何在数组头部插入元素

可以使用一个动态数组来存储数据，并维护一个指向“头部”的索引。当在头部插入元素时，你可以将头索引向前移动，并在新的头部位置插入元素。如果数组有足够的预留空间，这种方法可以较高效地工作。但是，这种方法需要手动管理数组的容量和头索引，以及可能的数组元素移动。

#include <iostream>
#include <vector>

class CircularArray {
public:
    CircularArray(int capacity) : capacity(capacity), head(0), size(0) {
        array.resize(capacity);
    }

    void insertAtFront(int value) {
        if (size >= capacity) {
            throw std::runtime_error("Array is full");
        }
        // 计算新的头部位置
        head = (head - 1 + capacity) % capacity;
        array[head] = value;
        ++size;
    }

    void display() const {
        for (int i = 0; i < size; ++i) {
            std::cout << array[(head + i) % capacity] << " ";
        }
        std::cout << std::endl;
    }

private:
    std::vector<int> array;
    int capacity;
    int head;
    int size;
};

int main() {
    CircularArray circularArray(5);
    circularArray.insertAtFront(1);
    circularArray.insertAtFront(2);
    circularArray.insertAtFront(3);

    circularArray.display(); // 应该输出: 3 2 1

    return 0;
}
/*
在插入第一个元素1时，我们需要理解head索引是如何计算的。初始时，head的值设定为0，表示数组的起始位置。当我们插入第一个元素时，按照循环数组的逻辑，我们希望1被插入到数组的“逻辑头部”，这意味着我们需要更新head的值，使其指向新的头部位置。

在插入操作中，head的更新公式为：

head = (head - 1 + capacity) % capacity;
这个公式确保了head的值在插入元素后仍然有效，并且能够正确地处理循环的情况。具体到插入第一个元素1的情况：

初始时，head = 0，capacity是数组的容量，假设为5。
插入第一个元素时，我们计算新的head值：head = (0 - 1 + 5) % 5 = 4。
因此，head更新为4，我们将元素1插入到数组的索引4的位置。
这个计算过程使得head始终指向数组中的“逻辑头部”，即使在物理上元素被插入到数组的末尾。通过这种方式，我们可以在数组的头部高效地插入新元素，同时保持数组其他元素的顺序不变。*/

12、拥塞控制

1、慢启动（Slow Start）

目的：在连接开始时快速找到网络的带宽容量。
机制：慢启动阶段，拥塞窗口（cwnd）从1个MSS（最大段大小）开始，每收到一个ACK，cwnd增加1个MSS。这意味着每个RTT（往返时间），cwnd翻倍，呈指数增长。
阈值：当cwnd达到一个阈值（ssthresh）时，TCP转入拥塞避免阶段。

2、拥塞避免（Congestion Avoidance）

目的：避免网络拥塞，通过控制数据的发送速率来维持网络的稳定性。
机制：在这个阶段，每个RTT成功传输后，cwnd仅增加1个MSS的量，导致cwnd线性增长，而不是慢启动阶段的指数增长。
条件：只要网络没有出现拥塞，就会继续保持这种增长模式。

3. 快速重传（Fast Retransmit）

触发条件：当发送方收到三个重复的ACK时，它推断一个段已经丢失，并立即重传丢失的段，而不是等待重传计时器到期。
目的：快速恢复丢失的数据包，减少等待时间。

4. 快速恢复（Fast Recovery）

机制：在快速重传后，TCP进入快速恢复阶段。在这个阶段，TCP将ssthresh设置为当前cwnd的一半，并将cwnd设置为ssthresh加上3个MSS的大小，然后开始线性增长，直到收到新的ACK。
结束条件：当收到新的ACK时，TCP退出快速恢复阶段，将cwnd设置为ssthresh的值，重新进入拥塞避免阶段。

13、分页机制

内存碎片问题：在动态分配内存时，可能会出现外部碎片，即内存中存在许多小的空闲块，无法满足大块内存的请求。分页机制通过将内存划分为固定大小的页，避免了外部碎片的产生。
虚拟内存的实现：分页机制使得虚拟内存的实现成为可能。程序可以使用比物理内存更大的地址空间，操作系统可以将不常用的页换出到磁盘，从而有效利用内存。
简化内存管理：分页机制简化了内存分配和回收的过程。由于页的大小是固定的，内存管理变得更加高效和简单。
提高内存利用率：通过将物理内存和虚拟内存结合，操作系统可以更灵活地管理内存，提高内存的利用率。
保护和隔离：分页机制可以为每个进程提供独立的虚拟地址空间，增强了进程之间的隔离和安全性，防止一个进程访问另一个进程的内存。