链地址法链地址法也叫做拉链法，它的基本思想是，将哈希表中的每个槽位都指向一个链表，当发生哈希冲突时，将数据插入到链表中。 很好理解，如图所示： 开放定址法开放定址法是一种解决哈希冲突的方法，它的基本思想是，当发生哈希冲突时，不是将数据直接插入到哈希表中，而是寻找哈希表中的空槽位，将数据插入到空槽位中。 线性探测线性探测采用固定步长的线性搜索来进行探测。 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为 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; } 笔记 编译过程 ...

互联网发展至今，HTTP 协议已经发展了多个版本，分别为 HTTP/1.0、HTTP/1.1、HTTP/2.0、HTTP/3.0，本文将对这几个版本的变化进行学习笔记。 HTTP/1.0HTTP/1.0 是最早的 HTTP 协议版本，它的特点是： 每次请求都会建立一个新的 TCP 连接，请求结束后立即断开连接。 每个请求都会包含完整的请求头和请求体。 不支持持久连接，每次请求都需要重新建立连接。 不支持管道化，即同一个连接中不能同时发送多个请求。 HTTP/1.1HTTP/1.1 是对 HTTP/1.0 的改进，它的特点是： 支持持久连接（Keep-Alive），即同一个连接可以发送多个请求。 支持管道化，即同一个连接中可以同时发送多个请求。但是，由于 HTTP/1.1 中的管道化存在队头阻塞问题，所以很少被使用。默认为关闭状态，并且大多数浏览器也不支持。 所以我们认为 HTTP/1.1 不支持管道化 。 HTTP/1.1 的缺点： 队头阻塞问题：如果一个请求响应时间过长，那么后面的请求就会被阻塞。 明文传输：HTTP/1.1 的数据传输是纯文本且未加密的，容易被窃听。比如状态码 200 会被分为 2、0、0 三个字节传输。这点会在 HTTP/2.0 中得到改进。 头部冗余：每次请求都需要携带完整的请求头，头部信息冗余。 HTTPS在讲述 HTTP/2.0 之前，我们先来了解一下 HTTPS。 HTTPS 是在 HTTP 的基础上加入了 SSL/TLS 加密层，使得数据传输更加安全。HTTPS 的特点是： 数据加密：HTTPS 使用 SSL/TLS 加密传输数据，保证数据传输的安全性。 身份认证：HTTPS 使用证书机制对服务器和客户端进行身份认证，防止中间人攻击。 数据完整性：HTTPS 使用数字签名对数据进行完整性校验，防止数据被篡改。 加密方式：对称加密、非对称加密、数字签名。 通信前使用非对称加密协商对称加密的密钥，通信过程使用对称加密传输数据，保证数据传输的安全性。 HTTP/2.0HTTP/2.0 是对 HTTP/1.1 的重大升级，它的特点是： 头部压缩：HTTP/2.0 使用 HPACK 算法对头部进行压缩，如果请求头中包含相同的字段，只需要发送一次，后续请求只需要发送索引，接着从静态表或动态表中获取对应的值。解决了 HTTP/1.1 中头部冗余的问题。 ...

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 文件中的命令即可恢复数据。实时硬盘操作，不会丢失数据，但是会影响性能。 ...

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

代码class AClass { private: int _count; public: AClass() : _count(0) { std::cout << "Default constructor called\n"; } // 赋值运算符，返回引用 AClass &operator=(int cnt) { _count = cnt;k return *this; } // 后置自增运算符，返回引用 int &operator++(int) { ++_count; return *this; } }; 如果不使用引用返回，其实也是可以运行的，只不过会在返回时调用拷贝构造函数，生成临时对象，然后再调用析构函数释放临时对象，这样会多出一次拷贝构造和析构的开销。而使用引用返回，可以直接返回对象的引用，避免了这个开销。 需要注意的是，如果我们返回值类型，我们是不能直接修改返回值的： class AClass { private: int _count; public: // 省略构造函数 // 赋值运算符，返回引用 AClass operator=(int cnt) { _count = cnt; return *this; } // 后置自增运算符，返回引用 int operator++(int) { ++_count; return *this; } void print() const { std::cout << "AClass: count = " << _count << '\n'; } }; int main() { AClass a; a.print(); // 输出 AClass: count = 0 (a++) = 10; a.print(); // 输出 AClass: count = 1 (a++)++; a.print(); // 输出 AClass: count = 2 } 可以看到，如果我们返回值类型，我们是不能直接修改返回值的。虽然 a++ 已经修改了 a 的值，但是 a++ 返回的是一个修改后的 a 对象的拷贝，所以 (a++) = 10; 或者 (a++)++; 修改的是这个拷贝对象，而不是原对象 a。 ...