Algorithm

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

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

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