Notes

本文基于 Linux 6.9 内核源码进行分析。 几个数据结构 eventpoll这是 epoll 的主要数据结构，它用于存储 epoll 的相关信息，包括等待队列、就绪队列、红黑树等。 struct eventpoll { wait_queue_head_t wq; // epoll 的等待队列：用于存储等待的进程/线程，指向等待队列头 wait_queue_head_t poll_wait;// 这个 poll_wait 等待队列只有在 epoll 嵌套的情况下才会用到 struct list_head rdllist; // 就绪队列：用于存储就绪的 fd，指向就绪队列头 struct rb_root_cached rbr; // 红黑树：用于存储所有的 fd，指向红黑树根节点 struct wakeup_source *ws; // 一个唤醒源，用于唤醒进程 }; epitemepitem 的作用是将 fd、就绪队列、红黑树节点等信息封装在一起。 struct epitem { union { struct rb_node rbn; // 红黑树节点，用于存储 fd，指向红黑树节点 struct rcu_head rcu; // 用于释放 epitem }; struct list_head rdllink; // 就绪队列节点，用于存储就绪的 fd，指向就绪队列节点 struct eventpoll *ep; // 指向 eventpoll struct epoll_filefd ffd; // epoll 文件描述符 struct wakeup_source *ws; // 一个唤醒源，用于唤醒进程 struct epoll_event event; // 监听的事件 }; ep_pqueue给 poll 队列封装的结构体，用于存储 poll_table 和 epitem。 ...

C++ 内存模型从上（高地址）到下（低地址）可以分为以下几个部分： 栈区：由编译器自动分配释放，存放函数的参数值、局部变量的值等。 堆区：由程序员分配释放，若程序员不释放，程序结束时可能由操作系统回收。 全局/静态区：分为 .data 段（全局初始化区）和 .bss 段（全局未初始化区），.data 段存放 已初始化 了的全局变量和静态变量，.bss 段存放 未初始化 的变量。 常量区：就是 .rodata 段，存放常量。 代码区：存放函数体的代码。

链地址法链地址法也叫做拉链法，它的基本思想是，将哈希表中的每个槽位都指向一个链表，当发生哈希冲突时，将数据插入到链表中。 很好理解，如图所示： 开放定址法开放定址法是一种解决哈希冲突的方法，它的基本思想是，当发生哈希冲突时，不是将数据直接插入到哈希表中，而是寻找哈希表中的空槽位，将数据插入到空槽位中。 线性探测线性探测采用固定步长的线性搜索来进行探测。 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为 1），直至找到空桶，将元素插入其中。 查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。 注意，我们不能在开放寻址哈希表中直接删除元素。因为删除元素会在数组内产生一个空桶 None ，当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在。 为了解决该问题，我们可以采用懒删除（ lazy deletion ）机制，不直接从哈希表中移除元素，而是利用一个常量 TOMBSTONE 来标记这个桶。 None 和 TOMBSTONE 都代表空桶，都可以放置键值对。线性探测到 TOMBSTONE 时应该继续遍历，因为其之下可能还存在键值对。在线性探测中记录遇到的首个 TOMBSTONE 的索引，并将搜索到的目标元素与该 TOMBSTONE 交换位置，这样可以优化效率。 线性探测容易产生 聚集现象，为了缓解这个问题，就有了平方探测和双重散列。 平方探测平方探测思想与线性探测类似，不同之处在于探测的步长是平方级别的。即当发生哈希冲突时，探测的步长为 1，4，9，…步。 平方探测可以缓解线性探测的聚集现象，但不能彻底解决。 多次哈希多次哈希的基本思想是，当发生哈希冲突时，尝试其他的哈希函数，直到找到空槽位。 与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量。 警告 以上三种方法，线性探测、平方探测和多次哈希哈希表都存在 不能直接删除元素 的问题。 ...

常用容器 序列容器 vector: 动态数组，随机插入/删除 O(n)，随机访问 O(1)，尾插 O(1) array: 静态数组，不支持插入/删除，随机访问 O(1) deque: 双端队列，头尾插入/删除 O(1)，随机访问 O(1)，中间插入/删除 O(n) list: 双向链表，插入/删除 O(1)，不支持随机访问 forward_list: 单向链表，插入/删除 O(1)，不支持随机访问 关联容器（底层实现为 红黑树 ） set: 有序集合，插入/删除/查找 O(logn) map: 有序映射，插入/删除/查找 O(logn) multiset: 有序多重集合，插入/删除/查找 O(logn) multimap: 有序多重映射，插入/删除/查找 O(logn) 无序容器（底层实现为 哈希表 ） unordered_set: 无序集合，插入/删除/查找 O(1) unordered_map: 无序映射，插入/删除/查找 O(1) unordered_multiset: 无序多重集合，插入/删除/查找 O(1) unordered_multimap: 无序多重映射，插入/删除/查找 O(1) 容器适配器 stack: 栈，后进先出，只能在栈顶插入/删除元素 queue: 队列，先进先出，只能在队尾插入，在队头删除元素 priority_queue: 优先队列，元素按照一定规则排序，每次取出的是最大/最小元素，底层实现为堆 vector#include <iostream> #include <vector> using namespace std; // vector使用示例 int main() { vector<int> vec = {1, 2, 3, 4, 5}; // 尾部插入元素：复杂度为O(1) vec.push_back(6); // 尾部删除元素：复杂度为O(1) vec.pop_back(); // 随机插入和删除元素：复杂度为O(n) vec.insert(vec.begin() + 1, 3); vec.erase(vec.begin() + 1); // vector的大小 cout << vec.size() << endl; // 获取vector的容量 cout << vec.capacity() << endl; // 判断vector是否为空 cout << vec.empty() << endl; // 获取vector的第一个元素和最后一个元素 cout << vec.front() << endl; cout << vec.back() << endl; // 访问指定位置的元素 cout << vec[2] << endl; cout << vec.at(2) << endl; // at函数会检查索引是否越界，更安全 vector<int> vec2 = {7, 8, 9, 10}; vec.swap(vec2); // 交换两个vector的元素 // 清空vector vec.clear(); } vector 常用的成员函数： ...

对象MyClass obj; obj.fun(); obj.count = 10; 对象是类的实例，占据实际的内存空间，可以调用类的成员函数和访问类的成员变量。 对象大小 = 成员变量大小 + 对齐填充 指针MyClass *p = new MyClass; p->fun(); p->count = 10; 指针是一个变量，存储对象的地址，可以通过指针访问对象的成员函数和成员变量。 指针大小 = 4 字节（32 位系统）或 8 字节（64 位系统） 对象和指针的区别 内存管理 对象：内存分配和释放通常是自动的（除非使用动态分配）。 指针：指向的内存需要手动管理，尤其是动态分配的内存。 访问方式： 对象：直接访问成员。 指针：通过解引用访问成员（使用 -> 操作符）。 生命周期： 对象：由作用域决定，局部对象在离开作用域时自动销毁。 指针：生命周期由程序员控制，指针可以指向任何作用域的变量。

C++ 的多态性是面向对象程序设计的三大特性之一（封装、继承、多态），它允许将子类对象赋值给父类对象，从而实现基类指针指向子类对象，实现基类指针调用子类对象的成员函数。 C++ 的多态性主要有两种实现方式：静态多态和动态多态。 静态多态：通过函数重载和模板实现。 动态多态：通过虚函数实现。 静态多态函数重载函数重载是指在同一个作用域内，可以定义 多个名称相同 但 参数列表不同 的函数。注意，不能用 返回值类型 来区分重载函数。 int add(int a, int b) { return a + b; } double add(double a, double b) { return a + b; } double add(double a, double b, double c) { return a + b + c; } 笔记 编译过程 ...

TCP 的拥塞控制算法有几种： Tahoe Reno NewReno SACK BIC CUBIC BBR 笔记 MSS: Maximum Segment Size，最大分段大小。 ...

智能指针简介智能指针是一种 RAII（Resource Acquisition Is Initialization）技术，用于管理动态分配的内存。智能指针的优点是可以自动释放内存，避免内存泄漏。 C++11 标准引入了三种智能指针：std::unique_ptr、std::shared_ptr 和 std::weak_ptr。 它们都定义在头文件 <memory> 中。 unique_ptrunique_ptr 是一种独占所有权的智能指针，它保证同一时间只有一个指针可以指向对象。 unique_ptr 的创建#include <iostream> #include <memory> int main() { // 使用 new 创建 unique_ptr std::unique_ptr<int> up1(new int(10)); std::cout << *up1 << std::endl; // 使用裸指针创建 unique_ptr int count = 20; std::unique_ptr<int> up2(&count); std::cout << *up2 << std::endl; // 使用 make_unique 创建 unique_ptr auto up2 = std::make_unique<int>(20); std::cout << *up2 << std::endl; return 0; } unique_ptr 的拷贝和赋值unique_ptr 不能拷贝，但可以移动。 #include <iostream> int main() { std::unique_ptr<int> up1(new int(10)); std::unique_ptr<int> up2 = std::move(up1); std::cout << *up2 << std::endl; return 0; } unique_ptr 的释放unique_ptr 会在离开作用域时自动释放内存。 #include <iostream> int main() { std::unique_ptr<int> up1(new int(10)); std::cout << *up1 << std::endl; return 0; } unique_ptr 的自定义删除器unique_ptr 支持自定义删除器，可以用于释放动态分配的内存。 ...

Redis 采用单线程的原因是因为在 内存中 进行读写操作，CPU不是Redis的性能瓶颈，而是内存和带宽，所以采用单线程可以避免 线程切换和锁的开销。 Redis 是什么？Redis 是一个开源的内存数据库，它可以存储键值对，支持多种数据结构，如字符串（string）、哈希（hash）、列表（list）、集合（set）、有序集合（zset）等。 Redis 是不是单线程？实际上，Redis 是多线程的，其内部有以下几个线程： redis-server：主线程，负责接收客户端的连接，读取请求，发送响应。 bio-close-file：负责异步关闭大文件。 bio-aof-fsync：负责将 AOF 文件异步刷到磁盘。 bio-lasy-free：负责异步释放大内存。 jemalloc-bg-thread：负责内存碎片整理。 io-thread：IO 线程，负责 read/write，decode/encode。 笔记 AOF（Append Only File） 是 Redis 的一种持久化方式，将所有写操作追加到文件末尾，重启时重新执行 AOF 文件中的命令即可恢复数据。实时硬盘操作，不会丢失数据，但是会影响性能。 ...

在学习堆排序之前，我们先来了解一下堆这种数据结构。 堆的概念堆是一种特殊的树形数据结构，它满足以下性质： 堆必须是一个 完全二叉树 。 堆序性：堆中任意节点的值总是不大于或不小于其子节点的值。 根据堆序性，我们可以将堆分为两种类型： 大顶堆：每个节点的值都大于或等于其子节点的值 小顶堆：每个节点的值都小于或等于其子节点的值 所以，如果一个完全二叉树的一个节点即大于其父节点，又大于其子节点，那么这个树就不是一个堆。小于同理。 笔记 完全二叉树的性质 ...