快手游戏服务端开发一面

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

1、tcp的重传机制有哪几种？具体描述一下

1. 超时重传（Timeout Retransmission）

这是最基本的重传机制。TCP会为每一个已发送但未确认的分组设置一个超时时间（即重传超时时间，RTO）。如果在该时间内没有收到对该分组的确认（ACK），则认为该分组丢失并重新发送。

RTO计算：RTO并不是固定的，而是根据网络的往返时间（RTT，Round-Trip Time）动态调整的。TCP根据测量到的RTT值计算加权平均值（SRTT，Smoothed RTT）并加上一定的偏差（RTTVAR）来确定RTO值，确保在网络状况不佳时适当延长超时时间。

2. 快速重传（Fast Retransmit）

快速重传是一种比超时重传更快的机制。它依赖于TCP的累积确认特性。如果TCP接收方收到一个乱序的分组（即缺少前面的某个分组），它会立即发送一个重复的ACK。发送方收到三个连续的重复ACK（即四个相同的ACK，包括原ACK和三个重复ACK）时，就会认为该分组可能丢失了，立即触发重传，而不必等待RTO超时。

触发条件：三个重复ACK。
优势：能够更快地检测和恢复部分丢包情况，减少等待超时的时间。

3. 选择性确认（Selective Acknowledgment, SACK）

SACK是一种TCP扩展，允许接收方通知发送方哪些数据块已经成功收到，哪些没有。这样，发送方可以仅重传那些确实丢失的数据块，而不必重传整段数据。

SACK选项：在TCP头部的选项字段中包含，发送方和接收方在建立连接时通过选项协商SACK支持。
优势：在高丢包率或乱序情况严重时，SACK能显著减少重传的数据量，提升传输效率。

4. 快速恢复（Fast Recovery）

快速恢复通常与快速重传机制结合使用。当快速重传被触发时，TCP假设网络丢包是由拥塞引起的，因此它会将拥塞窗口（cwnd）减半以减少网络负载。快速恢复机制允许TCP在进入拥塞避免阶段之前立即重传丢失的数据，而不是像传统的慢启动（Slow Start）那样从一个小窗口开始。

操作过程：

快速重传：触发重传丢失的分组。
快速恢复：调整cwnd，并重传数据，在恢复之前保持传输速率接近丢包前的水平。

5. 重复数据重传（Duplicate Data Retransmission）

这种机制用于应对数据乱序到达的情况。TCP接收方可以接收到某些乱序的数据段，它会继续发送ACK以确认已经收到的数据段，但也会通知发送方有数据段是丢失的。发送方根据这些信息进行必要的数据重传。

2、override、final？

1. `override` 关键字

override关键字用于显式声明派生类中的虚函数是重写基类中的虚函数。它使得代码更为清晰，便于编译器在编译期间检测潜在的错误。

用法

当在派生类中重写一个基类的虚函数时，可以使用override关键字来标记该函数。这可以确保函数的签名（返回类型、参数类型和数量）完全匹配基类中的虚函数签名。如果不匹配，编译器会产生一个错误，避免运行时出现意外行为。

c++

class Base {
public:
    virtual void doSomething(int x) {
        // 基类中的实现
    }
};

class Derived : public Base {
public:
    void doSomething(int x) override {  // 使用 override 关键字
        // 派生类中的实现
    }
};

如果你在派生类中错误地声明了一个函数，比如签名不匹配：

c++

class Derived : public Base {
public:
    void doSomething(double x) override {  // 编译错误，参数类型不匹配
        // 错误的重写（参数类型不同）
    }
};

编译器将会给出一个错误，因为doSomething(double x)并没有正确重写基类中的doSomething(int x)。

2. `final` 关键字

final关键字用于防止类被进一步继承或防止类的虚函数在派生类中被重写。它帮助开发者明确地表明设计意图，防止误用。

用法

用于类：如果你希望某个类不能被进一步继承，可以将类声明为final。
用于虚函数：如果你希望某个虚函数不能被进一步重写，可以将该函数声明为final。

用于类：

c++

class FinalClass final {
    // 该类不能被继承
};

// 会导致编译错误，因为 FinalClass 是 final
class DerivedFromFinal : public FinalClass {
    // 编译错误
};

用于虚函数：

c++

class Base {
public:
    virtual void doSomething() final {
        // 该方法不能被派生类重写
    }
};

class Derived : public Base {
public:
    // 编译错误：doSomething 被标记为 final，不能重写
    void doSomething() override {
        // 企图重写final函数
    }
};

3、epoll的边缘触发和水平触发？

1. 水平触发（Level Triggered, LT）

水平触发是 epoll 的默认模式。特点是：只要文件描述符（file descriptor, FD）上有未处理的事件，epoll 就会不断通知应用程序。这意味着应用程序可以不必一次性处理所有数据，可以留到下次处理。

工作原理

行为：只要文件描述符上的数据没有被完全读取或者空间没有被完全写满，epoll 会反复地通知用户有事件需要处理。
触发条件：当文件描述符变为可读或可写状态时，且直到所有数据都被处理或者空间被使用完之前，epoll 都会通知。
实现：适合数据量不确定的情况或需要逐步处理数据的场景。

假设一个套接字上有数据可读，水平触发模式下，只要该套接字上还有数据可读，每次调用 epoll_wait 都会返回该事件，直到数据被完全读取。

c++

int fd = socket(...);
struct epoll_event ev, events[MAX_EVENTS];
int epollfd = epoll_create1(0);

ev.events = EPOLLIN; // 读事件，水平触发
ev.data.fd = fd;
epoll_ctl(epollfd, EPOLL_CTL_ADD, fd, &ev);

while (1) {
    int nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
    for (int n = 0; n < nfds; ++n) {
        if (events[n].data.fd == fd) {
            // 处理可读事件
            handle_read(fd);
        }
    }
}

2. 边缘触发（Edge Triggered, ET）

边缘触发是一种高效模式，通常用于减少系统调用次数。与水平触发不同的是，边缘触发仅在文件描述符的状态发生变化时通知应用程序，并且只通知一次。如果应用程序没有在通知时处理所有数据或进行所有的写操作，它就不会再收到通知。

工作原理

行为：只在文件描述符从无数据到有数据（可读）、或从不能写到能写（可写）的状态变化时通知，且只会触发一次。应用程序必须尽可能地读取或写入文件描述符，直到返回 EAGAIN 错误。
触发条件：当文件描述符的状态从不可用变为可用时（例如从无数据变为有数据），epoll 只通知一次。要想再次触发，状态必须再次发生变化。
实现：适用于需要在事件发生后立即处理大量数据的情况，通常用于提高效率，因为减少了重复的事件通知。

在边缘触发模式下，假设套接字上有数据可读，epoll 只会通知一次。应用程序必须在收到通知时将数据读取完（或写入尽可能多的数据），否则就不会再收到通知。

c++

int fd = socket(...);
struct epoll_event ev, events[MAX_EVENTS];
int epollfd = epoll_create1(0);

ev.events = EPOLLIN | EPOLLET; // 读事件，边缘触发
ev.data.fd = fd;
epoll_ctl(epollfd, EPOLL_CTL_ADD, fd, &ev);

while (1) {
    int nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
    for (int n = 0; n < nfds; ++n) {
        if (events[n].data.fd == fd) {
            // 处理可读事件，边缘触发需要一直读取，直到返回 EAGAIN
            while (1) {
                ssize_t count = read(fd, buffer, sizeof(buffer));
                if (count == -1) {
                    if (errno == EAGAIN) {
                        // 没有更多的数据可读
                        break;
                    } else {
                        // 处理读取错误
                        handle_error(fd);
                    }
                } else if (count == 0) {
                    // EOF，关闭连接
                    close(fd);
                    break;
                } else {
                    // 处理数据
                    handle_data(buffer, count);
                }
            }
        }
    }
}

4、tcp的滑动窗口？

TCP（Transmission Control Protocol）的**滑动窗口（Sliding Window）**机制是用于流量控制和保证可靠传输的重要机制。滑动窗口机制通过在发送方和接收方之间动态调整数据包的发送和接收速度，确保网络资源的高效利用，并防止网络拥塞和丢包。

1. 滑动窗口的基本概念

TCP 滑动窗口机制的核心是利用一个动态的窗口（window）来控制发送方可以发送的字节数量，这个窗口会根据接收方的处理能力和网络状况动态调整。

发送窗口（Send Window）：发送方在特定时刻可以发送的数据字节数的范围。未被确认的已发送数据加上尚未发送的数据总和不能超过这个窗口的大小。
接收窗口（Receive Window）：接收方可以接收和缓存的数据字节数的范围。接收方通过 ACK（确认报文）将其接收窗口的大小反馈给发送方。

2. 滑动窗口的工作原理

滑动窗口的工作方式可以简单描述为：

初始化：发送方和接收方在连接建立时商定初始窗口大小。
发送数据：发送方可以在不超出发送窗口的范围内连续发送多个数据包。
接收数据并发送确认（ACK）：接收方在收到数据后，更新自己的接收窗口，并通过 ACK 报文告知发送方它所能接收的窗口大小。
窗口滑动：发送方在接收到 ACK 后，将发送窗口向前滑动（即窗口的起点根据已确认的数据向前移动），从而允许发送新的数据。

窗口滑动示例

假设发送窗口大小为 4 个字节，接收窗口大小也为 4 个字节：

初始状态：
- 发送窗口：[0, 1, 2, 3]
- 已发送但未确认的数据：空
- 未发送的数据：[4, 5, 6, ...]
步骤1：发送方发送字节 0到3。
- 发送窗口：[0, 1, 2, 3]
- 已发送但未确认的数据：[0, 1, 2, 3]
步骤2：接收方收到字节0到 3，并发回 ACK = 4，表示它已经成功接收到这些字节，并可以接收新的数据。
- 发送窗口根据 ACK 滑动到 [4, 5, 6, 7]。
- 发送方可以继续发送字节 4 到 7。

窗口滑动的图示

发送窗口:
+---+---+---+---+
| 0 | 1 | 2 | 3 | 已发送数据
+---+---+---+---+
| 4 | 5 | 6 | 7 | 未发送数据
+---+---+---+---+

3. 滑动窗口的优势

高效数据传输：滑动窗口机制允许发送方在不等待每个数据包的 ACK 的情况下连续发送多个数据包，从而提高了数据传输效率，特别是在高延迟网络中。
流量控制：接收方通过告知接收窗口大小来控制发送方的发送速度，防止接收方缓存溢出。
拥塞控制：结合 TCP 的其他机制（如慢启动、拥塞避免、快速重传等），滑动窗口也用于动态调整发送速率以避免网络拥塞。

4. TCP 滑动窗口的细节

滑动窗口机制涉及多个参数和机制：

窗口大小（Window Size）：通过 TCP 头部的 Window Size 字段进行声明，最大为 65535 字节（如果使用窗口缩放选项，可以更大）。
接收窗口（Receive Window）：动态调整，取决于接收方的缓冲区容量。
发送窗口（Send Window）：由接收窗口和拥塞窗口（Congestion Window，反映网络拥塞状态）共同决定。发送窗口大小等于这两个窗口的较小值。

5. 重要的滑动窗口机制

1. 流量控制（Flow Control）

TCP 滑动窗口的一个关键功能是流量控制，确保发送方的发送速率不会超过接收方的接收能力。接收方在 ACK 报文中包含了接收窗口大小，发送方根据这个大小调整自己的发送窗口。

2. 拥塞控制（Congestion Control）

TCP 使用滑动窗口机制进行拥塞控制，防止网络出现拥塞。主要方法包括：

慢启动（Slow Start）：发送窗口（拥塞窗口）从小到大逐渐增大，直到达到一个阈值（慢启动阈值）。
拥塞避免（Congestion Avoidance）：当超过慢启动阈值后，窗口增速减慢，避免拥塞。
快速重传和快速恢复（Fast Retransmit and Fast Recovery）：在丢包或重传时，通过减小窗口大小并逐步恢复，以迅速适应网络状况。

5、stl的常用容器及其底层实现数据结构？

`vector`

概述：vector 是一个动态数组，支持快速随机访问。它的元素在内存中是连续存储的，类似于C语言中的数组。
底层实现：使用动态数组（即连续的内存块）。当需要扩展容量时，vector 会重新分配更大的内存块并将原有元素拷贝过去。默认情况下，vector的容量按2倍的方式增长。
特点：
- 支持随机访问（通过索引），时间复杂度为 O(1)。
- 插入和删除操作（非末尾）可能会导致大量元素的移动，时间复杂度为 O(n)。
- 在尾部插入和删除元素相对高效，摊销时间复杂度为 O(1)。

c++

std::vector<int> vec;  // 创建一个空的vector

`deque`

概述：deque（double-ended queue，双端队列）支持在两端快速插入和删除元素。deque的元素并不是连续存储的。
底层实现：使用一组指向不同内存块的指针，这些内存块共同构成一个逻辑上的连续存储空间。通常使用双向链表和动态数组相结合的结构。
特点：
- 支持快速的随机访问，时间复杂度为 O(1)。
- 支持在两端插入和删除元素，时间复杂度为 O(1)。
- 中间插入和删除操作需要移动数据块指针，时间复杂度为 O(n)。

cpp

std::deque<int> deq;  // 创建一个空的deque

`list`

概述：list 是一个双向链表，支持在任意位置快速插入和删除元素。
底层实现：双向链表，每个节点包含指向前一个和后一个节点的指针。
特点：
- 不支持随机访问，访问特定位置的元素需要遍历链表，时间复杂度为 O(n)。
- 在链表的任意位置进行插入和删除操作非常高效，时间复杂度为 O(1)。
- 元素的内存地址不连续，增加了内存开销。

c++

std::list<int> lst;  // 创建一个空的list

`set` 和 `multiset`

概述：set 是一种有序集合，其中的元素是唯一的，multiset 允许重复元素。它们通常用于需要快速查找、插入和删除元素的场景。
底层实现：红黑树（self-balancing binary search tree，自平衡二叉查找树）。
特点：
- 自动对元素进行排序。
- 查找、插入和删除操作的时间复杂度为 O(log n)。
- 元素的插入操作会按顺序排列（根据比较规则）。

c++

std::set<int> s;  // 创建一个空的set
std::multiset<int> ms;  // 创建一个空的multiset

`map` 和 `multimap`

概述：map 是一种关联容器，用于存储键值对（key-value pair），其中键是唯一的，multimap 允许多个相同的键。map 和 multimap 是用来快速查找、插入和删除键值对的容器。
底层实现：红黑树。
特点：
- 自动对键进行排序。
- 查找、插入和删除操作的时间复杂度为 O(log n)。
- 键是唯一的（map）或可重复的（multimap）。

c++

std::map<int, std::string> m;  // 创建一个空的map
std::multimap<int, std::string> mm;  // 创建一个空的multimap

`unordered_set` 和 `unordered_multiset`

概述：unordered_set 是一种无序集合，基于哈希表（hash table），元素的顺序不固定，unordered_multiset 允许重复元素。
底层实现：哈希表。
特点：
- 元素无序存储。
- 查找、插入和删除操作的平均时间复杂度为 O(1)，最坏情况下为 O(n)（当发生哈希碰撞时）。
- 更高效的查找和插入操作，相较于基于树的容器（如 set 和 map）。

c++

std::unordered_set<int> us;  // 创建一个空的unordered_set
std::unordered_multiset<int> ums;  // 创建一个空的unordered_multiset

`unordered_map` 和 `unordered_multimap`

概述：unordered_map 是一种无序的关联容器，用于存储键值对，基于哈希表，unordered_multimap 允许多个相同的键。
底层实现：哈希表。
特点：
- 键值对无序存储。
- 查找、插入和删除操作的平均时间复杂度为 O(1)，最坏情况下为 O(n)。
- 键是唯一的（unordered_map）或可重复的（unordered_multimap）。

c++

std::unordered_map<int, std::string> um;  // 创建一个空的unordered_map
std::unordered_multimap<int, std::string> umm;  // 创建一个空的unordered_multimap

`stack`

概述：stack 是一种适用于后进先出（LIFO，Last In, First Out）操作的容器适配器，它允许在容器的一端（栈顶）进行插入和删除操作。
底层实现：通常使用 deque 作为底层实现，但也可以使用 vector 或 list。
特点：
- 只允许访问栈顶元素。
- 插入（push）、删除（pop）和访问（top）操作的时间复杂度为 O(1)。

c++

std::stack<int> stk;  // 创建一个空的stack

`queue`

概述：queue 是一种适用于先进先出（FIFO，First In, First Out）操作的容器适配器，允许在容器的一端插入（入队），在另一端删除（出队）。
底层实现：通常使用 deque 作为底层实现，但也可以使用 list。
特点：
- 只允许访问队头和队尾。
- 插入（push）、删除（pop）和访问（front, back）操作的时间复杂度为 O(1)。

c++

std::queue<int> q;  // 创建一个空的queue

`priority_queue`

概述：priority_queue 是一种优先队列，允许按照优先级顺序（默认是最大堆）来插入和删除元素。
底层实现：通常使用堆（heap），例如二叉堆。
特点：
- 自动按优先级顺序排序。
- 插入（push）和删除（pop）操作的时间复杂度为 O(log n)。
- 访问最高优先级的元素（top）操作的时间复杂度为 O(1)。

c++

std::priority_queue<int> pq;  // 创建一个空的priority_queue

6、static的用法和作用？

1. 在函数内部使用 `static` 变量

用法：当在函数内部声明一个变量为 static 时，该变量在函数的多个调用之间保持其值不变。
作用：
- 持久性：static 局部变量的生命周期为整个程序运行期间，而不是局限于函数的单次调用。因此，它在函数调用结束后依然存在，并在下次调用时保留上次的值。
- 仅初始化一次：static 局部变量在程序的生命周期内只被初始化一次，之后的每次函数调用不会重新初始化该变量。

c++

#include <iostream>

void counter() {
    static int count = 0;  // 只初始化一次
    count++;
    std::cout << "Count: " << count << std::endl;
}

int main() {
    counter();  // 输出: Count: 1
    counter();  // 输出: Count: 2
    counter();  // 输出: Count: 3
    return 0;
}

count 变量在 counter 函数内被声明为 static，因此它的值在每次调用 counter 函数后都保持不变，而不是在每次函数调用时重新初始化。

2. 在全局或命名空间作用域使用 `static` 变量或函数

用法：在全局或命名空间作用域声明的变量或函数前加上 static 关键字。
作用：
- 内部链接性：static 全局变量或函数的作用域仅限于定义它的文件（编译单元），不会被其他文件（编译单元）访问。它们的名称在连接（linking）阶段是局部的。
- 隐藏：static 的这种特性可以防止名称冲突，因为这些变量或函数不会与其他文件中的同名实体冲突。

c++

// file1.cpp
static int file_scope_var = 42;  // 仅限于 file1.cpp 文件内可见

static void staticFunction() {   // 仅限于 file1.cpp 文件内可见
    std::cout << "This is a static function in file1.cpp" << std::endl;
}

file_scope_var 和 staticFunction 只在 file1.cpp 文件内部可见。即使另一个文件（如 file2.cpp）中也有一个同名的变量或函数，它们之间也不会发生冲突。

3. 在类中使用 `static` 成员变量和成员函数

用法：static 成员变量和成员函数是类的属性，而不是类的对象的属性。它们属于整个类，而不是类的某个实例。
作用：
- 共享数据：所有对象共享同一个 static 成员变量。
- 无需实例化：static 成员函数可以在不创建类对象的情况下调用，因为它们不依赖于类的特定实例。

c++

#include <iostream>

class Example {
public:
    static int staticVar;  // 静态成员变量声明

    static void staticMethod() {  // 静态成员函数
        std::cout << "Static Method called. StaticVar: " << staticVar << std::endl;
    }
};

// 静态成员变量定义
int Example::staticVar = 0;

int main() {
    Example::staticVar = 10;  // 修改静态成员变量
    Example::staticMethod();  // 调用静态成员函数
    return 0;
}

staticVar 是 Example 类的静态成员变量，staticMethod 是静态成员函数。它们都可以在不实例化 Example 类的情况下直接通过类名调用。

7、智能指针？

1. `std::unique_ptr`

概述：std::unique_ptr 是一种独占所有权的智能指针，即一个对象的所有权只能被一个 std::unique_ptr 拥有。
特点：
- 独占所有权：一个对象只能由一个 std::unique_ptr 实例拥有，不能被复制。
- 转移所有权：可以通过 std::move 将所有权转移到另一个 std::unique_ptr。
- 自动释放内存：当 std::unique_ptr 超出其作用域或被销毁时，会自动调用 delete 释放所指向的对象。
- 轻量级：由于不需要维护引用计数，相比 std::shared_ptr，std::unique_ptr 更加轻量。

c++

#include <memory>
#include <iostream>

void example() {
    std::unique_ptr<int> ptr1 = std::make_unique<int>(10);
    std::cout << *ptr1 << std::endl; // 输出 10

    // std::unique_ptr<int> ptr2 = ptr1;  // 错误：`unique_ptr` 不可复制
    std::unique_ptr<int> ptr2 = std::move(ptr1); // 使用 std::move 转移所有权
    if (!ptr1) {
        std::cout << "ptr1 is now null" << std::endl;
    }
}

2. `std::shared_ptr`

概述：std::shared_ptr 是一种具有共享所有权的智能指针，多个 shared_ptr 可以指向相同的对象，并通过引用计数来管理对象的生命周期。
特点：
- 共享所有权：多个 std::shared_ptr 可以共享同一个对象的所有权。
- 引用计数：内部维护一个引用计数器，当引用计数变为 0 时，自动释放内存。
- 线程安全：增加和减少引用计数的操作是线程安全的。

c++

#include <memory>
#include <iostream>

void example() {
    std::shared_ptr<int> ptr1 = std::make_shared<int>(20);
    std::shared_ptr<int> ptr2 = ptr1; // 共享同一个对象

    std::cout << *ptr1 << std::endl; // 输出 20
    std::cout << ptr1.use_count() << std::endl; // 输出 2（引用计数）
}

3. `std::weak_ptr`

概述：std::weak_ptr 是一种不影响引用计数的智能指针，通常与 std::shared_ptr 搭配使用，用于解决循环引用的问题。
特点：
- 不共享所有权：std::weak_ptr 不影响 std::shared_ptr 的引用计数。
- 用于观察：std::weak_ptr 用于观察但不拥有对象，适合用于避免循环引用。
- 检查对象有效性：可以使用 expired() 检查对象是否已经被释放，也可以使用 lock() 从 weak_ptr 创建一个 shared_ptr（如果对象还存在）。

c++

#include <memory>
#include <iostream>

void example() {
    std::shared_ptr<int> sharedPtr = std::make_shared<int>(30);
    std::weak_ptr<int> weakPtr = sharedPtr; // 不影响引用计数

    std::cout << "Shared pointer count: " << sharedPtr.use_count() << std::endl; // 输出 1

    if (auto lockedPtr = weakPtr.lock()) { // 使用 lock() 创建 shared_ptr
        std::cout << *lockedPtr << std::endl; // 输出 30
    }
}

4. `std::auto_ptr`（已弃用）

概述：std::auto_ptr 是一种早期的智能指针类型，已在 C++11 中被弃用，并在 C++17 中被移除。它的语义与 std::unique_ptr 类似，但有一些问题。
特点：
- 独占所有权：类似于 std::unique_ptr，但 auto_ptr 会在复制时转移所有权（使用复制语义），容易导致意外的所有权转移。
- 已弃用和移除：因为 auto_ptr 存在易用性和所有权语义问题，它在 C++11 中被弃用，之后在 C++17 中被完全移除。

8、虚函数、虚表指针？

1. 虚函数（Virtual Function）

概念：虚函数是指在基类中使用 virtual 关键字声明的成员函数。虚函数允许在继承结构中通过基类指针或引用来调用派生类的函数，实现运行时的多态性（即动态绑定或晚绑定）。
用途：虚函数用于在继承体系中，基类指针或引用调用派生类对象时，确保调用派生类的重写版本，而不是基类版本。
如何使用：
- 在基类中定义一个函数为虚函数，只需在函数声明前加上 virtual 关键字。
- 在派生类中重写该虚函数时，不需要再次使用 virtual 关键字，但可以加上 override 关键字以表示它是重写的函数（C++11 引入）。

c++

#include <iostream>

// 基类
class Base {
public:
    virtual void show() { // 虚函数
        std::cout << "Base class show function called." << std::endl;
    }
};

// 派生类
class Derived : public Base {
public:
    void show() override { // 重写虚函数
        std::cout << "Derived class show function called." << std::endl;
    }
};

int main() {
    Base* basePtr = new Derived(); // 基类指针指向派生类对象
    basePtr->show(); // 调用派生类的 show 函数
    delete basePtr;
    return 0;
}

输出：

c++

Derived class show function called.

基类 Base 的 show 函数是虚函数。派生类 Derived 重写了 show 函数。当 basePtr（类型为 Base*）指向 Derived 的实例时，调用 basePtr->show() 实际上会调用 Derived 的 show 函数，而不是 Base 的 show 函数。

2. 虚表（Virtual Table, vtable）和虚表指针（vtable pointer, vptr）

虚表（vtable）：
- 虚表是一个存储类中虚函数地址的表。每个包含虚函数的类都有一个虚表。
- 在类中声明虚函数后，编译器为该类生成一张虚表，其中包含该类及其所有基类中所有虚函数的地址。
- 对于没有虚函数的类，编译器不会为其生成虚表。
虚表指针（vptr）：
- 虚表指针是一个隐藏的指针，存在于每个对象的内存布局中，指向对象所属类的虚表。
- 当对象被创建时，构造函数会初始化对象的虚表指针，使其指向正确的虚表。
- 当通过基类指针或引用调用虚函数时，编译器通过对象的虚表指针找到虚表，然后根据虚表中的函数地址进行调用，实现动态绑定。
工作机制：
- 每个对象的虚表指针（vptr）指向该对象所属类的虚表（vtable）。
- 当通过基类指针调用虚函数时，实际的调用过程是通过 vptr 找到虚表，进而找到对应的函数指针，然后调用该函数。
- 这种机制使得 C++ 能够在运行时确定要调用哪个函数，实现了多态性。

示例：虚表和虚表指针的工作机制

假设有如下的类继承关系：

c++

class Base {
public:
    virtual void func1() { /* ... */ }
    virtual void func2() { /* ... */ }
};

class Derived : public Base {
public:
    void func1() override { /* ... */ } // 重写基类的 func1
    void func3() { /* ... */ } // 派生类独有的函数
};

对于 Base 类，它的虚表可能看起来像这样：

c++

Base_vtable:
+---------------------+
| Base::func1 address |
+---------------------+
| Base::func2 address |
+---------------------+

而对于 Derived 类，它的虚表可能看起来像这样：

c++

Derived_vtable:
+---------------------+
| Derived::func1 address | // 重写后的函数地址
+-----------------------+
| Base::func2 address    | // 没有重写，指向基类的函数地址
+-----------------------+

每个 Base 对象有一个 vptr，指向 Base_vtable；每个 Derived 对象有一个 vptr，指向 Derived_vtable。调用虚函数时，通过对象的 vptr 指针确定实际调用的函数。

9、内存碎片？

内存碎片（Memory Fragmentation）是计算机内存管理中的一种现象，指的是由于频繁的内存分配和释放操作，导致内存中出现不能被有效利用的零散空间，进而影响系统性能和内存使用效率。内存碎片通常分为两种类型：外部碎片（External Fragmentation）和内部碎片（Internal Fragmentation）。

1. 外部碎片（External Fragmentation）

概念：外部碎片指的是由于内存块的分配和释放操作导致可用的空闲内存被分割成许多小块，这些小块分布在整个内存空间中，而每个小块都不足以满足新的内存分配请求。即便系统总的空闲内存足够，但因为它们不连续，导致无法分配给需要较大连续空间的请求。

产生原因：

当程序反复进行内存分配和释放操作时，内存分配器可能会将内存划分为不同大小的块。这些块之间可能会因为释放操作而产生不连续的空闲内存。
如果分配和释放的内存块大小不一致，内存会被切割成许多不同大小的空闲区域，这些空闲区域在新内存分配时可能因为不够大或位置不合适而无法被利用。

假设内存初始状态如下（每个数字代表分配的块，- 代表空闲块）：

|1111|--|22222|---|333|------|

如果释放块 1111 和 333 后内存情况如下：

|----|--|22222|---|---|------|

接下来需要一个大小为 6 的块，但是现有的所有空闲块都不能满足这个请求，即使总空闲内存（13个单位）是足够的。这就产生了外部碎片。

解决方法：

内存压缩：操作系统或内存管理器会偶尔进行内存压缩，将散落在各处的空闲块集中起来，形成更大的连续内存空间。
内存分区算法：使用适当的内存分配策略，如首次适应（First Fit）、最佳适应（Best Fit）和最差适应（Worst Fit）等，来尽量减少外部碎片的产生。

2. 内部碎片（Internal Fragmentation）

概念：内部碎片指的是分配的内存块内部未被使用的部分。由于内存分配器一般会按照一定的对齐要求（如8字节或16字节对齐）来分配内存，所以分配的内存块可能会比实际需要的稍大，导致一部分内存未被使用。

产生原因：当程序申请的内存量不是内存分配单元的整数倍时，分配器通常会向上对齐分配更多的内存。例如，如果内存管理器按8字节对齐，而程序请求的内存大小为10字节，那么实际分配的将是16字节，这样就会有6字节的内部碎片。

假设分配器按 16 字节对齐，而程序申请了 30 字节的内存，那么实际分配的将是 32 字节。未使用的 2 字节就是内部碎片。

解决方法：

更精细的内存管理：使用定制的内存分配器，根据具体情况调整内存块大小和对齐要求，减少内部碎片。
对象池或内存池：对于大量小对象的分配，可以使用对象池或内存池来管理内存，以减少内存碎片。

10、索引的优缺点？

优点

提高查询性能：
- 加速检索：索引可以极大地提高查询速度，尤其是对大型表中的数据进行检索时。它允许数据库管理系统（DBMS）快速定位到所需的记录，而无需扫描整个表。
- 支持快速排序和分组：索引能够加速排序（ORDER BY）和分组（GROUP BY）操作，因为索引可以帮助数据库快速找到排序或分组的所需记录。
优化查询条件：
- 提高特定条件下的查询效率：对于经常用于 WHERE 子句中的列，索引能够提高检索效率。例如，索引可以优化对某列的精确匹配或范围查询（如大于、小于操作符）。
提高唯一性约束：
- 支持唯一性约束：索引可用于维护数据的唯一性，如主键和唯一键索引可以确保表中不会出现重复的记录。
改进连接操作：
- 加速连接操作：在多表连接操作中，索引可以加速连接条件的匹配过程，提高联接的效率。

缺点

增加存储空间：
- 额外的存储开销：索引需要额外的存储空间来保存索引数据结构。对于大型表或多个索引的表，这些存储开销可能会非常显著。
降低写入性能：
- 写入操作的开销：每当对表进行插入、更新或删除操作时，相关的索引也需要进行更新。这可能会导致写操作的性能下降，特别是在有大量索引的情况下。
维护复杂性：
- 索引维护的复杂性：管理和优化索引需要额外的工作。选择哪些列建立索引、调整索引策略、监控索引性能等，都需要数据库管理员的细心维护和优化。
可能影响查询计划：
- 查询优化器的挑战：索引的存在可能会使查询优化器在选择最佳查询计划时变得更加复杂。有时，过多的索引可能会导致优化器选择次优的查询计划。

11、索引可以用哪些数据结构实现？

1. B树（B-Tree）

概念：B树是一种自平衡的树数据结构，广泛用于数据库和文件系统的索引。它的每个节点都可以有多个子节点，从而保持树的平衡。
特性：
- 自平衡：保持树的平衡，所有叶子节点都在同一层，确保查询时间复杂度为 O(log N)。
- 多路搜索：每个节点可以有多个子节点，使得搜索操作更高效。
- 适合范围查询：支持高效的范围查询操作。
应用：适用于需要高效查找、插入、删除和范围查询的场景。

2. B+树（B+-Tree）

概念：B+树是 B树的一个变种，所有的值都存储在叶子节点中，内部节点只存储索引信息。叶子节点通过链表连接，以支持范围查询。
特性：
- 所有值存储在叶子节点：使得范围查询更加高效。
- 叶子节点链表：链表结构允许顺序遍历和范围查询操作。
应用：在数据库系统和文件系统中广泛使用，如 MySQL 的 InnoDB 存储引擎。

3. 哈希表（Hash Table）

概念：哈希表通过哈希函数将键映射到表中的位置，以实现快速的查找操作。
特性：
- 常数时间复杂度：查找操作平均时间复杂度为 O(1)。
- 适合等值查询：对单个值的查询非常高效，但不适合范围查询。
应用：适用于只需快速查找、插入和删除操作的场景，如数据库中的哈希索引。

4. 位图索引（Bitmap Index）

概念：位图索引使用位图（bitmaps）来表示数据表中每个可能的值，通常用于低基数列（即列的不同值数量较少）。
特性：
- 压缩：位图可以压缩，适用于具有少量唯一值的列。
- 高效的逻辑运算：位图索引支持高效的逻辑运算（如 AND、OR、NOT），使得查询更加高效。
应用：适用于具有较少不同值的列，如性别、状态等。

5. 跳表（Skip List）

概念：跳表是一种链表的随机化数据结构，通过增加多层链表来实现快速的查找、插入和删除操作。
特性：
- 层次化链表：多层链表结构使得查找操作的时间复杂度为 O(log N)。
- 随机化：跳表利用随机化来实现平衡，提高操作效率。
应用：用于需要支持动态变化的高效查找操作的场景，部分数据库系统和内存数据库（如 Redis）中会使用跳表。

6. Trie（前缀树）

概念：Trie 是一种树状数据结构，用于高效存储和检索字符串，特别适用于前缀匹配。
特性：
- 前缀查询：支持快速的前缀匹配和词典查询。
- 空间效率：对于共享前缀的字符串，Trie 具有良好的空间效率。
应用：广泛用于实现字典、自动补全、拼写检查等功能。

12、手撕（15min）二叉树最近公共祖先

思路

递归

从根节点开始遍历二叉搜索树。
如果根节点的值大于两个指定节点的值，则最近公共祖先在左子树中，递归处理左子树。
如果根节点的值小于两个指定节点的值，则最近公共祖先在右子树中，递归处理右子树。
如果根节点的值位于两个指定节点的值之间，则根节点即为最近公共祖先。

非递归

从根节点开始遍历二叉搜索树。
如果当前节点的值大于两个目标节点的值，说明最近公共祖先在当前节点的左子树中，移动到左子节点继续遍历。
如果当前节点的值小于两个目标节点的值，说明最近公共祖先在当前节点的右子树中，移动到右子节点继续遍历。
如果当前节点的值在两个目标节点的值之间，说明当前节点就是最近公共祖先，直接返回当前节点。

使用栈：

从根节点开始，使用栈来辅助进行迭代遍历。
对于每个节点，判断其值与要查找的两个节点的值的关系：
- 如果节点的值在两个节点的值之间，或者等于其中一个节点的值，则当前节点就是最近公共祖先。
- 如果当前节点的值大于两个节点值的最大值，则说明最近公共祖先在当前节点的左子树中，将左子节点入栈。
- 如果当前节点的值小于两个节点值的最小值，则说明最近公共祖先在当前节点的右子树中，将右子节点入栈。
不断重复上述过程，直到找到最近公共祖先为止。

图解

根据示例二给大家进行图解。

2和4都小于根节点6，所以2和4都在根节点6的左子树上。

根节点的左子结点就是2，而4大于2，肯定在节点2的右节点上了。

所以，节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

参考代码

C++

递归

c++

#include <iostream>

using namespace std;

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 寻找二叉搜索树中两个节点的最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr; // 如果根节点为空，返回nullptr
    if (root->val > p->val && root->val > q->val) {
        // 如果根节点的值大于两个节点的值，则最近公共祖先在左子树中
        return lowestCommonAncestor(root->left, p, q);
    } else if (root->val < p->val && root->val < q->val) {
        // 如果根节点的值小于两个节点的值，则最近公共祖先在右子树中
        return lowestCommonAncestor(root->right, p, q);
    } else {
        // 如果根节点的值位于两个节点的值之间，则根节点即为最近公共祖先
        return root;
    }
}

// 创建二叉树
TreeNode* createTree(vector<int>& nodes, int index) {
    if (index >= nodes.size() || nodes[index] == -1) {
        return nullptr; // 如果节点为空，则返回nullptr
    }
    TreeNode* root = new TreeNode(nodes[index]); // 创建当前节点
    root->left = createTree(nodes, 2 * index + 1); // 创建左子树
    root->right = createTree(nodes, 2 * index + 2); // 创建右子树
    return root; // 返回当前节点
}

// 销毁二叉树
void destroyTree(TreeNode* root) {
    if (!root) return; // 如果根节点为空，直接返回
    destroyTree(root->left); // 递归销毁左子树
    destroyTree(root->right); // 递归销毁右子树
    delete root; // 删除当前节点
}

int main() {
    vector<int> nodes = {6, 2, 8, 0, 4, 7, 9, -1, -1, 3, 5}; // 二叉搜索树的先序遍历序列
    TreeNode* root = createTree(nodes, 0); // 创建二叉树
    TreeNode* p = root->left->left; // 指定节点 p
    TreeNode* q = root->left->right->left; // 指定节点 q
    TreeNode* ancestor = lowestCommonAncestor(root, p, q); // 查找最近公共祖先
    cout << "The lowest common ancestor of " << p->val << " and " << q->val << " is " << ancestor->val << endl;

    destroyTree(root); // 销毁二叉树

    return 0;
}

非递归

c++

#include <iostream>

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 找到两个节点的最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root) {
        if (root->val > p->val && root->val > q->val) {
            root = root->left;  // 如果根节点值大于 p 和 q 的值，说明最近公共祖先在左子树
        } else if (root->val < p->val && root->val < q->val) {
            root = root->right;  // 如果根节点值小于 p 和 q 的值，说明最近公共祖先在右子树
        } else {
            break;  // 如果根节点的值介于 p 和 q 的值之间，说明当前节点就是最近公共祖先
        }
    }
    return root;
}

// 创建二叉树
TreeNode* createTree(std::vector<int>& nodes, int index) {
    if (index >= nodes.size() || nodes[index] == -1) {
        return nullptr;  // 如果节点为空，则返回nullptr
    }
    TreeNode* root = new TreeNode(nodes[index]);  // 创建当前节点
    root->left = createTree(nodes, 2 * index + 1);  // 创建左子树
    root->right = createTree(nodes, 2 * index + 2);  // 创建右子树
    return root;  // 返回当前节点
}

// 销毁二叉树
void destroyTree(TreeNode* root) {
    if (!root) return;  // 如果根节点为空，直接返回
    destroyTree(root->left);  // 递归销毁左子树
    destroyTree(root->right);  // 递归销毁右子树
    delete root;  // 删除当前节点
}

int main() {
    std::vector<int> nodes = {6, 2, 8, 0, 4, 7, 9, -1, -1, 3, 5};  // 二叉搜索树的先序遍历序列
    TreeNode* root = createTree(nodes, 0);  // 创建二叉树
    TreeNode* p = new TreeNode(2);  // 节点p的值为2
    TreeNode* q = new TreeNode(4);  // 节点q的值为4
    TreeNode* result = lowestCommonAncestor(root, p, q);  // 找到最近公共祖先
    std::cout << "最近公共祖先的值为：" << result->val << std::endl;

    // 销毁二叉树
    destroyTree(root);
    delete p;
    delete q;

    return 0;
}

使用栈

c++

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 非递归方式寻找二叉搜索树中两个节点的最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    stack<TreeNode*> stack;
    stack.push(root); // 将根节点入栈

    TreeNode* ancestor = nullptr;
    while (!stack.empty()) {
        TreeNode* node = stack.top();
        stack.pop();

        // 如果节点的值在 p 和 q 的值之间，或者等于 p 或 q 的值，则当前节点为最近公共祖先
        if ((node->val >= p->val && node->val <= q->val) || (node->val <= p->val && node->val >= q->val)) {
            ancestor = node;
        }

        // 如果当前节点的值大于 p 和 q 的值之间的较大值，则继续向左子树查找
        if (node->val > max(p->val, q->val)) {
            if (node->left) {
                stack.push(node->left);
            }
        }

        // 如果当前节点的值小于 p 和 q 的值之间的较小值，则继续向右子树查找
        if (node->val < min(p->val, q->val)) {
            if (node->right) {
                stack.push(node->right);
            }
        }
    }

    return ancestor;
}

// 创建二叉树
TreeNode* createTree(vector<int>& nodes, int index) {
    if (index >= nodes.size() || nodes[index] == -1) {
        return nullptr; // 如果节点为空，则返回nullptr
    }
    TreeNode* root = new TreeNode(nodes[index]); // 创建当前节点
    root->left = createTree(nodes, 2 * index + 1); // 创建左子树
    root->right = createTree(nodes, 2 * index + 2); // 创建右子树
    return root; // 返回当前节点
}

// 销毁二叉树
void destroyTree(TreeNode* root) {
    if (!root) return; // 如果根节点为空，直接返回
    destroyTree(root->left); // 递归销毁左子树
    destroyTree(root->right); // 递归销毁右子树
    delete root; // 删除当前节点
}

int main() {
    vector<int> nodes = {6, 2, 8, 0, 4, 7, 9, -1, -1, 3, 5}; // 二叉搜索树的先序遍历序列
    TreeNode* root = createTree(nodes, 0); // 创建二叉树
    TreeNode* p = root->left->left; // 指定节点 p
    TreeNode* q = root->left->right->left; // 指定节点 q
    TreeNode* ancestor = lowestCommonAncestor(root, p, q); // 查找最近公共祖先
    cout << "The lowest common ancestor of " << p->val << " and " << q->val << " is " << ancestor->val << endl;

    destroyTree(root); // 销毁二叉树

    return 0;
}

微服务

文档

基础

快手游戏服务端开发一面 ​

1、tcp的重传机制有哪几种？具体描述一下 ​

1. 超时重传（Timeout Retransmission） ​

2. 快速重传（Fast Retransmit） ​

3. 选择性确认（Selective Acknowledgment, SACK） ​

4. 快速恢复（Fast Recovery） ​

5. 重复数据重传（Duplicate Data Retransmission） ​

2、override、final？ ​

1. override 关键字 ​

用法 ​

2. final 关键字 ​

用法 ​

3、epoll的边缘触发和水平触发？ ​

1. 水平触发（Level Triggered, LT） ​

工作原理 ​

2. 边缘触发（Edge Triggered, ET） ​

工作原理 ​

4、tcp的滑动窗口？ ​

1. 滑动窗口的基本概念 ​

2. 滑动窗口的工作原理 ​

窗口滑动示例 ​

窗口滑动的图示 ​

3. 滑动窗口的优势 ​

4. TCP 滑动窗口的细节 ​

5. 重要的滑动窗口机制 ​

1. 流量控制（Flow Control） ​

2. 拥塞控制（Congestion Control） ​

5、stl的常用容器及其底层实现数据结构？ ​

vector ​

deque ​

list ​

set 和 multiset ​

map 和 multimap ​

unordered_set 和 unordered_multiset ​

unordered_map 和 unordered_multimap ​

stack ​

queue ​

priority_queue ​

6、static的用法和作用？ ​

1. 在函数内部使用 static 变量 ​

2. 在全局或命名空间作用域使用 static 变量或函数 ​

3. 在类中使用 static 成员变量和成员函数 ​

7、智能指针？ ​

1. std::unique_ptr ​

2. std::shared_ptr ​

3. std::weak_ptr ​

4. std::auto_ptr（已弃用） ​

8、虚函数、虚表指针？ ​

1. 虚函数（Virtual Function） ​

2. 虚表（Virtual Table, vtable）和虚表指针（vtable pointer, vptr） ​

9、内存碎片？ ​

1. 外部碎片（External Fragmentation） ​

快手游戏服务端开发一面

1、tcp的重传机制有哪几种？具体描述一下

1. 超时重传（Timeout Retransmission）

2. 快速重传（Fast Retransmit）

3. 选择性确认（Selective Acknowledgment, SACK）

4. 快速恢复（Fast Recovery）

5. 重复数据重传（Duplicate Data Retransmission）

2、override、final？

1. `override` 关键字

用法

2. `final` 关键字

用法

3、epoll的边缘触发和水平触发？

1. 水平触发（Level Triggered, LT）

工作原理

2. 边缘触发（Edge Triggered, ET）

工作原理

4、tcp的滑动窗口？

1. 滑动窗口的基本概念

2. 滑动窗口的工作原理

窗口滑动示例

窗口滑动的图示

3. 滑动窗口的优势

4. TCP 滑动窗口的细节

5. 重要的滑动窗口机制

1. 流量控制（Flow Control）

2. 拥塞控制（Congestion Control）

5、stl的常用容器及其底层实现数据结构？

`vector`

`deque`

`list`

`set` 和 `multiset`

`map` 和 `multimap`

`unordered_set` 和 `unordered_multiset`

`unordered_map` 和 `unordered_multimap`

`stack`

`queue`

`priority_queue`

6、static的用法和作用？

1. 在函数内部使用 `static` 变量

2. 在全局或命名空间作用域使用 `static` 变量或函数

3. 在类中使用 `static` 成员变量和成员函数

7、智能指针？

1. `std::unique_ptr`

2. `std::shared_ptr`

3. `std::weak_ptr`

4. `std::auto_ptr`（已弃用）

8、虚函数、虚表指针？

1. 虚函数（Virtual Function）

2. 虚表（Virtual Table, vtable）和虚表指针（vtable pointer, vptr）

9、内存碎片？

1. 外部碎片（External Fragmentation）