游卡C++开发一面面经

来源：https://www.nowcoder.com/feed/main/detail/6d05344afb7640e8a445d017c6aa2a0c

1、虚函数怎么实现的？

虚函数允许在基类和派生类中有相同的函数名，根据对象的实际类型调用相应的函数。

在 C++ 中，要将一个成员函数声明为虚函数，需要在基类中将其声明为虚函数，并在派生类中重写该函数。

具体步骤如下：

1. 在基类中声明虚函数：在基类中将要成为虚函数的成员函数声明为虚函数。

class Base {
public:
    virtual void func();  // 声明为虚函数
};

2. 在派生类中重写虚函数：在派生类中重写（override）基类中的虚函数。重写时，函数名、参数列表和返回类型必须与基类中的虚函数相同，并且在函数声明前加上 virtual 关键字（这是为了明确表明该函数是对基类虚函数的重写，不过在派生类中加不加 virtual 都可以，但为了可读性和清晰性，建议加上）。

class Derived : public Base {
public:
    void func() override;  // 重写基类中的虚函数
};

3. 实现虚函数的动态绑定：在运行时，根据对象的实际类型确定调用的是哪个函数。当基类指针指向派生类对象，并调用虚函数时，会根据对象的实际类型调用相应的函数。

Base* ptr = new Derived();
ptr->func();  // 根据对象的实际类型调用 Derived 类中的 func() 函数

2、多重继承和多继承的情况下子类的虚函数表是怎样的？

在 C++ 中，多重继承指的是一个类可以从多个基类继承。在多重继承中，派生类继承了多个基类的成员，包括虚函数。这时候，派生类的虚函数表（vtable）会包含所有基类的虚函数表，并按照继承顺序排列。

给个例子：

#include <iostream>

class A {
public:
    virtual void funcA() { std::cout << "A::funcA()" << std::endl; }
};

class B {
public:
    virtual void funcB() { std::cout << "B::funcB()" << std::endl; }
};

class C : public A, public B {
public:
    void funcC() { std::cout << "C::funcC()" << std::endl; }
};

int main() {
    C c;
    c.funcA();  // 调用 A 中的虚函数
    c.funcB();  // 调用 B 中的虚函数
    return 0;
}

示例中，类 C 多重继承自类 A 和类 B。因此，C 的虚函数表中将包含 A 和 B 的虚函数表。在实际实现中，编译器会根据继承顺序安排虚函数表的内容，以确保正确的虚函数被调用。

在调用 c.funcA() 时，会根据 A 类的虚函数表调用 A::funcA()；在调用 c.funcB() 时，会根据 B 类的虚函数表调用 B::funcB()。

需要注意的是，多重继承会增加代码的复杂性。

3、哈希表怎么实现的？

哈希表（Hash Table）是一种用于存储键值对的数据结构，它通过将键映射到一个确定的索引（哈希值）来实现快速查找。哈希表的实现通常包括以下几个关键步骤：

1. 哈希函数：哈希函数将键映射到哈希表中的索引。良好的哈希函数应该尽可能均匀地分布键，以减少冲突（多个键映射到相同索引）的可能性。常见的哈希函数包括取余法、乘法哈希法、MD5、SHA等。
2. 解决冲突：由于哈希函数的有限性，可能会出现不同键映射到相同索引的情况，即冲突。常见的解决冲突的方法包括：
   • 开放寻址法：当发生冲突时，线性地探查下一个空槽，直到找到空槽或遍历完整个哈希表。
   • 链地址法：在哈希表的每个槽中维护一个链表（或其他数据结构），将哈希值相同的键值对存储在同一个链表中。
3. 动态扩容：为了保持较低的冲突率，当哈希表中的元素数量达到一定阈值时，通常会触发哈希表的动态扩容。扩容的过程包括重新计算哈希值并重新分配键值对到新的哈希表中。
4. 实现细节：在实现哈希表时，需要考虑到一些细节问题，如空槽的处理、哈希表的初始大小、负载因子（即元素数量与表大小的比率）、哈希碰撞的处理等。

示例：

#include <iostream>
#include <unordered_map>

int main() {
    // 创建一个哈希表
    std::unordered_map<std::string, int> hashTable;

    // 插入键值对
    hashTable["apple"] = 10;
    hashTable["banana"] = 20;
    hashTable["orange"] = 30;

    // 查找键的值
    std::cout << "apple: " << hashTable["apple"] << std::endl;

    // 遍历哈希表
    for (const auto& pair : hashTable) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

4、哈希冲突了怎么办？你刚刚提到了再哈希法，那我是怎么判断我这个键对应的值是哪一个？

哈希冲突是指两个不同的键经过哈希函数计算得到相同的哈希值，导致它们应该存储在哈希表中的相同位置。在发生哈希冲突时，需要使用冲突解决方法来确定具体存储位置。

在哈希表中，常见的冲突解决方法有两种：开放寻址法和链地址法。

1. 开放寻址法：当发生冲突时，线性地探查下一个空槽，直到找到空槽或遍历完整个哈希表。具体来说，如果键的哈希值计算得到的位置已经被占用，则依次向后查找，直到找到一个空槽或者遍历完整个哈希表。这个过程叫做线性探查（Linear Probing）。
2. 链地址法：在哈希表的每个槽中维护一个链表（或其他数据结构），将哈希值相同的键值对存储在同一个链表中。当发生冲突时，只需将新的键值对插入到对应槽的链表中即可。

对于开放寻址法，再哈希法是一种解决冲突的策略。在再哈希法中，当发生冲突时，使用一个独立的哈希函数来计算另一个位置，并在那个位置插入键值对。这个过程可以迭代多次，直到找到一个空槽或者遍历完整个哈希表。通常，再哈希法中使用的第二个哈希函数应该与第一个哈希函数有很大不同，以减少冲突的可能性。

对于链地址法，要确定一个键对应的值，首先使用哈希函数计算键的哈希值，然后根据哈希值找到对应槽中的链表，并遍历链表找到键对应的值。链地址法能够处理冲突，但可能会导致链表过长，影响查找效率。

5、介绍一下进程间通信方式？

进程间通信（Inter-Process Communication, IPC）是指在操作系统中，不同进程之间进行数据交换和通信的机制。进程间通信可以用于实现多个进程之间的协作和数据共享。

1. 管道（Pipe）：管道是一种半双工的通信方式，用于具有亲缘关系的进程间通信。它有两种：匿名管道和命名管道。匿名管道通常由父进程创建，并通过fork系统调用传递给子进程。命名管道允许无关的进程之间进行通信。
2. 信号（Signal）：信号是一种比较简单的进程间通信机制，用于通知接收进程发生了某种事件。常见的信号包括SIGINT（中断信号）和SIGTERM（终止信号）等。
3. 消息队列（Message Queue）：消息队列是一种通过消息传递进行通信的方式。发送进程将消息发送到消息队列，接收进程从队列中接收消息。消息队列通常用于实现进程间的异步通信。
4. 共享内存（Shared Memory）：共享内存允许多个进程共享同一块内存区域。这种方式效率高，但需要进程之间进行同步来避免竞态条件。
5. 信号量（Semaphore）：信号量是一种计数器，用于控制对共享资源的访问。它可以用来解决进程间的互斥和同步问题。
6. 套接字（Socket）：套接字是一种通用的进程间通信机制，常用于网络编程中，但也可以用于本地进程间通信。套接字提供了一种双向通信的机制，可以在不同主机或同一主机的不同进程间进行通信。
7. 文件（File）：进程可以通过读写文件来进行通信，但这种方式通常用于非实时通信，因为文件的读写会涉及磁盘IO，速度较慢。

6、你怎么理解死锁的？

死锁是指两个或多个进程互相等待对方持有的资源而无法继续执行的状态。在死锁状态下，每个进程都在等待另一个进程释放资源，导致所有进程都无法继续执行。死锁是多进程系统中常见的问题，也是一种严重的系统故障。

死锁发生的四个必要条件：

1. 互斥条件：进程对资源的访问是互斥的，即一次只能有一个进程占用资源。
2. 请求和保持条件：进程可以在持有某个资源的同时请求其他资源。
3. 不可剥夺条件：进程已经获得的资源不能被强制性地剥夺，只能在使用完之后自愿释放。
4. 循环等待条件：存在一组进程，每个进程都在等待下一个进程所持有的资源。

当这四个条件同时满足时，就可能发生死锁。为了避免死锁，可以采取以下策略：

• 破坏互斥条件：允许多个进程同时访问资源，或者引入虚拟资源来代替实际资源。
• 破坏请求和保持条件：要求进程在请求资源时一次性获取所有需要的资源，或者引入资源预分配策略。
• 破坏不可剥夺条件：允许操作系统强制剥夺进程已经获得的资源。
• 破坏循环等待条件：对系统中的资源进行全局排序，要求所有进程按照顺序请求资源。

7、TCP和UDP的区别是什么？为什么UDP适用于实时性更高的场景而TCP不适合呢？

1. 可靠性：
   • TCP：TCP 提供可靠的数据传输，通过使用序号、确认和重传机制来确保数据的可靠性和顺序性。如果数据包丢失或损坏，TCP 将重新发送数据包，直到对方确认接收到为止。
   • UDP：UDP 不提供可靠性，数据包的传输是不可靠的。UDP 发送数据后不会等待确认，也不会重传丢失的数据包。
2. 连接性：
   • TCP：TCP 是面向连接的协议，通信双方在传输数据之前需要先建立连接，然后再传输数据，传输结束后关闭连接。
   • UDP：UDP 是无连接的协议，发送数据时不需要先建立连接，直接发送数据包。因此，UDP 的开销更小，传输速度更快。
3. 数据量：
   • TCP：TCP 适用于大量数据传输，可以确保数据的完整性和顺序性，适合要求可靠传输的应用场景，如文件传输、网页访问等。
   • UDP：UDP 适用于少量数据的传输，适合对实时性要求较高的应用场景，如实时视频、语音通话等。
4. 实时性：
   • TCP：由于 TCP 的可靠性机制，数据传输时会有较大的延迟，不适合要求实时性较高的应用场景。
   • UDP：UDP 不保证数据的可靠性和顺序性，但传输速度快，适合要求实时性较高的应用场景。

8、TCP是怎么保证报文一定能到达对方的？

1. 序号和确认：TCP 使用序号和确认来保证数据的可靠传输。发送方将每个发送的数据包标记上一个序号，并等待接收方发送确认消息。接收方收到数据后，会发送确认消息给发送方，告诉发送方已经收到了哪些数据。如果发送方在一定时间内没有收到确认消息，就会重新发送数据包。
2. 超时重传：如果发送方在一定时间内没有收到确认消息，就会认为数据包丢失，会重新发送数据包。发送方会根据网络情况动态调整超时时间，以适应不同的网络环境。
3. 流量控制：TCP 使用滑动窗口机制来进行流量控制。接收方可以告诉发送方自己的接收窗口大小，发送方根据接收窗口大小来控制发送的数据量，避免发送速度过快导致数据丢失或网络拥塞。
4. 拥塞控制：TCP 使用拥塞控制算法来避免网络拥塞。当网络拥塞时，发送方会减小发送速率，以减少网络负载，从而保证数据能够稳定传输。
5. 有限状态机：TCP 使用有限状态机来管理连接的建立、数据传输和连接的释放等过程，确保数据按照正确的顺序传输，避免数据重复或丢失。

9、从安全性角度来讲TCP和UDP有区别吗？如果我希望网络上通信更安全，我应该用TCP还是UDP？

1. 连接性：
   • TCP 是面向连接的，通信双方在传输数据之前需要建立连接，因此可以通过连接建立过程中的身份验证来确保通信双方的身份。
   • UDP 是无连接的，发送数据时不需要建立连接，因此缺乏连接建立过程中的身份验证，容易受到欺骗和攻击。
2. 可靠性：
   • TCP 提供可靠的数据传输，通过序号、确认和重传机制来确保数据的可靠性。然而，TCP 的重传机制也可能导致拒绝服务（DoS）攻击，攻击者可以发送大量伪造的连接请求来耗尽服务器资源。
   • UDP 不提供可靠性，数据包的传输是不可靠的，因此容易受到数据包丢失或篡改的影响。
3. 安全性：
   • TCP 提供了一定程度的安全性，包括连接建立时的身份验证和数据传输过程中的加密（如果使用了 TLS/SSL 等协议）。
   • UDP 的安全性相对较低，因为缺乏连接建立过程中的身份验证和数据传输过程中的加密。

如果希望网络上的通信更安全，一般建议使用 TCP，并且在 TCP 上加上安全性更高的协议，如 TLS/SSL，以确保数据的机密性和完整性。对于需要实时性较高但安全性要求不那么严格的应用，可以考虑使用 UDP，并在应用层实现自己的安全机制。

10、get和post的区别你知道吗？

1. GET请求：
   • 使用场景：一般用于向服务器请求数据，比如浏览网页、发送搜索关键词等。
   • 数据传输：数据通过URL的查询字符串传输，数据量较小，一般在2KB左右。
   • 安全性：因为数据在URL中可见，不适合传输敏感信息，如密码等。
2. POST请求：
   • 使用场景：用于向服务器提交数据，比如提交表单、上传文件等。
   • 数据传输：数据通过请求体传输，可以传输大量数据，理论上没有大小限制。
   • 安全性：相比GET请求，POST请求传输的数据不会在URL中暴露，适合传输敏感信息。
3. 其他区别：
   • 缓存：GET请求可被浏览器缓存，POST请求不会缓存，每次都会重新请求。
   • 重复提交：由于GET请求在URL中包含数据，刷新页面时会重新发送请求，容易导致重复提交。POST请求则需要用户确认后才会提交，不易重复提交。

GET请求适用于请求数据，且数据量较小且不敏感；而POST请求适用于提交数据，且数据量较大或敏感。

11、HTTPS的TLS握手过程？

TLS（Transport Layer Security）是一种加密通信协议，用于在两个通信应用程序之间提供保密性和数据完整性。HTTPS就是在HTTP的基础上使用了TLS来加密通信内容，保护数据安全。

TLS握手过程如下：

1. 客户端发送支持的加密算法列表和随机数给服务器：客户端发送一个ClientHello消息给服务器，包含支持的TLS版本、加密算法列表和一个随机数（ClientRandom）。
2. 服务器回应：服务器接收到ClientHello消息后，选择一个加密算法、生成一个随机数（ServerRandom），并将选定的加密算法和随机数发送给客户端，同时发送自己的证书（如果需要客户端验证身份）。
3. 客户端验证服务器证书：客户端收到服务器的响应后，验证服务器的证书是否合法。如果证书有效，客户端生成一个新的随机数（PremasterSecret），并使用服务器的公钥加密这个随机数，然后将加密后的随机数发送给服务器。
4. 双方生成会话密钥：服务器收到客户端发来的加密后的PremasterSecret后，使用自己的私钥解密得到PremasterSecret，然后双方使用ClientRandom、ServerRandom和PremasterSecret通过一定的计算生成对话密钥（Session Key）。
5. 客户端通知服务器握手结束：客户端发送一个Finished消息，其中包含用于验证握手过程是否成功的哈希值。
6. 服务器发送握手结束通知：服务器也发送一个Finished消息。
7. 握手完成：握手过程完成，双方使用生成的会话密钥进行加密通信。

12、客户端怎样检验CA证书的？

1. 验证证书的合法性：客户端首先检查证书是否由受信任的证书颁发机构（CA）签发，即是否在本地信任的根证书列表中。如果证书不是由受信任的CA签发，客户端将会发出警告，提示用户证书可能不安全。
2. 验证证书的有效期：客户端检查证书的有效期，确保证书尚未过期。如果证书已过期，客户端会认为证书无效。
3. 检查证书的域名是否匹配：客户端检查证书中的主题（Subject）字段，确保证书的域名与正在访问的域名匹配。这可以防止中间人攻击。
4. 检查证书的吊销状态：客户端检查证书的吊销状态，确保证书未被吊销。CA会定期发布证书吊销列表（CRL）或使用在线证书状态协议（OCSP）来告知证书是否已经被吊销。
5. 验证证书链：如果证书是由中间CA签发的，客户端会递归地验证证书链，直到到达根证书。证书链中的每个证书都必须由其上一级证书签名，最终必须由根证书签名。
6. 执行安全性检查：一些客户端还会执行其他安全性检查，如检查证书密钥长度是否足够强、证书中是否包含关键用途扩展（如服务器身份认证、数字签名等）等。

13、如果有中间人伪造服务端发送CA证书，客户端会怎么处理？

如果有中间人伪造了服务端发送的CA证书，客户端可能会遇到以下情况：

1. 证书不受信任：客户端首先会验证证书的签发者是否在本地的受信任CA列表中。如果证书的签发者不在列表中，客户端会提示证书不受信任，无法建立安全连接。
2. 证书过期：客户端会检查证书的有效期，如果证书已过期，客户端会提示证书已过期，无法建立安全连接。
3. 域名不匹配：客户端会检查证书中的域名是否与正在访问的域名匹配。如果不匹配，客户端会提示域名不匹配，可能存在中间人攻击。
4. 证书链不完整：客户端会递归地验证证书链，确保每个证书都是由上一级证书签发的。如果证书链不完整，客户端会提示证书链不完整，无法建立安全连接。
5. 证书被吊销：客户端会检查证书的吊销状态，如果证书已被吊销，客户端会提示证书已被吊销，无法建立安全连接。

14、随便写一个你会的排序算法？